[Algorithms] 4.2 Breadth-first search
해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다.해석하면서 정리한 글입니다.
4.2 Breadth-first search
위 그림에서 S의 리프팅은 그래프를 layers(S와, 거리 1의 노드들, 거리 2의 노드)로 분할합니다.
정점 S부터 거리를 계산하는 가장 편한 방법은 한 층씩 진행하는 것 입니다.
- 거리가 0, 1, 2, …, d인 노드들을 골라냈다면, 거리가 d+1인 노드들은 쉽게 결정이 가능합니다.
- 이 노드들은 거리가 d인 노드에 인접(adjacent)하면서, 아직 안 본(as-yet-unseen) 노드들 입니다.
- 이를 통해, iterative algorithm을 설계할 수 있습니다.(2 layers가 동작하는 방식으로)
- 확실히 알아낸 어떤 layer d가 있고, 그 layers의 neighbors를 살펴보면서 발견하게 되는 d+1 layer가 존재합니다.
BFS(Breadth-first search)알고리즘은 layer by layer로 단순히 동작하는 알고리즘입니다.
동작방식
- (초기화) queue Q는 정점 s로만 구성, 이 때 이 노드의 거리는 0입니다.
- 각각의 후속 거리 d=1,2,3,…에 대해 Q에는 거리 d에 있는 모든 노드가 포함되고 다른 노드는 포함되지 않는 시점이 있습니다.
- 이러한 노드가 처리되면(대기열 앞쪽에서 꺼짐), 아직 표시되지 않은 인접 노드가 대기열 끝에 주입됩니다.
앞선 그림을 다시 예제로 살펴보겠습니다. 
(a)의 그래프를 보면 DFS 그래프(b)와 다르게, S에서 출발하는 모든 path들은 shortest입니다.(DFS-search tree와 다릅니다)
따라서 (a)는 shortest-path tree라고 할 수 있습니다.
Correctness
앞서 BFS의 basic intuition을 살펴보았습니다.
알고리즘이 정확히 작동하는지 확인하기 위해서는 아래와 같은 내용을 검토해야 합니다.
- For each d = 0, 1, 2, …, there is a moment at which
- all nodes at distance ≤ d from s have their distances correctly set
- all other nodes have their distances set to ∞;
- the queue contains exactly the nodes at distance d.
Efficiency
The overall running time of Algorithm : linear, $O(|V|+|E|)$
- 알고리즘 시간 = DFS와 동일한 이유입니다.
- 모든 노드가 큐에 정확히 한 번씩 존재합니다. (inject, eject 연산)
$2 V $ queue operations
- 나머지는 알고리즘의 내부에 동작하는 loop에서 걸립니다. (checking adjacency)
- 각 edge들을 한번씩 훑습니다. (in directed graphs)
- 각 edge들을 두번씩 훑습니다. (in undirected graphs)
$O( E )$ time
DFS vs. BFS
- DFS
- 그래프로 깊숙히 incursion 하여, 더 이상 방문할 새 노드가 없을때만 run out 합니다.
- (+) wonderful, subtle, and extremely useful properties
- (-) 실제로 매우 가까운 두 vertex 까지 비효율적인 path를 택할 수 있습니다.
- BFS
- 시작점부터 distance를 기준으로 정점을 방문합니다.
- DFS에 비해 더 넓고 얕은 탐색입니다.
- DFS와 거의 비슷한 code로 이루어져 있습니다.(스택 대신 큐가 있습니다)
- 추가적으로 다른 점이 있습니다.(less important)
- BFS는 s로부터의 거리에만 관심이 있으므로 연결된 다른 구성요소에서는 검색을 다시 실행하지 않습니다.
- s에서 연결할 수 없는 노드는 무시됩니다.
Reference
- Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani(http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf)
