너비 우선 탐색

너비 우선 탐색은 시작점에서 가까운 단계의 정점을 먼저 방문하는 그래프 탐색이다. 보통 FIFO 큐를 사용한다.

그래프 알고리즘
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘
최소 신장 트리 · 크루스칼 알고리즘 · 프림 알고리즘 · 강한 연결 요소 · 위상 정렬

원리

발견한 정점을 큐에 넣고 앞에서 꺼내며 이웃을 조사한다. 인접 리스트에서 정점 V개와 간선 E개를 처리하는 비용은 O(V+E)이다.

모든 이동 비용이 같은 미로에서는 출발점에서 한 칸, 두 칸 거리의 위치를 순서대로 찾으므로 최소 이동 횟수를 얻을 수 있다.

자료구조
배열 · 동적 배열 · 연결 리스트 · 스택 · 큐
덱 · 이진 트리 · 이진 탐색 트리 · AVL 트리 · 힙 (자료 구조) · 이진 힙

방문 표시는 큐에 넣을 때 관리하면 중복 등록을 줄일 수 있다. 간선 가중치가 서로 다르면 일반적인 BFS 거리 계산을 그대로 적용할 수 없다.