가까운 곳부터 차례로 방문하는 그래프 탐색. 시작점에서 한 걸음 거리를 전부 본 뒤에 두 걸음 거리를 보고, 그 다음 세 걸음을 본다. 물결이 퍼지는 모양이다.
큐로 퍼뜨리기
큐를 쓴다. 한 정점을 방문하면 그 이웃 중 아직 안 가본 곳을 전부 큐에 넣고, 큐 앞에서 하나씩 꺼내 같은 일을 반복한다. 큐가 먼저 들어온 것을 먼저 내주니 가까운 것부터 처리되는 순서가 저절로 지켜진다.
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next : graph[cur]) {
if (!visited[next]) {
visited[next] = true;
queue.add(next);
}
}
}방문 표시는 큐에 넣을 때 해야 한다. 꺼낼 때 하면 같은 정점이 큐에 여러 번 들어간다. 복잡도는 O(V + E)로 DFS와 같다.
탐색 순서가 곧 거리
BFS의 진짜 쓸모는 최단거리가 공짜로 나온다는 데 있다. 시작점 A를 처리하며 이웃들을 큐에 넣으면 큐에 들어간 것들은 전부 A로부터 거리 1이다. 그 다음 거리 1짜리들을 처리하며 넣는 것들은 전부 거리 2다. 탐색 순서가 그대로 거리 순서라서 따로 계산할 것이 없다. 방향이 있는 그래프에서도 똑같이 성립한다.
그래서 최소 이동 횟수, 미로 탈출, 연결 요소 찾기, 진입차수 방식의 위상 정렬에 쓴다.
가중치가 다를 때
간선마다 비용이 다르면 무너진다. 1에서 2로 가는 직행 간선이 100인데 3, 4, 5를 거쳐 도는 길이 1짜리 간선 넷이라면 실제 최단거리는 4다. 그런데 BFS는 한 걸음에 도달하는 100을 최단이라고 답한다. 홉 수가 적은 것과 비용이 싼 것은 다르다.