너비 우선 탐색

너비 우선 탐색

노드가 확장되는 순서 노드가 확장되는 순서
분류	검색 알고리즘
자료 구조	그래프
최악 시간복잡도	$O(|V|+|E|)=O(b^{d})$
공간복잡도	$O(|V|)=O(b^{d})$

너비 우선 탐색의 애니메이션 예시. 검은색: 탐색됨, 회색: 나중에 탐색될 대기열에 있음

미로 찾기 알고리즘에서 BFS

틱택토 게임 트리의 상단 부분

너비 우선 탐색(Breadth-first search, BFS)은 주어진 속성을 만족하는 노드를 찾기 위해 트리 (자료 구조)를 검색하는 알고리즘이다. 트리 루트에서 시작하여 현재 깊이에 있는 모든 노드를 탐색한 후 다음 깊이 레벨의 노드로 이동한다. 발견했지만 아직 탐색하지 않은 자식 노드를 추적하기 위해 일반적으로 큐 (자료 구조)와 같은 추가 메모리가 필요하다.

예를 들어, 체스 엔드게임에서 체스 엔진은 가능한 모든 움직임을 적용하여 현재 위치에서 게임 트리를 구축하고 너비 우선 탐색을 사용하여 백을 위한 승리 위치를 찾을 수 있다. 암시적 트리(게임 트리 또는 기타 문제 해결 트리와 같은)는 무한한 크기일 수 있다. 너비 우선 탐색은 솔루션 노드가 존재한다면 반드시 찾는다.

대조적으로, 역추적하고 다른 노드를 확장하기 전에 노드 분기를 가능한 한 멀리 탐색하는 (일반적인) 깊이 우선 탐색(DFS)은 무한 분기에서 길을 잃어 솔루션 노드에 도달하지 못할 수 있다. 반복적 깊이심화 탐색은 트리의 상위 부분을 계속해서 탐색하는 대가로 후자의 단점을 피한다. 반면에 두 깊이 우선 알고리즘은 일반적으로 너비 우선 탐색보다 훨씬 적은 추가 메모리를 필요로 한다.

너비 우선 탐색은 주어진 시작 노드('검색 키'라고도 함)를 가진 무향 그래프와 유향 그래프 모두에 일반화될 수 있다. 인공지능의 상태 공간 탐색에서는 정점의 반복 탐색이 종종 허용되지만, 너비 우선 탐색 기반 알고리즘의 이론적 분석에서는 일반적으로 반복을 방지하기 위한 예방 조치가 취해진다.

BFS와 그래프의 연결 요소를 찾는 데 적용하는 방법은 1945년 콘라트 추제가 그의 (거부된) 플랑칼퀼 프로그래밍 언어에 대한 박사 학위 논문에서 발명했지만, 1972년까지 출판되지 않았다. 1959년에 에드워드 F. 무어가 미로에서 최단 경로를 찾는 데 사용하면서 재발명되었고, 나중에 C. Y. 리가 배선 경로 배정 알고리즘으로 개발했다 (1961년 출판).

의사코드

입력: 그래프 G와 G의 시작 정점 root

출력: 목표 상태. 부모 링크는 root로 돌아가는 최단 경로를 추적한다.

 1  절차 BFS(G, root) 는
 2      Q를 큐로 설정
 3      root를 탐색됨으로 레이블 지정
 4      Q.enqueue(root)
 5      while Q가 비어 있지 않으면 do
 6          v := Q.dequeue()
 7          if v가 목표이면 then
 8              v 반환
 9          for all v에서 w로 가는 G.adjacentEdges(v)의 간선에 대해 do
10              if w가 탐색됨으로 레이블 지정되지 않았다면 then
11                  w를 탐색됨으로 레이블 지정
12                  w.parent := v
13                  Q.enqueue(w)

더 자세한 내용

몇몇 도시 간 연결이 있는 남독일의 예시 지도

주어진 지도에서 프랑크푸르트에서 시작하여 BFS를 실행하여 얻은 너비 우선 트리

이 비재귀적 구현은 비재귀적 깊이 우선 탐색 구현과 유사하지만 두 가지 방식으로 다르다.

1. 큐(선입선출)를 사용하는 대신 스택(후입선출)을 사용하며,
2. 정점을 큐에서 꺼낼 때까지 이 확인을 지연하는 대신 정점을 큐에 넣기 전에 정점이 탐색되었는지 확인한다.

만약 G가 트리 (자료 구조)라면, 이 너비 우선 탐색 알고리즘의 큐를 스택으로 바꾸면 깊이 우선 탐색 알고리즘이 된다. 일반적인 그래프의 경우, 반복 깊이 우선 탐색 구현의 스택을 큐로 바꾸면 너비 우선 탐색 알고리즘이 생성되지만, 다소 비표준적인 방식이다.

Q 큐는 알고리즘이 현재 검색 중인 경계를 포함한다.

노드는 구현에 따라 세트에 저장하거나 각 노드에 속성을 지정하여 탐색됨으로 레이블을 지정할 수 있다.

노드라는 단어는 일반적으로 정점이라는 단어와 호환된다는 점에 유의한다.

