0. 서론
BFS는 그래프에서 가장 기본적이고 필수적인 탐색 알고리즘이다. BFS의 동작원리 때문에 BFS로 찾아진 모든 경로들은 항상 어떤 노드 v로 부터의 최단거리경로가 된다.
알고리즘의 시간복잡도는 \( O \left( n + m \right) \)인데, 이 때 n은 정점(vertices)의 개수, m은 간선(edges)의 개수이다. 그 이유는 BFS에서는 모든 정점과 노드들을 딱 한번씩만 방문하기 때문이다.
1. BFS(Breadth First Search) 란?
BFS 알고리즘은 입력으로 unweighted graph와, source vertex s, 총 두개를 받는다. 입력으로 주어지는 그래프는 directed graph, undirected graph 둘 다 가능하다.
아래에 BFS가 어떻게 작동하는지 설명되어 있다.
마치 시작노드로 부터 불이 번지 듯 탐색이 이루어진다고 생각하면 조금 이해가 쉬울지도 모르겠다.
2. BFS 구현
위에 설명한 BFS를 C++로 구현함.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 10; // number of nodes.
vector<int> p; // 이 배열은 최단거리경로를 구하기 위해 필요함. parent.
vector<int> adj[N]; // adjacency list representation.
bool visited[N];
queue<int> q; // nodes to be processed.
int d[N];
void bfs(int s) { // s는 시작 노드이다.
// 반복문을 돌리기 전에 시작 노드를 queue에 넣어주고 방문 완료 처리해준다.
visited[s] = true;
q.push(s);
// 시작 노드의 거리는 0.
d[s] = 0;
p[s] = -1;
// 반복문은 q가 비어있을 때까지 돌아간다.
while(!q.empty()) {
int v = q.front();
q.pop();
// 여기서 노드 v를 출력하면 BFS로 탐색한 결과를 출력하게 된다.
// v에 인접한 '모든' 노드를 처리해준다. BFS 작동원리.
for(auto u : adj[v]) {
if(visited[u]) continue;
visited[u] = true;
q.push(u);
d[u] = d[v] + 1;
p[u] = v;
}
}
}
BFS 알고리즘 구현을 위해 네 개의 공간이 필요하다.
1. 입력으로 받을 graph를 저장할 공간: 인접 리스트로 표현된 그래프 adj
2. 노드를 방문했는지 안했는지 저장할 공간: boolean 타입의 배열 visited
3. 처리되어야 할 vertices다 담겨있는 공간: queue q
4. 시작노드로부터의 거리를 저장할 공간: 배열 d
처음에는, 시작 노드 s를 queue에 push해준다. 그리고 visited[v] = true로 해줘서 방문했다고 처리해준다. 시작노드의 거리는 0으로 설정해준다. 이후에 queue 가 빌 때 까지 반복문을 돌리게 되면 탐색이 완료된다.
3. 최단거리경로 구하기
맨위 서론에서 BFS로 최단거리경로를 구할 수 있다고 적어놓았었다. 위에 구현코드에서 p 배열을 여기서 활용한다.
아래 코드를 실행하기 전 반드시 먼저 BFS가 한번 시행되어야 정상적으로 작동한다.
void findShortestPath(int u) {
// u 노드를 방문한적이 없다면 시작노드로 부터 경로가 존재하지 않는다.
if(!visited[u]) {
cout << "No Path\n";
return;
}
vector<int> path;
for(int v = u; v != -1; v = p[v])
path.push_back(v);
reverse(path.begin(), path.end());
cout << "Path: ";
for(auto e : path)
cout << e << ' ';
cout << endl;
}
출처: cses.fi, cp-algorithms.com
댓글