너비 우선 탐색(BFS)이란?
너비 우선 탐색(BFS, Breadth-First Search)은 자식 정점을 방문하기 전에 먼저 인접한 이웃 정점들을 모두 방문하는 그래프 순회 알고리즘입니다. BFS는 탐색 과정에서 큐(Queue) 자료구조를 활용한다는 점이 특징입니다.
BFS의 동작 원리
BFS는 다음 세 가지 규칙에 따라 동작합니다.
- 인접한 미방문 정점을 방문하고, 방문 처리한 후 화면에 표시한 뒤 큐에 삽입(enqueue)합니다.
- 더 이상 방문하지 않은 인접 정점이 없다면, 큐의 맨 앞 정점을 제거(dequeue)합니다.
- 큐가 빌 때까지 위 두 규칙을 반복합니다.
BFS 순회 과정 시각화
아래 표를 통해 BFS 순회가 실제로 어떻게 진행되는지 단계별로 살펴보겠습니다.
| 단계 | 순회 상태 | 설명 |
|---|---|---|
| 1 |  | 큐를 초기화합니다. |
| 2 |  | 시작 노드 S를 방문하고 방문 처리(visited)합니다. |
| 3 |  | S의 인접 노드 중 미방문 노드를 찾습니다. 이 예제에는 세 개의 노드가 있지만 알파벳 순서대로 A를 선택해 방문 처리한 뒤 큐에 삽입합니다. |
| 4 |  | 다음으로 S의 미방문 인접 노드 B를 방문 처리하고 큐에 삽입합니다. |
| 5 |  | 이어서 S의 미방문 인접 노드 C를 방문 처리하고 큐에 삽입합니다. |
| 6 |  | 이제 S에는 더 이상 방문하지 않은 인접 노드가 없으므로, 큐에서 제거(dequeue)하여 다음 노드 A를 꺼냅니다. |
| 7 | | A의 인접 노드 중 미방문 노드 D를 찾아 방문 처리하고 큐에 삽입합니다. |
이 시점에서 더 이상 방문하지 않은(표시되지 않은) 노드는 남아 있지 않습니다. 하지만 알고리즘의 규칙에 따라 모든 노드를 확인할 때까지 계속 dequeue를 반복하며, 최종적으로 큐가 완전히 비면 프로그램은 종료됩니다.
JavaScript로 BFS 구현하기
그럼 이 알고리즘을 실제로 어떻게 JavaScript로 구현할 수 있는지 살펴보겠습니다.
코드 예제
BFS(node) {
// 큐를 생성하고 시작 노드를 추가합니다
let q = new Queue(this.nodes.length);
let explored = new Set();
q.enqueue(node);
// 첫 번째 노드를 탐색 완료(explored)로 표시합니다
add(node);
// 큐가 빌 때까지 반복합니다
while (!q.isEmpty()) {
let t = q.dequeue();
// 큐에서 꺼낸 모든 요소를 로그로 출력합니다
console.log(t);
// 1. edges 객체에서 현재 노드와 직접 연결된 노드를 찾습니다.
// 2. 이미 탐색된 노드는 필터링하여 제외합니다.
// 3. 아직 탐색하지 않은 각 노드를 explored로 표시하고 큐에 추가합니다.
this.edges[t]
.filter(n => !explored.has(n))
.forEach(n => {
explored.add(n);
q.enqueue(n);
});
}
}위 함수는 다음과 같이 테스트해 볼 수 있습니다.
테스트 예제
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");
g.BFS("A");실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
A C B D G E F
출력 결과를 보면 노드 A에서 시작해 인접한 노드들(C, B, D)을 먼저 모두 방문한 뒤, 그다음 깊이의 노드들(G, E, F)을 차례로 탐색하는 것을 확인할 수 있습니다. 이것이 바로 BFS가 "너비 우선"이라 불리는 이유입니다.