그래프에서의 BFS

강의 사이트

• http://www.kocw.net/home/search/kemView.do?kemId=1148815

그래프 순회

1. 순회(traversal)

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

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

2. 너비 우선 순회 (BFS)

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

2.1 큐를 이용한 너비 우선 순회

2.2 Pseudo Code

2.3 BFS와 최단 경로

• 최단 경로까지 가는 도중 길이를 저장할 변수가 필요

• 입력: 방향 혹은 무방향 그래프 G=(V,E), 그리고 출발노드 s∈V
• 출력: 모든 노드 v에 대해서
  • d[v] = s로부터 v까지의 최단 경로의 길이(에지의 개수)
  • π[v] = s로부터 v까지의 최단경로상에서 v의 직전(이전) 노드(predecessor)
• 아래는 최단경로 추가한 수도 코드

• undirected 그래프라고 가정

• 인접리스트로 표현하면 시간복잡도는 O(n+m)이고 인접행렬로 구현하면 O(n^2)이다.

3. BFS 트리

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

• 어떤 에지도 2개의 Layer를 건너가지 않는다. 다시 말해서 L0에서 L2로 바로 가는 경로는 없다. 어쨌든 L1을 지날 수 밖에 없다는 이야기

3.1 최단 경로 출력하기

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