[탐색] 너비 우선 탐색, BFS(Breadth First Search)

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃

https://www.youtube.com/watch?v=Cs8DaupoSPM&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=21 

---

너비 우선 탐색, BFS(Breadth First Serch)

 

그래프 완전 탐색 기법 중 하나

시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

기능	특징	시간 복잡도(노드 수: V, 엣지 수: E)
그래프 완전 탐색	- FIFO 탐색 - Queue 자료구조 이용	O(V + E)

 

선입선출 방식으로 탐색하므로 큐를 이용해 구현함

탐색 시작 노드와 가까운 노드를 우선하여 탐새갛므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장함

 

BFS는 한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 리스트가 필요하며, 그래프는 인접 리스트로 표현할 수 있음

1. 시작할 노드를 정한 후 큐에 시작점을 삽입, 방문 여부 표시
2. 큐의 값을 pop 한 후 탐색 순서에 기록, 삭제한 값의 인접 노드(인접 리스트를 통해 확인)에 대하여 방문 여부 확인 후 방문하지 않았다면 큐에 삽입, 방문 여부 표시
3. pop한 값에 인접 노드가 없다면 다음 큐 값 pop 하여 2번 진행
4. 큐에 남은 값이 없을 때까지 반복