인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

---

그래프 순회

순회(traversal)

• 그래프의 모든 노드들을 방문하는 일

대표적 두 가지 방법

• BFS (Breadth-First Search, 너비우선순회)
• DFS (Depth-First Search, 깊이우선순회)

---

너비우선순회 (BFS)

BFS 알고리즘은 다음 순서로 노드들을 방문

큐를 이용한 너비우선순회

---

수도코드

---

BFS와 최단경로

• S에서 Li에 속한 노드까지의 최단 경로의 길이는 i이다.

  (여기서 경로의 길이는 경로에 속한 에지의 개수를 의미한다.)

• BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다.

입력 : 방향 혹은 무방향 그래프 G = (V, E), 그리고 출발 노드 s ∈ V

출력 : 모든 노드 v에 대해서

• d[V] = s로 부터 v까지의 최단 경로의 길이(에지의 개수)

• π[V] = s로부터 c까지의 최단경로상에서 v의 직전 노드(predecessor)

  

• 약간 변경한 버젼(π[s]가 아니라 π[u]다.)

  

---

각 노드 v와 π[V]를 연결하는 에지들로 구성된 트리

• BFS 트레이서 S에서 V까지의 경로는 s에서 v까지 가는 최단경로

• 어떤 에지도 2개의 layer를 건너가지 않는다.
  (동일 레이어의 노드를 연결하거나, 혹은 1개의 layer를 건너간다.)

  

---

너비우선순회: 최단 경로 출력하기

---

너비우선순회 (BFS)

• 그래프가 disconnected이거나 혹은 방향 그래프라면 BFS에 의해서 모든 노드가 방문되지 않을 수도 있음

• BFS를 반복하여 모든 노드 방문

  BFS-ALL( G )
  {
    while there exists unvisited node v
      BFS(G, V);
  }