Breadth First Search (너비 우선 탐색)
개요
BFS(Breadth First Search, 너비 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서부터 가까운 정점들을 먼저 탐색한 후, 차례대로 거리가 먼 정점들을 탐색하는 방식이다. BFS는 너비를 우선적으로 탐색하기 때문에, 최단 경로를 구할 때 유용하며 주로 큐(Queue)를 사용하여 구현된다.
BFS는 다음과 같은 문제에서 주로 사용된다:
•
최단 경로 탐색 (무가중치 그래프에서)
•
레벨 탐색 (트리 구조에서 각 노드의 깊이를 계산할 때)
•
연결 요소 찾기 (그래프의 모든 연결 요소를 탐색)
너비를 우선 탐색한다는 것의 의미
BFS에서 '너비를 우선 탐색한다'는 것은, 시작 정점으로부터 가까운 정점들을 먼저 탐색하고, 그 다음에 더 먼 정점들을 탐색한다는 의미이다. 이를 위해 BFS는 먼저 시작 정점을 큐에 넣고, 그 정점과 연결된 정점들을 차례대로 큐에 넣으면서 탐색을 진행한다.
BFS는 한 번 방문한 정점을 다시 방문하지 않기 때문에 중복된 경로를 피할 수 있다. 이는 주로 방문 여부를 기록하는 배열(혹은 리스트)을 통해 처리된다.
•
수도 코드
BFS(시작 정점 s):
큐 Q를 빈 상태로 초기화
시작 정점 s를 Q에 삽입
s를 방문 처리
while Q가 비어 있지 않으면:
정점 u = Q에서 꺼냄
u와 인접한 모든 정점 v에 대해:
만약 v를 방문하지 않았다면:
v를 Q에 삽입
v를 방문 처리
Plain Text
복사
BFS와 트리 구조
트리의 레벨 순회를 일반화한 것이 BFS이다.
예제
가령, 다음과 같은 그래프가 있다고 하자.
1 -- 2 -- 3
| |
4 -- 5
Plain Text
복사
위 그래프에서 1번 정점에서 BFS를 시작한다면, 큐에 들어가는 순서는 다음과 같다.
1.
시작 정점인 1을 큐에 삽입
2.
1과 인접한 2, 4가 큐에 추가됨
3.
2와 인접한 3, 5가 큐에 추가됨 (이미 4는 방문했으므로 제외)
4.
큐에서 3, 5를 차례대로 처리하며 탐색 종료
BFS 코드 (C++)
1.
인접 리스트 기반
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void BFS(int start, vector<vector<int>>& adjList, vector<bool>& visited) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " ";
for (int neighbor : adjList[current]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
int n = 6; // 노드 수
vector<vector<int>> adjList(n);
adjList[0] = {1, 3};
adjList[1] = {0, 2, 4};
adjList[2] = {1};
adjList[3] = {0, 4};
adjList[4] = {1, 3, 5};
adjList[5] = {4};
vector<bool> visited(n, false);
BFS(0, adjList, visited);
return 0;
}
C++
복사
2.
인접 행렬 기반
#include <iostream>
#include <queue>
using namespace std;
void BFS(int start, vector<vector<int>>& adjMatrix, vector<bool>& visited) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " ";
for (int i = 0; i < adjMatrix.size(); ++i) {
if (adjMatrix[current][i] == 1 && !visited[i]) {
q.push(i);
visited[i] = true;
}
}
}
}
int main() {
int n = 6; // 노드 수
vector<vector<int>> adjMatrix = {
{0, 1, 0, 1, 0, 0},
{1, 0, 1, 0, 1, 0},
{0, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 1, 0},
{0, 1, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 0}
};
vector<bool> visited(n, false);
BFS(0, adjMatrix, visited);
return 0;
}
C++
복사
BFS 코드 (Python)
1.
인접 리스트 기반
from collections import deque
def bfs(start, adj_list):
visited = [False] * len(adj_list)
queue = deque([start])
visited[start] = True
while queue:
current = queue.popleft()
print(current, end=' ')
for neighbor in adj_list[current]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
adj_list = [
[1, 3], # 0번 노드와 인접한 노드
[0, 2, 4], # 1번 노드와 인접한 노드
[1], # 2번 노드와 인접한 노드
[0, 4], # 3번 노드와 인접한 노드
[1, 3, 5], # 4번 노드와 인접한 노드
[4] # 5번 노드와 인접한 노드
]
bfs(0, adj_list)
Python
복사
2.
인접 행렬 기반
from collections import deque
def bfs(start, adj_matrix):
visited = [False] * len(adj_matrix)
queue = deque([start])
visited[start] = True
while queue:
current = queue.popleft()
print(current, end=' ')
for i in range(len(adj_matrix[current])):
if adj_matrix[current][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
adj_matrix = [
[0, 1, 0, 1, 0, 0], # 0번 노드와의 연결 상태
[1, 0, 1, 0, 1, 0], # 1번 노드와의 연결 상태
[0, 1, 0, 0, 0, 0], # 2번 노드와의 연결 상태
[1, 0, 0, 0, 1, 0], # 3번 노드와의 연결 상태
[0, 1, 0, 1, 0, 1], # 4번 노드와의 연결 상태
[0, 0, 0, 0, 1, 0] # 5번 노드와의 연결 상태
]
bfs(0, adj_matrix)
Python
복사
요약
•
BFS는 큐를 사용해 너비를 우선으로 탐색하며, 무가중치 그래프에서 최단 경로를 찾는 데 유용하다.
•
BFS는 주로 인접 리스트와 인접 행렬을 사용해 구현되며, 각 방식에 따라 다르게 접근할 수 있다.
•
BFS는 그래프의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(V + E)이며, 여기서 V는 정점의 수, E는 간선의 수를 의미한다.
참고로,
BFS는 최단경로의 문제를 푸는 알고리즘은 다익스트라 알고리즘 등과 이어진다.
REFERENCES
•
주우석, 2015, C/C++로 배우는 자료구조론, 한빛미디어
Written by Changyu Lee