🌱 너비 우선 탐색 (BFS, Breadth-first search)
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
- 그래프 완전 탐색
- FIFO 탐색
- Queue 자료구조 이용
- 시간복잡도 : O(V+E)
너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현. 또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 떄 최단 경로를 보장.
🌱 너비 우선 탐색 (BFS, Breadth-first search)의 핵심 이론
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요.
그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일.
하나 차이점이 있다면, 탐색을 위해 스택이 아닌 큐를 사용.
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입.
이떄 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않음.
또한 큐에서 꺼낸 노드는 탐색 순서에 기록.
3. 큐 자료구조에 값이 없을 때까지 반복하기
큐에 노드가 없을 때까지 앞선 과정을 반복.
선입선출 방식으로 탐색하므로 탐색 순서가 DFS와 다름을 확인해보기.
2,3 순서로 노드를 꺼내며 인접 노드를 큐에 삽입.
2의 경우 5,6은 아직 방문한 적이 없으므로 방문 배열을 체크하며 모두 삽입.
3의 경우 4 역시 방문한적이 없으므로 방문 배열을 체크하며 삽입.
탐색 순서는 2,3 이 기록됨.
5,6 을 꺼낼 때는 인접 노드가 없므니 탐색 순서에 기록만 하고 꺼냄.
4를 꺼낼 때는 인접 노드가 6이지만 이미 앞서 방문했으므로 6은 큐에 삽입하지 않고 꺼내지만 함.
최종 탐색 순서는 1,2,3,5,6,4
