그래프

23.08.02

그래프

그래프 종류

그래프 구현

그래프 순회

BFS (너비 우선 탐색)

BOJ_9934 : BFS를 ‘트리’로 구현한 문제

BFS를 ‘그래프’로 구현하기

그래프

Vertex와 Edge로 구성된 자료구조

ex ) 네비게이션 길찾기, 게임 내 캐릭터 이동, 지식 그래프

그래프 종류

• 방향 그래프
  • 방향이 있는 순서대로만 루트

• 무방향 그래프

• 가중치 그래프
  • 각 vertex에 가중치가 존재
    • bellman
    • dikstra

• 루프 그래프

• 순환 그래프
  • cycle이 존재하는 그래프

그래프 구현

• 인접행렬
  • 이차원 배열

    

    1 : 연결 || 0 : 연결 x

• 인접 리스트
  • vertex개수 만큼의 list 사용

    

    • 인접행렬에 비해…
      • 메모리 공간을 효율적으로 사용가능
      • 노드를 삭제하거나, 추가하는 것도 인접행렬보다 수월
      • BUT VERTEX간의 연결관계를 확인하는건 인접행렬보다 오래걸림

그래프 순회

• DFS

• BFS

• 위상정렬

---

BFS (너비 우선 탐색)

그래프에 있어서, 가까운 곳 부터 탐색하는 방법

트리 → BFS로 탐색함

BOJ_9934 : BFS를 ‘트리’로 구현한 문제

[1] Root 노드인 3이 queue에 삽입

[2] Root가 poll되고, 해당 노드의 왼쪽, 오른쪽을 큐에 추가(6,2)

[3] for문이 돌면서, 가장 먼저 들어간 6이 poll되고 6의 왼쪽과 오른쪽을 큐에 추가 (1, 4)

[4] for이 돌면서, 이후 들어간 2가 poll되고 2의 왼쪽과 오른쪽을 큐에 추가 (5, 7)

BFS를 ‘그래프’로 구현하기

[1] 가장 우선 노드인 A가 큐에 삽입된다.

[2] A가 poll된 후, A와 연결된 B가 큐에 삽입된다.

[3] B가 poll된후, B와 연결된 C,D,E,가 큐에 삽입된다. (이때, C,D,E의 순서는 상관 없음)

[4] C,D,E중 가장 먼저 들어간 C가 poll 되면서 C와 연결된 F가 추가적으로 큐에 삽입된다. (D는 이미 들어가있음)

[5] D가 poll되면서 D와 연결된 G, H가 추가적으로 큐에 삽입된다. (E는 이미 들어가있음)

[6] 모두 들어가있으므로 이제 큐에서 하나씩 POLL된다.

[7] 큐에서 모두 poll되어 isEmpty가 되면 끝

Uploaded by N2T