너비 우선 탐색(Breadth-First Search, BFS)는 깊이 우선 탐색과 마찬가지로 그래프의 정점들을 순회하는 알고리즘이다. 깊이 우선 탐색은 될 수 있는 한 끝까지 깊이 들어갔다가 되돌아 오는 반면, 너비 우선 탐색은 시작 정점에서 가까운 정점부터 방문하는 특성을 지닌다. 정확한 동작 방식은 다음과 같다.
- 시작 정점을 '방문함'으로 설정하고 큐에 삽입
- 큐에서 가장 앞에 있는 정점과 인접한 정점들을 방문 / 큐에서 가장 앞에 있는 정점 제거
- 그 정점들을 방문하고 큐에 삽입
- 모든 정점을 방문할 때까지 2~4를 반복
시각화하면 다음처럼 나타낼 수 있다.
1번 정점을 시작 정점이라고 할 때, 시작 정점과 연결되어 있는 2, 3, 4번 정점을 순서대로 방문한 다음 2번 정점에 연결된 정점, 3번 정점에 연결된 정점, 4번 정점에 연결된 정점... 순으로 방문하여 1-2-3-4-5-6-7-11-9-10 순으로 방문하게 된다.
BFS의 구현
인접 행렬로 그래프를 표현할 때는 다음과 같이 구현할 수 있다.
bool adj[MAX][MAX];
bool visited[MAX];
int n; // 정점의 수
void bfs(int v) {
queue<int> q;
q.push(v);
visited[v] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (adj[now][i] && !visited[i]) {
q.push(i);
visited[i] = 1;
}
}
}
}BFS의 시간 복잡도도 DFS와 크게 다를 것이 없다. 인접 행렬일 때는 인접한 정점을 확인하기 위해 $O(V)$ 시간이 걸리고, 그걸 $V$번 반복해야 하므로 총 시간 복잡도는 $O(V^2)$이다.
인접 리스트로 그래프를 표현할 때는 다음처럼 구현할 수 있다.
vector<int> adj[MAX];
bool visited[MAX];
void bfs(int v) {
queue<int> q;
q.push(v);
visited[v] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i < adj[now].size(); i++) {
int nxt = adj[now][i];
if (!visited[nxt]) {
q.push(nxt);
visited[nxt] = 1;
}
}
}
}인접 리스트로 구현했을 때의 시간 복잡도도 DFS를 인접 리스트에서 구현했을 때의 시간 복잡도와 같은 $O(V+E)$이다.
최단 거리 구하기
BFS는 시작 정점으로부터 거리가 가까운 정점 순으로 방문하기 때문에 간선에 가중치가 없는 그래프에서는 BFS를 통해 최단거리를 구할 수 있다.
어떤 정점을 방문할 때 이 정점은 시작 정점으로부터 최단 거리에 방문한다는 것이 보장되기 때문에, (현재 정점의 이전 정점 거리) + 1이 현재 정점과 시작 정점 사이의 최단 거리가 된다.
vector<int> adj[MAX];
bool visited[MAX];
int dist[MAX]; // 거리를 저장하는 배열: dist[n]은 시작 정점과 n번 정점 사이의 거리
void bfs(int v) {
queue<int> q;
q.push(v);
visited[v] = 1;
dist[v] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i < adj[now].size(); i++) {
int nxt = adj[now][i];
if (!visited[nxt]) {
q.push(nxt);
visited[nxt] = 1;
dist[nxt] = dist[now] + 1;
}
}
}
}