개념
너비 우선 탐색은 BFS라고도 하며, 루트에서 가까운 노드부터 같은 깊이의 노드를 모두 탐색한 뒤 다음 깊이로 내려가는 방식이다.
동작 방식
BFS는 OPEN과 CLOSED에서 OPEN을 큐처럼 사용한다. 먼저 들어온 노드가 먼저 탐색된다.
장점
목표 노드가 존재하고 모든 간선 비용이 같다면 최단 경로를 찾을 수 있다. 같은 레벨을 빠짐없이 탐색하기 때문에 해를 보장하는 성질이 강하다.
단점
한 레벨의 모든 노드를 저장해야 하므로 메모리 사용량이 커질 수 있다. 상태 공간이 넓게 퍼지는 문제에서는 매우 느려진다.
가장 얕은 해의 깊이를 , 분기 수를 라 하면 시간과 공간 복잡도는 보통 다음과 같다.