너비 우선 탐색

수치해석 소프트웨어 마지막 수정: 2026-08-31 04:14:26

1. 개요[편집]

너비 우선 탐색 Breadth-first search, BFS
대상	유향·무향 그래프 $G=(V,E)$, 시작점 $s$
자료구조	FIFO 큐 (DFS 는 스택)
복잡도	$O(V+E)$ (인접 리스트 기준)
추가 공간	$O(V)$ — 최악의 프런티어가 $\Theta(V)$
핵심 보장	무가중 그래프 최단경로 $d[v]=\delta(s,v)$
변종	0-1 BFS · 다중 소스 · 양방향 · 방향 최적화
수치해석 쪽 얼굴	커스힐-맥키 순서화 · 연결성 판정 · 웨이브프론트

너비 우선 탐색(breadth-first search, BFS)은 시작 정점에서 가까운 순서대로 그래프를 층층이 훑는 순회 전략이다. 시작점을 큐에 넣고, 큐에서 하나 꺼내 그 이웃 중 아직 안 본 것을 전부 큐 뒤에 넣는 것을 반복한다. 구현은 깊이 우선 탐색의 스택을 큐로 바꾼 것뿐인데, 그 한 글자 차이가 알고리즘의 성격을 통째로 바꾼다.

BFS 가 특별한 이유는 순회 순서가 거리 순서와 정확히 일치한다는 것이다. 간선 가중치가 전부 같은 그래프에서 BFS 가 정점 $v$ 를 처음 만나는 시점의 층 번호는 그냥 “먼저 만난 경로”가 아니라 증명 가능한 최단경로 길이다. 이 보장 하나 때문에 BFS 는 순회 도구가 아니라 최단경로 알고리즘의 원형으로 취급되며, 가중치가 붙는 순간 다익스트라 알고리즘으로, 목적지를 아는 순간 A* 알고리즘으로, 연속체로 넘어가는 순간 고속 행진법으로 확장된다. 셋 다 “가장 가까운 것부터 확정한다”는 BFS 의 뼈대를 물려받았다.

시뮬레이션 쪽에서 BFS 는 길찾기 말고도 조용히 여러 곳에 박혀 있다. 메시가 몇 조각인지 세는 것, 강성행렬의 대역폭을 줄이는 순서화, 격자 위의 거리장, 전부 BFS 다.

2. 큐 하나로 최단경로가 나오는 이유[편집]

$s$ 를 층 0 으로 두고, 층 $k$ 의 정점에서 처음 닿는 미방문 정점을 층 $k+1$ 로 매긴다.

d[*] = ∞;  d[s] = 0;  Q = [s]
while Q not empty:
    u = Q.pop_front()
    for each edge (u,v):
        if d[v] == ∞:
            d[v] = d[u] + 1;  parent[v] = u;  Q.push_back(v)

정점은 큐에 정확히 한 번 들어가고, 들어간 정점마다 인접 리스트를 한 번 훑으므로 총 비용은 $O(V+E)$ 다. 무향그래프면 간선을 양쪽에서 한 번씩 보므로 $\Theta(V+2E)$ .

최적성 $d[v]=\delta(s,v)$ 의 증명은 두 조각으로 나뉜다. 여기서 $\delta(s,v)$ 는 간선 수로 잰 진짜 최단거리다.

(1) 큐 단조성 보조정리. 실행 중 어느 순간에도 큐가 $\langle v_1,\dots,v_r\rangle$ 이라면 $d[v_r] \le d[v_1]+1$ 이고 $d[v_i] \le d[v_{i+1}]$ 이다. 즉 큐에는 많아야 두 종류의 거리값만 들어 있고, 그 둘은 1 차이다. 큐 연산 횟수에 대한 귀납으로 증명된다 — 앞에서 꺼내면 최솟값이 커지고, 뒤에 넣는 값은 방금 꺼낸 값 +1 이다.

(2) 귀류법. $d[v] > \delta(s,v)$ 인 정점이 있다고 하고, 그중 $\delta(s,v)$ 가 최소인 것을 $v$ 라 하자. 최단경로에서 $v$ 의 직전 정점 $u$ 는 $\delta(s,u)=\delta(s,v)-1$ 이므로 최소성에 의해 $d[u]=\delta(s,u)$ 다. 이제 $u$ 를 큐에서 꺼내는 순간 $v$ 의 상태를 보면,

