그래프 알고리즘 II: 너비 우선 탐색 (BFS)
너비 우선 탐색 (BFS)
지난 시간에 다룬 DFS에 이어, 너비 우선 탐색 (Breadth First Search, BFS)은 그래프를 탐색하는 또 다른 중요한 알고리즘이다. BFS는 시작 정점에서부터 인접한 모든 정점을 먼저 방문하고, 그 다음에 그 인접한 정점들의 인접한 정점들을 방문하는 식으로, 마치 잔잔한 물에 돌을 던졌을 때 파동이 퍼져나가는 모양처럼 그래프를 탐색한다.
BFS의 작동 방식
BFS는 큐(queue)를 사용하여 방문할 정점을 저장한다. 시작 정점을 큐에 넣고, 큐에서 정점을 하나씩 꺼내면서 인접한 정점들을 방문한다. 방문한 정점은 큐에 넣고, 이미 방문한 정점은 다시 방문하지 않는다. 이때 큐를 사용하는 이유는 어떤 정점들 방문했는지 검사함으로써 무한루프를 방지하기 위함이다.
BFS의 의사 코드 (Pseudocode)
BFS(v):
Set L{i} = [] for i=1,..., n
L0 = {w}, where w is the start node
for i = 0,...,n-1:
for u in L{i}:
for each v which is a neighbor of u:
If V hasn't yet visited:
mark v as visited, and put it in L{i+1}BFS는 각 정점과 간선을 최대 한 번씩 방문하기 때문에, 시간 복잡도는 O(n + m)이다. 여기서 n은 정점의 수, m은 간선의 수이다.
BFS 트리 (BFS Tree)
 |
| BFS tree |
DFS와 마찬가지로 BFS도 탐색 과정에서 BFS 트리를 구성할 수 있다. BFS 트리는 루트가 시작 정점이고, 각 정점의 자식은 BFS 탐색 순서대로 방문한 정점들이다. BFS 트리는 그래프의 최단 경로를 찾는 데 유용하게 사용된다.
BFS의 활용: 최단 경로 찾기
BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용될 수 있다. BFS 트리에서 루트에서 특정 정점까지의 경로가 최단 경로가 된다.
예를 들어, 다음 그래프에서 정점 w에서 정점 v까지의 최단 경로를 찾는다고 가정하자.
 |
| shortest path example |
BFS를 수행하면 다음과 같은 BFS 트리가 생성된다.
 |
| BFS result |
BFS 트리에서 정점 w에서 정점 v까지의 경로는 3 step으로 갈 수 있다. 이 경로가 정점 w에서 정점 v까지의 최단 경로가 된다. 만약 w에서 v가 reachable하지 않다면 거리는 무한히 발산한다.
BFS를 이용하여 최단 경로를 찾는 시간 복잡도는 \(O(m)\)이다.
+) \(O(n+m)\)이 아닌 이유는 최단 경로를 찾는 상황은 보통 복잡한 경로인, 즉 간선이 많은 dense한 graph이므로 \(O(n+m)\)를 \(O(m)\)과 같이 표현할 수 있다.
BFS의 활용: 이분 그래프 판별
이분 그래프 (Bipartite Graph)는 정점을 두 그룹으로 나눌 수 있고, 모든 간선이 두 그룹 사이에만 존재하는 그래프이다. BFS를 사용하여 그래프가 이분 그래프인지 판별할 수 있다.
 |
| bipartite |
이분 그래프 판별 방법
BFS 트리의 각 레벨에 번갈아 색을 칠한다. 만약 인접한 두 정점이 같은 색으로 칠해진다면, 그래프는 이분 그래프가 아니다.
 |
| finding bipartite using BFS |
예를 들어, 다음 그래프는 이분 그래프가 아니다.
 |
| bipartite-ness |
그림과 같이 BFS 트리의 레벨 2에 있는 노란색 정점에서 다음 레벨로 나아갈 때, 빨간색으로 칠해야 하지만 같은 색으로 칠해져 있다. 따라서 이 그래프는 이분 그래프가 아니다.
이분 그래프 판별의 증명
BFS를 사용하여 이분 그래프를 판별하는 방법은 다음과 같이 증명할 수 있다.
- BFS 트리에서 인접한 두 정점은 항상 다른 레벨에 있다.
- BFS 트리의 각 레벨에 번갈아 색을 칠하면, 인접한 두 정점은 항상 다른 색으로 칠해진다.
- 만약 인접한 두 정점이 같은 색으로 칠해진다면, BFS 트리의 레벨에 모순이 발생한다.
- 따라서 BFS를 사용하여 이분 그래프를 판별할 수 있다.
마치며
이번 포스팅에서는 너비 우선 탐색 (BFS)에 대해 알아보았다. BFS는 그래프 탐색, 최단 경로 찾기, 이분 그래프 판별 등 다양한 문제를 해결하는 데 사용되는 중요한 알고리즘이다. 다음 포스팅에서는 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘에 대해 알아보도록 하겠다.
추천글:
[알고리즘] Graph algorithm - Depth First Search, Topological ordering
(https://hyeondev.blogspot.com/2024/10/graph-algorithm-depth-first-search.html)
