너비 우선 탐색(BFS)이란?
너비 우선 탐색(Breadth First Search, BFS)은 주어진 그래프의 모든 노드를 빠짐없이 방문하기 위해 사용되는 대표적인 그래프 순회(traversal) 알고리즘입니다. BFS는 시작 노드를 하나 선택한 뒤, 해당 노드에 인접한 모든 노드를 차례대로 방문합니다. 인접한 정점들을 모두 처리하고 나면 다음 정점으로 이동하여 같은 방식으로 그 정점의 인접 정점들을 다시 탐색합니다.
이러한 특성 덕분에 BFS는 시작점에서 가까운 노드부터 멀리 있는 노드 순서로 탐색하게 되며, 최단 경로 문제나 레벨(level) 단위 탐색에 널리 활용됩니다.
BFS의 핵심: 큐(Queue) 자료구조
BFS를 구현하려면 큐(Queue) 자료구조가 반드시 필요합니다. 동작 방식은 다음과 같습니다.
현재 노드와 인접한 모든 정점을 큐에 추가하고, 해당 정점들의 처리가 끝나면 큐에서 하나의 항목을 꺼내(dequeue) 그 정점을 기준으로 다시 탐색을 진행합니다. 이처럼 큐의 선입선출(FIFO) 특성 덕분에 가까운 노드부터 순서대로 방문할 수 있습니다.
또한 그래프에는 사이클(cycle)이 존재할 수 있으므로, 이미 방문한 노드를 다시 방문하지 않도록 각 노드의 방문 여부를 기록하는 배열을 사용해야 합니다.
입력 및 출력 예시
입력 – 그래프의 인접 행렬(Adjacency Matrix)
A B C D E F
A 0 1 1 1 0 0
B 1 0 0 1 1 0
C 1 0 0 1 0 1
D 1 1 1 0 1 1
E 0 1 0 1 0 1
F 0 0 1 1 1 0
출력 – BFS 순회 결과: B A D E C F
BFS 알고리즘 의사코드
bfs(vertices, start)
입력 – 정점 목록(vertices)과 시작 정점(start)
출력 – 그래프가 연결되어 있다면 모든 노드를 순회
Begin
빈 큐 que를 생성한다
처음에 모든 노드의 상태를 '미방문'으로 표시한다
시작 정점을 que에 삽입한다
que가 비어 있지 않은 동안 반복한다:
que에서 항목을 삭제하여 u에 저장한다
정점 u를 출력한다
u와 인접한 모든 정점 i에 대해 반복한다:
만약 vertices[i]가 미방문 상태라면
vertices[i]를 '임시 방문'으로 표시한다
정점 v를 큐에 삽입한다
표시를 종료한다
반복 종료
u를 '완전 방문' 상태로 표시한다
반복 종료
End
C++ 구현 예제
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다. 시작 정점은 B로 설정했습니다.
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
typedef struct node{
int val;
int state; // 방문 상태
}node;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void bfs(node *vert, node s){
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++){
vert[i].state = 0; // 미방문 상태로 초기화
}
vert[s.val].state = 1;// 시작 노드를 방문 처리
que.push(s); // 시작 노드를 큐에 삽입
while(!que.empty()){
u = que.front(); // 큐에서 제거하며 출력
que.pop();
cout << char(u.val+'A') << " ";
for(i = 0; i<NODE; i++){
if(graph[i][u.val]){
// 아직 방문하지 않은 노드인 경우
if(vert[i].state == 0){
vert[i].state = 1;
que.push(vert[i]);
}
}
}
u.state = 2;// 노드 u의 탐색 완료
}
}
int main(){
node vertices[NODE];
node start;
char s;
for(int i = 0; i<NODE; i++){
vertices[i].val = i;
}
s = 'B';// 시작 정점을 B로 지정
start.val = s-'A';
cout << "BFS Traversal: ";
bfs(vertices, start);
cout << endl;
}
실행 결과
BFS Traversal: B A D E C F
위 코드는 시작 정점 B에서 출발하여 인접한 노드들을 큐에 순서대로 삽입하고, 큐에서 하나씩 꺼내며 탐색을 이어갑니다. 그 결과 B → A → D → E → C → F 순서로 모든 정점을 방문하는 것을 확인할 수 있습니다.