아직 미방문이면 그 자리에서 $d[v]=d[u]+1=\delta(s,v)$ — 가정에 모순.
이미 방문됐다면 어떤 $w$ 가 $u$ 보다 먼저 나오면서 $v$ 를 넣은 것이고, 단조성에 의해 $d[w] \le d[u]$ 이므로 $d[v]=d[w]+1 \le \delta(s,v)$ — 역시 모순.

따라서 그런 $v$ 는 없다. d[v] 를 큐에 넣는 시점에 확정하는 것이 이 증명의 핵심이다. 꺼내는 시점에 갱신하도록 코드를 고치면 같은 정점이 여러 번 큐에 들어가면서 복잡도가 무너진다.¹

여기서 부수적으로 무향그래프의 모든 간선은 같은 층을 잇거나 인접한 두 층을 잇는다(층 차이 $\ge 2$ 인 간선은 최단거리 정의에 모순)는 사실이 나온다. 그래서 “같은 층을 잇는 간선이 하나라도 있는가”가 곧 홀수 사이클의 존재이고, BFS 한 번으로 이분그래프 판정이 끝난다.

3. DFS 와의 대조[편집]

두 순회의 차이를 한 표에 몰아 둔다. 자세한 쪽은 깊이 우선 탐색 문서로 넘긴다.

항목	BFS	DFS
자료구조	FIFO 큐	LIFO 스택(대개 재귀)
최악 추가 메모리	프런티어 크기, 격자에서 $\Theta(\sqrt{V})$ · 트리에서 $\Theta(b^d)$	경로 길이 $O(V)$
무가중 최단경로	보장	없음
남기는 부산물	층 번호, BFS 트리	발견·종료 시각, 간선 4분류
대표 응용	최단경로, 연결성, 순서화, 거리장	위상 정렬, SCC, 단절점, 백트래킹
병렬화	레벨 동기식으로 자연스럽게	사전식 DFS 는 P-완전, 사실상 순차
해공간 탐색	프런티어가 지수로 폭발	메모리가 깊이에만 비례

마지막 줄이 실무에서 제일 자주 물린다. 그래프가 미리 존재하지 않고 탐색하면서 생성되는 문제(퍼즐, 조합 탐색)에서 BFS 는 “최단 해를 준다”는 매력적인 보장을 들고 오지만 프런티어 메모리로 먼저 죽는다. 그래서 그쪽 동네는 백트래킹과 반복 깊이증가를 쓴다.

4. 실전에서 쓰는 네 가지 변형[편집]

다중 소스 BFS. 큐를 시작점 하나가 아니라 소스 집합 전체로 초기화하고 그들 모두 $d=0$ 을 준다. 그러면 각 정점의 $d$ 는 가장 가까운 소스까지의 거리가 된다. 가상의 초정점을 만들어 모든 소스에 0-간선을 붙인 것과 같으므로 정당성은 그대로. 소스마다 BFS 를 $k$ 번 돌리면 $O(k(V+E))$ 인 것이 한 번의 $O(V+E)$ 로 줄어든다. 격자에서 “가장 가까운 장애물까지의 거리장”, “가장 가까운 시드의 라벨”(= 이산 보로노이 다이어그램)을 뽑을 때 국룰이다.

0-1 BFS. 간선 가중치가 0 또는 1 뿐이면 힙이 필요 없다. 큐 대신 덱(deque)을 쓰고, 가중치 0 간선으로 완화한 정점은 push_front, 1 간선은 push_back 한다. 덱 안에 두 종류의 거리값만 존재한다는 단조성이 그대로 유지되므로 라벨 설정이 성립하고, 비용은 $O(V+E)$ — 다익스트라 알고리즘의 $O(E\log V)$ 를 로그만큼 이긴다. 가중치가 작은 정수 $0..C$ 범위면 버킷 큐를 쓰는 다이얼(Dial) 알고리즘으로 $O(E+VC)$ 까지 일반화된다. 격자에 “방향 전환 비용 1, 직진 0” 같은 규칙을 얹는 문제에서 곧바로 써먹는다.

양방향 BFS. 출발점과 도착점에서 동시에 BFS 를 키워 중간에서 만나게 한다. 분기 계수 $b$ , 답 깊이 $d$ 인 그래프에서 $O(b^d)$ 가 $O(2b^{d/2})$ 로 줄어들며, 이건 상수 배가 아니라 지수의 절반이라 체감이 다르다. 함정이 하나 있는데, 한 레벨을 완전히 펼친 뒤에 교집합을 검사해야 한다. 정점 하나 만들 때마다 검사해서 즉시 반환하면 최적보다 1 긴 경로를 내놓는 경우가 생긴다. 두 프런티어 중 작은 쪽을 확장하는 것도 표준 요령이다.

