넓이 우선 탐색(BF)은 한 소스 정점, $s$로부터 가장 가까운 거리에 있는 정점들부터 하나씩 탐색한다.
BFS의 과정을 조금 더 쉽게 이해하기 위해 각 정점은 흰색, 회색, 검정색 중 하나의 색으로 칠해져 있다고 가정한다.
여기서 흰색은 방문한 적이 없는 정점이고, 회색 또는 검정색은 방문한 적이 한 번이라도 있는 (discovered) 정점을 의미한다.
회색과 검정색을 비교하면, 회색은 인접한 정점 중 흰색 정점이 존재하는 정점을 의미하고, 검정색은 인접한 정점이 모두 흰색이 아닌 정점을 의미한다(BFS의 실제 구현만을 위해서는 구분이 필요하지 않다고 한다. 이해를 돕기 위한 구분..).
BFS는 breadth-first tree를 만들게 된다. 트리의 루트는 source vertex인 $s$이다.
이미 방문한 정점 $u$의 인접 리스트를 탐색하는 과정에서 흰 색 정점인 $v$를 발견하면, 정점 $v$와 간선 $(u,v)$가 트리에 추가된다. 이 때 $u$를 breadth-first tree에서 $v$를 $u$의 predecessor또는 parent라고 부른다. 각 정점은 최대 한 번의 발견되는 순간을 가지므로 최대 하나의 부모(parent)를 가진다.
breadth-first tree에서 선조(ancestor)와 자손(descendant)관계는 루트인 $s$와 상대적으로 정의된다. $u$가 루트 $s$에서 정점 $v$로 이어지는 path에 있으면 $u$는 $v$의 선조이고, $v$는 $u$의 자손이다.
밑에 소개할 BFS 과정은 그래프 $G = (V,E)$가 인접 리스트로 나타내어져 있다고 가정한다.
또한 그래프의 각 정점에 몇 개의 속성(attribute)을 부여한다. $u \in V$에 대해 $u.color$는 $u$의 색을 의미하고, $u.π$는 $u$의 직전 정점을 의미한다. $u = s$이거나 $u$가 발견되지 않아서 직전 정점이 없다면 $u. \pi = NIL$이다.
$u.d$는 알고리즘에서 계산된 소스 $s$로부터 정점 $u$까지의 거리를 의미한다.
또한 알고리즘은 FIFO의 특성을 가진 큐, $Q$를 사용하여 회색 정점의 집합을 관리한다.
다음은 $BFS(G,s)$의 수도 코드이다.
for each vertex u ∈ G.V - {s}
u.color = WHITE
u.d = ∞
u.π = NIL
s.color = GRAY
s.d = 0
s.π = NIL
Q = ∅
Enqueue(Q, s)
while Q ≠ ∅
u = Dequeue(Q)
for each v ∈ G.Adj[u]
if v.color == WHITE
v.color = GRAY
v.d = u.d + 1
v.π = u
Enqueue(Q, v)
u.color = BLACK
 정리/img/img-7.png)