각 노드의 부모 속성은 BFS가 실행되고 선행 노드가 설정된 후 대상 노드에서 시작 노드까지 역추적하는 등 최단 경로에서 노드에 접근하는 데 유용하다.

너비 우선 탐색은 아래 예시에서 보여지는 너비 우선 트리를 생성한다.

예시

아래 그림은 독일 도시의 예시 그래프(위 그림)에서 프랑크푸르트에서 시작하여 BFS를 실행하여 얻은 너비 우선 트리를 보여준다.

분석

시간 및 공간 복잡도

시간 복잡도는 최악의 경우 모든 정점과 모든 간선이 탐색되므로 $O(|V|+|E|)$로 표현할 수 있다. $|V|$는 정점의 수이고 $|E|$는 그래프의 간선 수이다. $O(|E|)$는 입력 그래프가 얼마나 희소한지에 따라 $O(1)$에서 $O(|V|^{2})$까지 달라질 수 있음에 유의한다.

그래프의 정점 수가 미리 알려져 있고, 어떤 정점이 이미 큐에 추가되었는지 확인하기 위해 추가 자료 구조가 사용되는 경우, 공간 복잡도는 $O(|V|)$로 표현할 수 있으며, 여기서 $|V|$는 정점의 수이다. 이는 그래프 자체에 필요한 공간과는 별개이며, 알고리즘 구현에서 사용되는 그래프 표현에 따라 달라질 수 있다.

명시적으로 저장하기에는 너무 크거나 무한한 그래프로 작업할 때, 너비 우선 탐색의 복잡도를 다른 용어로 설명하는 것이 더 실용적이다. 시작 노드에서 거리 d(간선 횡단 횟수로 측정)에 있는 노드를 찾기 위해 BFS는 O(b^{d + 1}) 시간과 메모리를 필요로 하며, 여기서 b는 그래프의 "분기 계수"(평균 바깥쪽 차수)이다.

완전성

알고리즘 분석에서 너비 우선 탐색의 입력은 인접 리스트, 인접행렬 또는 유사한 표현으로 나타나는 유한 그래프라고 가정한다. 그러나 인공지능에서 그래프 순회 방법을 적용할 때는 입력이 무한 그래프의 암시적 표현일 수 있다. 이 맥락에서 검색 방법은 목표 상태가 존재할 경우 반드시 목표 상태를 찾는다면 완전하다고 설명된다. 너비 우선 탐색은 완전하지만 깊이 우선 탐색은 그렇지 않다. 암시적으로 표현된 무한 그래프에 적용될 때, 너비 우선 탐색은 결국 목표 상태를 찾지만, 깊이 우선 탐색은 목표 상태가 없는 그래프의 일부에서 길을 잃고 돌아오지 못할 수 있다.

BFS 순서

그래프의 정점 열거는 이 그래프에 BFS를 적용하여 얻을 수 있는 가능한 출력이라면 BFS 순서라고 한다.

$G=(V,E)$를 $n$개의 정점을 가진 그래프라고 하자. $N(v)$는 $v$의 이웃 집합임을 상기하자. $\sigma =(v_{1},\dots ,v_{m})$을 $V$의 서로 다른 원소들의 리스트라고 하자. $v\in V\setminus \{v_{1},\dots ,v_{m}\}$에 대해, $\nu _{\sigma }(v)$를 $v_{i}$가 $v$의 이웃이 되는 가장 작은 $i$라고 하자. 그러한 $i$가 존재하지 않으면 $\infty$라고 하자.

$\sigma =(v_{1},\dots ,v_{n})$을 $V$의 정점들의 열거라고 하자. 열거 $\sigma$는 모든 $1<i\leq n$에 대해, $v_{i}$가 $\nu _{(v_{1},\dots ,v_{i-1})}(w)$가 최소인 $w\in V\setminus \{v_{1},\dots ,v_{i-1}\}$인 정점일 때 BFS 순서(시작점 $v_{1}$ 포함)라고 한다. 동등하게, $\sigma$는 모든 $1\leq i<j<k\leq n$와 $v_{i}\in N(v_{k})\setminus N(v_{j})$에 대해, $m<i$인 $v_{j}$의 이웃 $v_{m}$이 존재한다면 BFS 순서이다.

응용

너비 우선 탐색은 그래프 이론의 여러 문제를 해결하는 데 사용될 수 있다. 예를 들면:

• 쓰레기 수집 (컴퓨터 과학) 복사, 체니의 알고리즘
• 두 노드 u와 v 사이의 최단 경로 찾기 (경로 길이는 간선 수로 측정, 깊이 우선 탐색에 비해 장점)
• (역) 커스힐-매키 메쉬 번호 매기기
• 네트워크 흐름에서 최대 유량을 계산하는 포드-풀커슨 방법
• 이진 트리 직렬화/역직렬화 대 정렬된 순서 직렬화: 트리를 효율적인 방식으로 재구성할 수 있게 한다.
• 아호-코라식 패턴 매처의 실패 함수 구성.
• 그래프의 이분성 테스트.
• 그래프의 전이 클로저를 계산하기 위한 병렬 알고리즘 구현.

같이 보기

• 깊이 우선 탐색