[기초 알고리즘] 넓이 우선 탐색(BFS)Ⅱ

넓이 우선 탐색(BFS)

이제 기본적인 내용은 다 배웠으니 그림으로 어떤 식으로 탐색이 진행 되는지 

알아보도록 하겠습니다. 최대한 이해하기 쉽게

일단 그래프를 보시면 세 가지 색으로 나타나 있을 것이 보이실 겁니다.

검정 / 회색 / 흰색 이렇게요

검정은 탐색 완료 / 회색은 탐색 중 / 흰색은 아직 미 탐색 

위에 보이는 그래프처럼 시작점을 A라고 한다면 A에서 같은 거리에 있는 B / D 를 탐색하기 시작합니다.

그리고 난 뒤, A는 탐색이 끝났으므로 검정으로 변환시켜 주고 B / D를 탐색하고 난 뒤 

B는 더 이상 탐색할 수 있는 정점이 없으므로 검정으로 변환시켜 주고 D는 다시 탐색을 시작합니다.

계속 이러한 과정을 거치면서 마지막 연결된 정점까지 탐색을 하는 것입니다.

이런 설명으로는 많이 부족할 것 같아서 

나보다 더 좋은 설명을 해주신 분이 있어서 아래 링크 남깁니다

http://exynoa.tistory.com/269