방향 최적화 BFS. 대규모 소셜 그래프처럼 차수 분포가 두꺼운 그래프에서는 프런티어가 폭발하는 중간 레벨에 “위에서 아래로” 훑는 것이 낭비다. 이때 방향을 뒤집어 미방문 정점이 자기 이웃 중 프런티어에 있는 것을 찾는 바텀업 방식으로 전환하면, 이웃 하나만 찾아도 즉시 멈출 수 있어 간선 검사량이 크게 줄어든다. 프런티어 크기를 보고 톱다운/바텀업을 매 레벨 전환하는 이 하이브리드가 Graph500 랭킹의 판을 바꿨다.²

5. 커스힐-맥키 — 레벨 집합이 곧 순서화[편집]

BFS 가 수치해석 코드 깊숙이 박혀 있는 대표적인 자리가 행렬 대역폭 축소다. 대칭 희소행렬 $A$ 의 대역폭을 $\beta = \max\{\,|i-j| : a_{ij} \ne 0\,\}$ 로 정의하면, 대역 촐레스키 분해의 비용은 $O(n\beta^2)$ 이고 저장량은 $O(n\beta)$ 다. 즉 대역폭을 반으로 줄이면 연산이 4분의 1이 된다. 그런데 $\beta$ 는 행렬 자체의 성질이 아니라 번호 매기기의 성질이다. 같은 유한요소법 메시라도 절점 번호를 어떻게 붙였느냐에 따라 강성행렬이 예쁜 띠가 되기도 하고 온 사방에 점이 흩뿌려지기도 한다.

커스힐-맥키(Cuthill–McKee, 1969) 순서화는 이 문제에 BFS 를 그대로 갖다 붙인다.

편심도가 큰 정점(유사 주변 정점, pseudo-peripheral vertex)을 시작점으로 고른다. 아무 정점에서 BFS 를 돌려 가장 먼 층의 정점으로 옮겨가는 더블 스윕을 몇 번 반복하는 것이 표준 휴리스틱이다.
BFS 를 돌린다. 정점을 레벨 집합 순서대로 번호 매긴다.
같은 레벨 안에서는 차수 오름차순으로 정렬해 번호를 준다.

BFS 레벨 집합을 쓰는 이유는 앞 절의 사실 그대로다 — 간선은 같은 레벨이나 인접 레벨만 잇는다. 그러니 레벨 순서로 번호를 매기면 어떤 간선도 레벨 두 개 폭 이상으로 뛸 수 없고, 대역폭이 자동으로 “가장 두꺼운 두 인접 레벨의 크기” 언저리에 묶인다. 좁고 긴 도메인일수록 레벨이 얇아 효과가 크다.

실무에서 쓰는 것은 이 순서를 뒤집은 역커스힐-맥키(RCM)다. 순서를 뒤집어도 대역폭 $\beta$ 자체는 변하지 않지만, 프로파일(각 행에서 첫 비영 원소까지의 거리 합, envelope)은 절대 늘지 않고 대개 확 줄어든다는 것이 조지(A. George, 1971)의 관찰이었다.³ 프로파일 기반 스카이라인 솔버의 비용이 곧 프로파일이므로 공짜로 얻는 이득이다.

물론 대역폭 최소화 자체는 NP-난해라 RCM 은 어디까지나 휴리스틱이다. 그리고 요즘 대규모 희소행렬 직접 솔버는 대역이 아니라 채움현상을 줄이는 쪽(중첩 절단, 최소 차수)을 쓴다 — 그쪽은 오히려 분할 정복과 그래프 분할의 세계다. 그래도 RCM 은 반복법의 캐시 지역성을 올리고 불완전 LU 분해 전처리자의 품질을 바꾸기 때문에 여전히 기본 옵션으로 살아 있다.

6. 격자·메시 위의 BFS[편집]

