너비 우선 탐색(Breadth First Search, BFS)은 각 정점을 방문할 때마다 모든 인접 정점들을 검사합니다. 이 중 처음 보는 정점을 발견하면 이 정점을 방문 예정이라고 기록해 둔 뒤, 별도의 위치에 저장합니다. 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문하게 됩니다. 따라서 너비 우선 탐색의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정됩니다.
이를 구현하는 간단한 방법은, 목록에 먼저 넣은 정점을 항상 먼저 꺼내는 것입니다. 시작점에서 멀리 있는 정점일수록 나중에 목록에 먼저 넣은 정점을 항상 먼저 꺼내는 것입니다. 시작점에서 멀리 있는 정점일수록 나중에 목록에 추가되기 때문입니다. 따라서 정점 목록으로 큐를 사용하면 너비 우선 탐색의 조건을 만족시킬 수 있습니다.
// 그래프의 인접 리스트 표현
vector<vector<int> ad;
// start에서 시작해 그래프를 너비 우선 탐색하고 각 정점의 방문 순서를 반환한다.
vector<int> bfs(int start) {
// 각 정점의 방문 여부
vector<bool> discovered(adj.size(), false);
// 방문할 정점 목록을 유지하는 큐
queue<int> q;
// 정점의 방문 순서
vector<int> order;
discovered[start] = true;
q.push(start);
while (!q.empty()) {
int here = q.front();
q.pop();
// here를 방문한다.
order.push_back(here);
// 모든 인접한 정점을 검사한다.
for (int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i];
// 처음 보는 정점이면 방문 목록에 집어넣는다.
if (!discovered[there]) {
q.push(there);
discovered[there] = true;
}
}
}
return order;
}
discovered[]는 각 정점의 발견 여부를 저장한다. 깊이 우선 탐색과는 달리 너비 우선 탐색에서는 발견과 방문이 같지 않습니다. 따라서 모든 정점은 다음과 같은 세 개의 상태를 순서대로 거쳐 가게 됩니다.
- 아직 발견되지 않은 상태
- 발견되었지만 아직 방문되지는 않은 상태(이 상태에 있는 정점들의 목록은 큐에 저장되어 있습니다)
- 방문된 상태
시간복잡도
너비 우선 탐색의 시간 복잡도는 깊이 우선 탐색과 다를 것이 없습니다. 모든 정점을 한 번씩 방문하며, 정점을 방문할 때마다 인접한 모든 간선을 검사하기 때문이지요. 따라서, 인접 리스트로 구현된 경우에는 O(|V|+|E|), 인접 행렬로 구현했을 경우 O(|V|^2)의 시간 복잡도를 갖게 됩니다.
너비 우선 탐색과 최단 거리
그래프의 구조에 관련된 다양한 문제를 푸는 데 사용되는 깊이 우선 탐색과 달리, 너비 우선 탐색은 대개 딱 하나의 용도로 사용됩니다. 바로 그래프에서의 최단 경로 문제 를 푸는 것입니다. 최단 경로 문제는 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾는 문제로, 그래프 이론의 가장 고전적인 문제 중 하나입니다.
너비 우선 탐색 알고리즘을 간단하게 변경해 모든 정점에 대해 시작점으로부터의 거리 distance[]를 계산하도록 할 수 있습니다.
// start에서 시작해 그래프를 너비 우선 탐색하고 시작점부터 각 정점까지의
// 최단 거리와 너비 우선 탐색 스패닝 트리를 계산한다.
// distance[i] = start로부터 i까지의 최단 거리
// parent[i] = 너비 우선 탐색 스패닝 트리에서 i의 부모의 번호. 루트인 경우 자신의 번호
void bfs2(int start, vector<int>& distance, vector<int>& parent) {
distance = vector<int>(adj.size(), -1);
parent = vector<int>(adj.size(), -1);
queue<int> q; // 방문할 정점 목록을 유지하는 큐
distance[start] = 0;
parent[start] = start;
q.push(start);
while (!q.empty()) {
int here = q.front();
q.pop();
// here의 모든 인접한 정점을 검사한다.
for (int i = 0; i < adj[here].size(); ++i) {
int there = adj[here][i];
// 처음 보는 정점이면 방문 목록에 집어넣는다.
if (distance[there] == -1) {
q.push(there);
distance[there] = distance[here] + 1;
parent[there] = here;
}
}
}
}
// v로부터 시작점까지의 최단 경로를 계산한다.
vector<int> shortestPath(int v, const vector<int>& parent) {
vector<int> path(1, v);
while (parent[v] != v) {
v = parent[v];
path.push_back(v);
}
reverse(path.begin(), path.end());
return path;
}
- bfs2() = 각 정점까지의 최단 거리와 너비 우선 탐색 스패닝 트리를 계산
- shortestPath() = 너비 우선 탐색 스패닝 트리를 입력받아 실제 최단 경로를 계산
각 정점으로부터 트리의 루트인 시작점으로 가는 경로가 실제 그래프 상에서의 최단 경로임을 알 수 있습니다. 시작점으로부터의 최단 경로는 너비 우선 탐색 스패닝 트리에서 루트로 가는 경로이므로, 각 정점이 부모의 번호를 갖고 있게 하면 쉽게 최단 경로를 계산할 수 있습니다.