너비 우선 검색

Breath-First-Search

너비 우선 검색 알고리즘

그래프 탐색 알고리즘 중 하나로 쉽게 이해하면 다단계이다.

나를 시작점(s)으로 나의 친구들을 모두 만난다. 전부 다 만났으면 그 친구들의 친구들을 모두 만난다. 그리고 또 다 만났으면 그 친구들의 친구들을 만난다. 그렇게 level 단위로 정점들을 검색해 나가는 방법이 너비 우선 검색 알고리즘이다.

• 구현 : Queue. 만난 정점을 Queue 구조에 넣는다. Queue는 선입선출 방식으로, 먼저 들어온 데이터가 먼저 나간다. BFS의 동작 방식을 보면, 시작 정점과 간선으로 연결된 정점들을 탐색하고 시작 정점을 뺀다. 그리고 그 정점의 인접리스트에 속한 정점들을 Queue에 넣은다음 다시 밴다.