연결성 판정. 메시 생성 결과에 떠 있는 조각, 고아 절점, 닫히지 않은 표면을 잡는 첫 검사가 요소 인접 그래프 BFS 다. 성분이 하나가 아니면 그 메시는 솔버에 넣기 전에 이미 틀렸다. 비정렬 메시의 병렬 분할에서 “고립된 조각이 생기지 않았는가”를 확인하는 것도 같은 루틴.
플러드 필. 플러드 필을 재귀 DFS 로 짜면 픽셀 수만큼 스택이 쌓여 죽지만, BFS 로 짜면 큐가 힙 메모리에 있어 깊이 문제가 없다. 그림판이 큰 영역을 칠해도 안 죽는 이유. 라벨링·블롭 카운팅·이미지 분할의 시드 성장도 같은 구조다.
격자 경로 계획. 균일 비용 격자에서는 경로 계획의 답이 그냥 BFS다. 다만 격자 거리는 유클리드 거리가 아니다. 4방향이면 맨해튼 거리라 대각선 방향에서 최대 $\sqrt2$ 배 과대평가하고, 8방향에 대각선 비용 $\sqrt2$ 를 주는 옥타일 거리도 22.5° 방향에서 약 8.2% 과대평가한다. 이 격자화 오차(metrication error)는 격자를 아무리 잘게 쪼개도 사라지지 않는다 — 해상도가 아니라 이웃 정의에서 오는 오차이기 때문이다.

7. 웨이브프론트와 고속 행진법 — 이산과 연속[편집]

BFS 의 층 구조를 “시간에 따라 퍼져 나가는 파면”으로 읽으면 자연스럽게 연속 아날로그가 떠오른다. 실제로 균일 매질에서 아이코날 방정식

|\nabla T(\mathbf{x})| = \frac{1}{F(\mathbf{x})}, \qquad T|_{\Gamma} = 0

의 해 $T$ 는 소스 $\Gamma$ 로부터의 도달 시간이고, $F \equiv 1$ 이면 그냥 거리함수다. 로봇공학에서 말하는 웨이브프론트 알고리즘은 이걸 격자에서 BFS 로 근사한 것이다.

차이는 업데이트 규칙에 있다. BFS 는 $T(\mathbf{x}) = \min_{\text{이웃}} T + h$ 로 이웃 하나만 보고 값을 정하기 때문에, 파면이 격자축에 묶여 앞 절의 격자화 오차를 그대로 안고 간다. 격자를 반으로 줄여도 오차 비율은 그대로다. 반면 고속 행진법은 같은 우선순위 확정 골격을 쓰되 풍상 차분으로 이차방정식을 풀어 두 방향의 이웃 값을 동시에 반영한다. 그래서 격자 간격 $h \to 0$ 일 때 진짜 유클리드 거리로 수렴한다. 한마디로 BFS·다익스트라는 그래프 거리를, 고속 행진법은 연속체 거리를 계산하며, 둘의 정확한 관계는 고속 행진법 문서가 다룬다. 레벨셋 방법에서 부호거리함수를 재초기화할 때 BFS 로 때우면 계면 위치에 편향이 생기는 것도 같은 이유다.

8. 관련 문서[편집]

깊이 우선 탐색 · 위상 정렬 · 이행 폐포
다익스트라 알고리즘 · A* 알고리즘 · 벨만-포드 알고리즘 · 우선순위 큐
고속 행진법 · 레벨셋 방법 · 경로 계획 · 내비게이션 메시
희소행렬 · 강성행렬 · 커스힐-맥키 알고리즘 · 그래프 분할
메시 생성 · 플러드 필 · 이미지 분할 · 퍼콜레이션
백트래킹 · 분할 정복 · 그리디 알고리즘 · 병렬 컴퓨팅

이 버그는 조용해서 더 나쁘다. 결과값은 맞는데(어차피 최종적으로 최솟값으로 수렴한다) 큐 길이가 간선 수만큼 부풀어 “왜 BFS 가 이렇게 느리지”만 남는다. 방문 표시는 넣을 때 찍는 것이 국룰이고, 이 규칙이 깨지는 유일한 예외가 가중치가 붙어 라벨 수정이 필요한 경우다. ↩
Beamer, S., Asanović, K., Patterson, D. (2012). “Direction-optimizing breadth-first search”. SC ‘12. 그래프 알고리즘 최적화 논문이 대개 자료구조를 만지작거리는 데 반해 이건 “그냥 반대로 훑자”는 발상 하나로 몇 배를 먹었다. Graph500 벤치마크가 하필 BFS 인 이유는 부동소수점 연산이 없어 FLOPS 로는 아무것도 측정되지 않고 순수하게 메모리 랜덤 접근 능력만 남기 때문이다. 단위도 FLOPS 가 아니라 TEPS(traversed edges per second). ↩
뒤집기가 대역폭은 그대로 두면서 프로파일만 줄인다는 것이 처음엔 마술처럼 보이는데, 대역폭은 최댓값이라 순열 반전에 불변이고 프로파일은 합이라 그렇지 않다는 것이 전부다. 이런 “공짜 점심”은 수치해석에서 드물어서, 그래서 아직도 함수 이름이 symrcm 이지 symcm 이 아니다. ↩