[알고리즘/이론]너비 우선 탐색(BFS)

BFS는 간단한 검색 알고리즘으로 많은 그래프 알고리즘의 원형이 되는 알고리즘이다.

발견된 정점과 발견되지 않은 정점 사이의 경계선을 균일하게 확장시켜나간다는 사실에서 너비 우선 검색이라는 이름이 유래하게 되었다. 즉, 거리가 k인 정점을 모두 탐색한 후에 k+1의 거리를 갖는 정점을 탐색한다는 뜻이기도 한다.

특징적인 부분으로 이 알고리즘은 그래프 내의 하나의 출발점에서 도달이 가능한 모든 정점을 체계적으로 검색하는 알고리즘이다.

(검색이란 그래프 내의 정점을 방문하기 위해 간선을 규칙에 맞춰 따라가는 행위이다.)

또한, 출발점에서 도달이 가능한 모든 정점을 포함하는 너비 우선 트리를 만들며, 이때 각 정점까지의 단순 경로는 출발점에서 특정 정점까지의 거리를 의미한다.

(거리란 정점과 정점 사이의 최소의 간선 개수를 의미합니다.)

보통 너비 우선 검색을 구현할 때는 그것의 방문 여부를 구별할 변수와 루트로부터의 거리, 직전원소(부모), 큐를 활용하여 구현한다.

(자세한 구현에 의문이 생긴다면 댓글주시면 감사하겠습니다.)

너비 우선 검색으로 인해 생긴 너비 우선 트리는 정점을 검색하는 순서에 따라 달라질 수 있지만 그 정점과 루트 사이의 거리를 절대로 달라지지 않는다고 한다.

---

수행시간의 분석은 다음과 같다.

모든 정점은 한 번 발견된 후 큐를 단 한 번 통과한다. 따라서 큐에 한 번씩 삽입되고 제거되므로 V*O(1)로 O(V)의 시간이 걸린다. 각 정점이 큐에서 제거될 때 딱 한 번 해당 정점의 인접 리스트가 검색된다. 모든 정점의 인접리스트를 한 번씩 검색하는 것은 인접 리스트의 총 길이에 비례하므로 시간 복잡도는 O(E)가 된다. 처음 모든 정점의 속성을 초기화하는 데도 O(V)의 시간이 소모된다. 따라서 BFS를 수행하는 데 걸리는 총 시간은 O(V+E)가 된다.

---

최단 경로

정점 사이 모든 경로의 간선 개수 중 가장 작은 수를 최단 경로 거리라고 하며, 최단 경로거리를 갖는 정점 사이의 경로를 최단 경로라고 한다. 너비 우선 검색의 경우, 최단 경로 거리를 정확하게 계산한다. 간선의 가중치가 없는 경우 간선을 1로 생각한다.

---

보조정리 1

방향 또는 무방향 그래프에서 s를 임의의 정점이라 하자. 그러면 그래프 내의 간선 (u,v)에 대해 다음이 성립한다.

δ(s,v) ≤ δ(s,u) + 1

=> s에서 u로 도달할 수 있을 때와 도달할 수 없을 때를 구분지어 생각해보면 증명할 수 있다.

보조정리 2

우선 BFS를 통해 구한 거리 값이 δ(s,v)가 가질 수 있는 최대값이다.

=> 큐에 삽입될 때 계산되는 경로 값에 대해 귀납법을 사용하여 증명할 수 있다. 귀납법을 사용할 때 δ(s,v) ≤ δ(s,u) + 1를 활용할 수 있다. 귀납법을 통해 큐에 삽입될 때 정점의 거리 값이 해당 조건을 만족한다는 것을 보이면 정점의 거리 값은 큐에 들어갈 때 한 번만 계산된다는 점을 통해 모든 정점에 대해 귀납 가정이 계속 유지되면 따라서 위의 명제는 항상 참이라는 것을 알 수 있다.

보조정리 3

BFS를 수행하는 동안 큐에 삽입된 v1, v2, v3, ..., vr 정점에 대해서 i = 1, 2, 3, ..., r-1일 때 vr의 거리 ≤ v1의 거리 + 1 이고, vi의 거리 ≤ v(i+1)의 거리이다.

=> 귀납법을 사용하여 증명한다. 큐가 처음 s만 가지고 있을 때, 큐에 정점을 하나 삽입하거나 삭제할 때도 해당 정리가 성립한다는 것을 보임으로써 증명할 수 있다.

따름정리 3-1

BFS를 수행하는 도중에 vi가 vj보다 큐에 먼저 삽입되었다고 가정하면 vi의 거리 ≤ vj의 거리이다.

=> 보조정리 3과 큐에 한 번만 들어간다는 사실을 활용하면 증명할 수 있다.

정리 1(위의 모든 보조정리와 따름정리는 정리1을 위해 필요하다.)

어떤 그래프에서 BFS는 도달가능한 모든 정점을 찾고, 각 정점에 대해 최단 거리를 찾는다. 또한 s가 아닌 어떠한 정점까지의 s로부터의 최단 경로는 그 정점의 이전 탐색 정점까지의 s로부터의 경로와 그 정점과 해당 정점 사이의 간선으로 구성된 경로이다.

=> 귀류법을 활용해서 푼다. BFS를 수행했을 때 어떠한 정점에서는 최단 값이 아닌 거리가 구해졌다고 가정한다. 보조정리 1, 2을 활용하여 v와 s와 v 사이의 최단경로 위에 있는 u의 거리에 대한 식을 구한다. 큐에서 u를 제거할 때 v의 모든 상태에서 위의 식이 모순임을 보임으로써 모든 정점에서 최단 거리 값을 구함을 증명할 수 있다. (도달 가능한 정점에 대해서) (+ 도달이 불가능한 정점은 BFS거리와 최단거리가 모두 무한대이므로 성립함). 만약 도달가능한 정점이 BFS를 통해 모두 찾아지지 않는다면 그것은 위의 증명에서 모순을 발생시키므로 도달가능한 정점은 BFS를 통해 모두 찾아진다. 최단경로 증명 또한 위의 증명을 활용하면 자명해진다.

---

너비 우선 트리

직전원소 부분 그래프라고 하며, BFS로 탐색된 정점과 간선에 의해 구성된 그래프로 간선의 개수는 정점-1이므로 사실상 트리라고 할 수 있다. s에서 v까지 유일하며 최단인 경로를 갖는다.