너비 우선 탐색
출발점에서 가까운 거리 층부터 큐에 담아 방문하는 너비 우선 탐색(BFS)의 파면 불변식과 무가중 그래프 최단 간선 수 계산을 살펴본다.
· 마지막 업데이트: 2026-11-07 · 7 min read
개요
너비 우선 탐색(Breadth-first search, BFS)은 출발점에서 간선 하나로 닿는 정점들을 모두 방문한 뒤, 간선 두 개로 닿는 정점들로 넓혀 가는 그래프 탐색 방법이다. 지하철 노선도에서 한 번의 이동으로 갈 수 있는 역을 전부 확인한 다음에야 두 정거장 거리 역을 살피는 방식과 같아서, 모든 간선의 비용이 같을 때 처음 발견한 경로가 곧 최소 간선 경로가 된다.
연혁
Edward F. Moore는 1959년 미로 최단 탈출 경로를 찾는 논문 「The Shortest Path Through a Maze」에서 출발점으로부터 거리 순서로 표식을 넓혀 가는 탐색을 제안했다.1 이어 1961년 C. Y. Lee는 「An Algorithm for Path Connections and Its Applications」에서 Moore의 방법을 인용하며, 같은 거리의 격자점이 파면(wavefront)처럼 퍼져 나가는 성질을 인쇄회로기판(PCB) 자동 배선 문제에 적용했다.2 이와 별개로 Konrad Zuse도 1945년 작성한 *Plankalkül* 원고에서 그래프 연결 성분을 번호 매기는 동등한 절차를 기록했으나, 당대에는 출판되지 못했다.
선입선출 큐와 2계층 단조성
선입선출(FIFO) 큐는 먼저 들어온 정점을 먼저 꺼낸다. 출발점 에서 거리 인 정점 를 큐 뒤에 넣고, 이후 를 꺼내며 발견한 거리 인 정점 를 큐에 넣으면 는 반드시 뒤에 자리한다. 따라서 큐에는 언제나 최대 두 개의 인접한 거리 층(와 )만 공존하며, 앞선 거리 층이 모두 빠져나간 뒤에야 다음 층이 꺼내진다.
방문 표시는 정점을 큐에서 꺼낼 때가 아니라 큐에 넣는(enqueue) 순간에 기록해야 한다. 아래 그림에서 와 는 둘 다 로 향하는 간선을 가진다. 만약 큐에서 꺼낼 때 방문 표시를 한다면 의 이웃을 훑을 때 이미 큐에 들어간 를 에서 또 큐에 넣어 중복 방문과 메모리 팽창이 일어난다. 넣는 즉시 거리를 기록하면 자기 간선(self-loop)이나 순환(cycle)이 있어도 정점마다 큐에 정확히 한 번만 들어간다.
실행 예제
정점 A부터 E까지를 인덱스 0..4로 두고 인접 리스트로 표현하자. B와 C가 모두 D를 가리키는 구조여서 중복 발견 방지와 거리 층 계산을 함께 확인할 수 있다. 출발점과 모든 이웃 인덱스는 0..graph.length-1 범위 안에 있어야 한다.
function breadthFirst(graph: readonly (readonly number[])[], start: number) {
const distance = new Array<number>(graph.length).fill(-1);
const order: number[] = [];
const queue = [start];
distance[start] = 0;
for (let head = 0; head < queue.length; head++) {
const from = queue[head]!;
order.push(from);
for (const to of graph[from]!) {
if (distance[to] !== -1) continue;
// 큐에서 꺼낼 때가 아니라 큐에 넣는 순간 거리를 기록해 중복 삽입을 막는다.
distance[to] = distance[from]! + 1;
queue.push(to);
}
}
return { order, distance };
}
const names = ['A', 'B', 'C', 'D', 'E'];
const graph = [[1, 2], [3], [3, 4], [], []];
const result = breadthFirst(graph, 0);
console.log(result.order.map(index => names[index]).join(','));
console.log(result.distance.join(','));실행 결과:
A,B,C,D,E
0,1,1,2,2A에서 한 간선 거리인 B·C가 먼저 처리되고, 두 간선 거리인 D·E가 뒤따른다. 도달할 수 없는 정점은 초기값 -1로 남는다. JavaScript 배열에서 queue.shift()를 반복 호출하면 남은 원소를 매번 앞으로 당기느라 큐 조작만 이 될 수 있으므로, 여기서는 읽기 인덱스 head만 한 칸씩 전진시켜 디큐를 유지했다.
C++ 예제
C++에서는 std::queue<int>(기본 컨테이너 std::deque<int>)를 써도 되지만, 정점 수가 정해진 그래프에서는 std::vector<int>와 읽기 인덱스 head를 조합하면 연속된 메모리 블록 하나에서 캐시 친화적으로 큐를 순회할 수 있다.
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>
struct BfsResult {
std::vector<int> order;
std::vector<int> distance;
};
BfsResult breadthFirst(const std::vector<std::vector<int>>& graph, int start) {
std::vector<int> distance(graph.size(), -1);
std::vector<int> order;
std::vector<int> queue{start};
distance[start] = 0;
for (std::size_t head = 0; head < queue.size(); ++head) {
int from = queue[head];
order.push_back(from);
for (int to : graph[from]) {
if (distance[to] != -1) continue;
// 큐에 넣는 순간 거리를 기록해 중복 삽입을 막는다.
distance[to] = distance[from] + 1;
queue.push_back(to);
}
}
return {std::move(order), std::move(distance)};
}
int main() {
const char names[] = {'A', 'B', 'C', 'D', 'E'};
const std::vector<std::vector<int>> graph{{1, 2}, {3}, {3, 4}, {}, {}};
const auto result = breadthFirst(graph, 0);
for (std::size_t i = 0; i < result.order.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << names[result.order[i]];
}
std::cout << '\n';
for (std::size_t i = 0; i < result.distance.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << result.distance[i];
}
std::cout << '\n';
return 0;
}실행 결과:
A,B,C,D,E
0,1,1,2,2비용과 적용 범위
정점 수를 , 간선 수를 라 할 때, 각 정점은 큐에 최대 한 번 들어가고 그 정점의 인접 리스트도 한 번만 훑으므로 시간 복잡도는 , 거리 배열과 큐가 쓰는 보조 공간 복잡도는 다.
BFS는 모든 간선의 가중치가 동일할 때만 최단 거리를 보장한다. 간선 가중치가 과 로만 이루어진 경우에는 양쪽 끝에서 넣고 빼는 덱(deque)을 쓰는 0-1 BFS로 에 풀 수 있고, 일반 비음수 가중치 그래프에서는 누적 비용 순으로 정점을 꺼내는 다익스트라 알고리즘을 사용해야 한다. 반대로 한 갈래를 끝까지 파고들며 순환 여부나 강연결 요소를 분석할 때는 깊이 우선 탐색이 알맞다.
같이 보기
각주
- Edward F. Moore, “The Shortest Path Through a Maze,” Proceedings of an International Symposium on the Theory of Switching (1957), Part II, Harvard University Press, 1959, pp.285–292. ↩
- C. Y. Lee, “An Algorithm for Path Connections and Its Applications,” IRE Transactions on Electronic Computers EC-10(3), 1961, pp.346–365. 서론 및 §VI. 원문, DOI. ↩