5.3.1 너비 우선 검색

너비 우선 검색(Breadth-First Search, BFS)은 그래프 내에 레이어 또는 레벨로 구성된 이웃 그룹들이 있을 때 적용할 수 있는 가장 효율적인 그래프 순회 전략입니다. 예를 들어, 링크드인 회원의 관계 네트워크는 회원을 중심으로 1단계 커넥션, 2단계 커넥션과 같은 레이어로 구성되어 있습니다.

BFS는 루트 버텍스에서 시작하여 그 인근 레이어에 있는 이웃 버텍스들을 탐색합니다. 이웃들에 대한 확인이 끝나면 다음 레이어로 이동하여 검색 과정을 반복합니다.

아래 무방향 그래프와 함께 BFS 알고리즘을 살펴봅시다.

▲ 그림 5-9 BFS 알고리즘