[Algorithm] 너비 우선 탐색(Breadth-First Search)
너비 우선 탐색(Breadth-First Search)란?
BFS는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 가까운 정점부터 차례대로 탐색하는 방식입니다.
마치 물이 퍼져나가듯이, 현재 정점에 연결된 모든 정점을 먼저 방문하고, 그 다음에는 그 정점들에 연결된 정점을 방문하는 방식입니다.
(출처 : illinois.edu)
특징
- 최단 경로 탐색: 가중치가 없는 그래프에서 시작 정점부터 목표 정점까지의 최단 경로를 찾을 수 있습니다.
- 큐(Queue) 사용: 탐색 순서를 유지하기 위해 큐 자료구조를 사용합니다.
- 레벨 단위 탐색: 같은 “레벨”에 있는 정점들을 먼저 탐색합니다. (시작 정점과의 거리가 같은 정점들)
동작방식
- 시작 정점을 방문합니다.
- 시작 정점에 인접한 모든 정점을 방문합니다.
- 방문한 정점들에 인접한 아직 방문하지 않은 모든 정점을 방문합니다.
- 더 이상 방문할 정점이 없을 때까지 위 과정을 반복합니다.
DFS와의 비교
BFS는 깊이 우선 탐색(DFS)과 함께 대표적인 그래프 탐색 알고리즘입니다. 두 알고리즘은 탐색 방식에 차이가 있습니다.
- BFS: 너비 우선 탐색, 큐 사용, 최단 경로 탐색에 적합
- DFS: 깊이 우선 탐색, 스택 또는 재귀 사용, 모든 정점 방문에 적합
어떤 알고리즘을 사용할지는 문제의 특성에 따라 결정해야 합니다.
최단 경로를 찾아야 하는 경우에는 BFS가 적합하고, 모든 정점을 방문해야 하는 경우에는 DFS가 더 효율적일 수 있습니다.
장단점
장점
- 최단 경로 보장 (가중치가 없는 그래프): 시작 정점에서 목표 정점까지의 최단 경로를 찾을 수 있다는 것이 가장 큰 장점입니다. 이는 BFS가 레벨(시작 정점으로부터의 거리) 순으로 탐색하기 때문에, 목표 정점에 처음 도달했을 때 그 경로가 최단 경로임을 보장하기 때문입니다. 예를 들어, 지도에서 두 도시 사이의 최단 경로를 찾거나, 게임 맵에서 캐릭터가 목표 지점까지 가장 빠르게 이동하는 경로를 찾을 때 유용하게 사용됩니다.
- 구현이 비교적 간단: DFS(깊이 우선 탐색)에 비해 구현이 비교적 직관적이고 간단합니다. 큐(Queue)를 사용하여 탐색 순서를 관리하기 때문에, 코드의 흐름을 이해하기 쉽습니다.
- 레벨 단위 탐색: 그래프의 구조를 레벨 단위로 파악할 수 있습니다. 즉, 시작 정점으로부터 같은 거리에 있는 모든 정점을 한 번에 탐색할 수 있습니다. 이는 네트워크 브로드캐스팅이나 소셜 네트워크 분석 등에서 유용하게 활용될 수 있습니다. 예를 들어, 소셜 네트워크에서 특정 사용자의 2촌 인맥을 모두 찾을 때 BFS를 사용할 수 있습니다.
단점
- 메모리 사용량이 많을 수 있음: BFS는 큐를 사용하여 방문해야 할 정점들을 저장합니다. 따라서, 그래프가 크거나 분기 계수(branching factor, 한 정점에 연결된 다른 정점의 수)가 큰 경우, 큐에 저장해야 하는 정점의 수가 많아져 메모리 사용량이 급증할 수 있습니다. 특히, 그래프가 매우 넓고 깊이가 얕은 경우, DFS보다 훨씬 많은 메모리를 사용할 수 있습니다.
- 가중치 그래프에는 적합하지 않음: BFS는 가중치가 없는 그래프 또는 모든 간선의 가중치가 동일한 그래프에서 최단 경로를 찾는 데 효과적입니다. 간선에 가중치가 있는 그래프의 최단 경로를 찾기 위해서는 다익스트라(Dijkstra) 알고리즘과 같은 다른 알고리즘을 사용해야 합니다.
- 목표 정점이 깊은 곳에 있는 경우 비효율적일 수 있음: 만약 목표 정점이 그래프의 매우 깊은 곳에 위치하고 있다면, BFS는 넓은 부분을 먼저 탐색해야 하므로 불필요한 탐색을 많이 수행할 수 있습니다. 이러한 경우에는 DFS가 더 효율적일 수 있습니다.
예제
#include <iostream>
#include <vector>
#include <queue>
#include <list>
using namespace std;
class Graph {
private:
int numVertices;
vector<list<int>> adj;
public:
Graph(int vertices) : numVertices(vertices), adj(vertices) {}
void addEdge(int u, int v) {
adj[u].push_back(v); // 방향 그래프
// adj[v].push_back(u); // 무방향 그래프의 경우 추가
}
void BFS(int startVertex) {
vector<bool> visited(numVertices, false); // 방문 여부 저장
queue<int> q; // BFS에 사용할 큐
visited[startVertex] = true; // 시작 정점 방문 처리
q.push(startVertex); // 시작 정점을 큐에 넣음
while (!q.empty()) {
int currentVertex = q.front(); // 큐에서 정점 꺼내기
q.pop();
cout << currentVertex << " "; // 방문한 정점 출력
// 현재 정점에 인접한 정점들을 방문
for (int neighbor : adj[currentVertex]) {
if (!visited[neighbor]) { // 아직 방문하지 않은 정점인 경우
visited[neighbor] = true; // 방문 처리
q.push(neighbor); // 큐에 넣기
}
}
}
cout << endl;
}
};
int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
cout << "Starting BFS from vertex 0: ";
g.BFS(0); // 0번 정점에서 BFS 시작
return 0;
}