소스 s에서 시작한 BFS 과정을 보여줌 (CLRS p. 596)
BFS의 결과는 인접 정점을 방문하는 순서에 따라 달라질 수 있다. 그래서 breadth-first 트리는 다양하게 나올 수 있지만, 그래도 알고리즘에서 계산된 거리 $d$는 모두 같게 나온다.
분석
그래프 $G = (V,E)$의 실행 시간을 분석해보자.
알고리즘에서 초기를 빼고는 정점을 흰 색으로 다시 칠하는 과정은 없으므로 큐에 한 번 들어갔던 정점은 다시 큐에 들어가게 되지는 않는다. 큐에 입력하는 것(enqueuing)과 큐에서 출력하는 것(dequeuing)은 $O(1)$이 소요되므로 큐 연산에 소요되는 총 시간은 $O(V)$이다.
각 정점의 인접 리스트는 해당 정점을 큐에서 출력할 때만 스캔하므로, 각각의 인접 리스트는 최대 한 번 스캔된다. 모든 인접 배열의 길이의 sum은 $\Theta(E)$이므로 인접 리스트를 스캔하는 데 걸리는 총 시간은 $O(E)$이다.
알고리즘의 초기화 과정에는 $O(V)$가 소요된다.
종합한 BFS 과정의 소요 시간은 $O(V+E)$이다. 즉, bfs의 소요 시간은 그래프의 인접 리스트 표현의 사이즈에 선형으로 비례한다.
Shortest paths
그래프 $G = (V,E)$에서 소스 정점을 $s \in V$라 하자.
shortest-path distance(최단 경로 거리) $\delta(s,v)$를 $s$에서 $v$까지의 경로 중 최소 간선 갯수라고 정의한다. 만약 $s$에서 $v$까지 가는 것이 불가능하다면 $\delta(s,v) = \infty$이다.
다음은 최단 경로 거리의 중요 성질이다.
Lemma 22.1
$G = (V, E)$를 directed 또는 undirected 그래프라 하고, $s \in V$를 임의의 정점이라 하자. 그러면 모든 간선 $(u, v)\in E$에 대해 다음이 성립한다.
\[\delta(s,v) \leq \delta(s,u) + 1\]Proof
$(u, v)$의 간선이 존재하므로 $s$에서 $u$가 접근 가능(reachable)하다면 $v$도 가능하다. 이 경우에 $s$에서 $v$까지의 최단 거리는 $s$에서 $u$까지의 최단 거리에 간선 (u,v)의 거리인 1을 더한 것보다 더 길 수는 없다. 따라서 부등식이 성립.
$s$에서 $u$까지 접근할 수 없다면 $\delta(s,u) = \infty$이므로 부등식이 성립한다.
BFS가 각 정점 $v \in V$에 대해 $v.d = \delta(s,v)$가 되도록 계산하는지 확인해 보려 한다. 우선은 $v.d$가 $\delta(s,v)$를 위에서 유계(bound from above)하는지 알아보자.
Lemma 22.2
$G = (V,E)$를 directed 또는 undirected 그래프라 하고 주어진 소스 정점 $s \in V$에서 BFS를 시행했다고 하자. 시행이 끝난 후 각 정점 $v \in V$에 대해 BFS에서 계산된 $v.d$의 값은 $v.d \geq \delta(s,v)$을 만족한다.
Proof
enqueue연산의 경우들에 귀납법을 사용한다. 이 때 귀납적 가설은 모든 $v \in V$에 대해 $v.d \geq \delta(s,v)$하다는 것이다.
첫 단계는 알고리즘에서 처음에 $s$를 enqueue한 직후의 상황이다. 이 때는 $s.d = 0 = \delta(s,s)$이고 모든 $v \in V - {s}$에 대해 $v.d = \infty \geq \delta(s,v)$이므로 귀납적 가설이 성립한다.
그 뒤의 단계에서는 정점 $u$에서의 탐색 과정에서 발견된 흰 색 정점 $v$을 생각해보자. 귀납적 가설을 통해 $u.d \geq \delta(s,u)$라 할 수 있다. 알고리즘에서 할당한 속성 $d$와 lemma 22.1로부터 다음의 결과를 얻을 수 있다.
\[\begin{equation} \begin{split} v.d & = & u.d + 1 \\ & \geq & \delta(s,u) + 1 \\ & \geq & \delta(s,v) \\ \end{split} \end{equation}\]할당 이후에 $v$는 enque되고 회색으로 칠해졌기 때문에 다시 enque되지 않는다. 따라서 $v.d$는 변경되는 일이 없고 귀납적 가설은 깨지지 않는다.
$v.d = \delta(s,v)$임을 증명하기 위해서 큐, $Q$가 BFS 과정에서 어떻게 작동하는지 정확히 살펴봐야 한다. 다음 lemma는 큐가 많아야 두 가지의 다른 $d$값을 가지고 있게 됨을 보여준다.
Lemma 22.3
그래프 $G = (V, E)$에 대한 BFS의 수행 과정에서 큐, $Q$는 정점 $\langle v_1, v_2, \cdots, v_r \rangle$을 가지고 있게 된다. $v_1$은 $Q$의 head이고 $v_r$은 tail이다. $v_r . d \leq v_1 . d + 1$이고, $i = 1,2, \cdots, r-1$에 대해 $v_i .d \leq v_i+1 .d$이다.
Proof
여기서도 비슷하게 귀납법을 사용한다. 초기에 큐에 $s$만 있을 때는 당연히 lemma는 성립한다.
뒤의 단계에서는 큐 인출 직후와 큐에 정점을 입력한 직후에 lemma가 성립하는지 증명해야 한다.
큐의 head $v_1$이 인출되면 $v_2$가 새로운 head가 된다. (큐가 비어있으면 큰 의미는 없지만 lemma는 성립한다.) 귀납적 가설에 의해 $v_1 . d \leq v_2 . d$가 성립하는 것을 알고, 이를 이용해 다른 부등식의 성립에 영향을 주는 일 없이 $v_r . d \leq v_1 .d + 1 \leq v_2 . d + 1$이 성립함을 알 수 있다. 따라서 $v_2$가 head일 때도 lemma가 성립한다.
큐에 정점 $v$를 입력하면 이는 $v_{r+1}$이 된다. 입력이 된 시점에서는 현재 인접 리스트가 스캔되고 있는 정점 $u$는 이미 큐에서 제거된 상태이다. 그리고 귀납적 가설에 의해 새로운 head $v_1$은 $v_1 .d \geq u.d$가 성립한다. 따라서 $v_{r+1} .d = v.d = u.d + 1 \leq v_1 . d + 1$가 성립한다. 다시 귀납적으로 $v_r . d \leq u.d + 1$이 성립하므로 $v_r.d \leq u.d + 1 = v.d = v_{r+1} .d$가 성립하며 나머지 부등식의 성립도 영향받지 않는다. 따라서 $v$가 큐에 입력되었을 때도 lemma는 성립한다.
다음 따름정리는 정점이 큐에 입력되었을 시점의 $d$값은 시간에 따라 단조 증가함을 보여준다.
Corollary 22.4
정점 $v_i$와 $v_j$가 BFS 수행 과정에서 큐에 입력되었다고 하고 $v_i$는 $v_j$의 이전에 입력되었다고 하자. 그러면 $v_j$가 큐에 입력될 시점에서 $v_i .d \leq v_j .d$가 성립한다.
Proof
lemma 22.3과 각 정점은 BFS 과정의 방문을 통해 최대 한 번까지 유한한 값 $d$를 부여받는다는 성질을 통해 확인 가능.
이제 BFS가 정확히 최단 경로 거리를 찾는다는 것을 증명할 수 있다.
Theorem 22.5 (Correctness of breadth-first search)
$G = (V, E)$가 directed 또는 undirected 그래프이고 BFS가 주어진 소스 정점 $s \in V$에서 수행된다고 가정하자. 그러면 실행 과정에서 BFS는 소스 $s$에서 도달 가능한 모든 정점 $ v \in V$를 방문하게 된다. 그리고 종료 시점에서 모든 $v \in V$에 대해 $v.d = \delta(s,v)$가 성립한다. 또한 $v \ne s$인 $s$에서 도달 가능한 정점 $v$에 대해, $s$에서 $v$까지의 최단 경로는 $s$에서 $v.π$까지의 최단 경로 뒤에 간선 $(v.π , v)$을 추가한 것이다.
Proof
귀류법을 위해 몇몇 정점이 최단 경로 거리가 아닌 $d$값을 받는다고 해보자. $v$를 그런 값을 갖는 정점 중 가장 작은 $\delta(s,v)$를 갖는 정점이라 하자($v \ne s$).
lemma 22.2에 의해 $v.d \geq \delta(s,v)$가 성립하고, 처음에 귀류법을 위해 가정한 내용 때문에 $v.d > \delta(s,v)$이다. 여기서 알 수 있는 것은 정점 $v$가 $s$에서 도달 가능해야 한다는 점이다. 그렇지 않으면 $\delta(s,v) = \infty \geq v.d$가 된다. $u$를 $s$에서 $v$까지의 최단 경로에서 $v$를 한 단계 선행하는 정점이라 하자. 그러면 $\delta(s,v) = \delta(s,u) + 1$이 성립한다. $\delta(s,u) < \delta(s,v)$이 성립하고, 가정에서 $v$가 최단 경로 거리와 $d$가 일치하지 않는 정점 중 가장 짧은 최단 경로 거리를 갖는 정점이라 했으므로 $u$는 최단경로 거리와 $d$가 일치하게 된다(즉, $u.d = \delta(s,u)$).
이를 종합하면 다음을 얻을 수 있다.
\[v.d > \delta(s,v) = \delta(s,u) + 1= u.d + 1\]BFS 과정 중 $Q$에서 정점 $u$를 출력하는 시점을 생각해보자. 이 시점에서 $v$는 흰색, 회색, 검정색 중 하나이다. 세 경우에서 바로 위의 식에 모순이 되는 경우가 나옴을 보이고자 한다.
만약 $v$가 흰 색인 경우, $v.d = u.d + 1$이 되어서 위 식에 모순이 된다.
만약 검정 색인 경우, $v$는 이미 큐에서 제거되었을 것이고 따름정리 22.4에 의해 $v.d \leq u.d$가 되어 식과 모순이다.
회색인 경우, 어떤 정점 $w$를 큐에서 인출하는 과정에서 $v$가 회색으로 칠해졌을 것이다. 그러면 $w$는 $u$보다 먼저 인출되었을 것이고 $v.d = w.d + 1$일 것이다. 따름정리 22.4에 의해 $w.d \leq u.d$이 성립하여 $v.d = w.d + 1 \leq u.d + 1$이 되어 여기서도 모순이다.
따라서 모든 $v \in V$에 대해 $v.d = \delta(s,v)$이 성립한다고 결론지을 수 있다. 또한 $s$에서 도달 가능한 모든 정점 $v$가 방문되지 않으면 $\infty = v.d > \delta(s,v)$가 되므로 BFS 과정에서 꼭 한 번씩 방문되어야 한다.
만약 $v.π = u$인 경우, $v.d = u.d + 1$이므로 $s$에서 $v$까지의 최단 경로는 $s$에서 $v.π$까지의 최단 경로에 간선 $(v.π, v)$를 추가하면 된다.
Breadth-first trees
소스 $s$와 그래프 $G = (V, E)$에 대해 $G$의 ‘predecessor subgraph‘를 $G_{\pi} = (V_{\pi}, E_{\pi})$로 나타내고 다음과 같이 정의한다.
$G_{\pi} = (V_{\pi} , E_{\pi})$이고, 이 때 $V_{\pi} = { v \in V : v. \pi \ne NIL } \cup { s}$이고 $E_{\pi} = { ( v.\pi , v) : v \in V_{\pi} - { s}}$이다.
만약 $V_{\pi}$가 $s$에서 도달 가능한 정점들로 이루어져있고, 동시에 모든 $v \in V_{\pi}$에 대해 subgraph $G_{\pi}$가 그래프 $G$내에서 $s$에서 $v$까지의 최단 경로인 유일한 단순 경로(unique simple path)들을 포함하고 있으면 predecessor subgraph $G_{\pi}$는 breadth-frist tree이다.
breadth-first tree는 $|E_{\pi}| = |V_{\pi}| - 1$이고 서로 연결되어있으므로 트리라 할 수 있다. $E_{\pi}$에 있는 간선들을 tree edges라고 부른다.
Lemma 22.6
directed 또는 undirected 그래프인 $G = (V, E)$에 대해 BFS 과정은 predecessor subgraph $G_{\pi} = (V_{\pi} , E_{\pi})$가 breadth-first tree이도록 해주는 $\pi$를 할당해준다.
Proof
BFS의 알고리즘에서 $v.\pi = u$로 할당하는 것은 $(u, v) \in E$이고 $\delta(s,v) < \infty$임과 동치이다. 그 말은 $v$가 $s$에서 도달 가능하다는 말이기도 하므로 $V_{\pi}$가 $s$에서 도달 가능한 $V$의 정점들로 이루어져 있음을 의미한다. $G_{\pi}$가 트리를 형성하므로 Theorem B.2(책 참고)에 의해 $G_{\pi}$는 $s$에서 $V_{\pi}$의 각 정점들로 도달하는 유일한 단순 경로를 포함하고 있다. Theorem 22.5를 귀납적으로 적용하여 그런 경로들이 $G$에서 최단 거리 경로라고 결론지을 수 있다.