너비 우선 탐색(BFS, Breadth-First Search)
트리나 그래프의 하나의 정점에서 시작해서
정점에 인접한 모든 노드를 먼저 탐색하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
=> 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용
** BFS는 일반적으로 Queue라는 자료구조를 통해 구현되며, Queue가 어떤 것인지 잘 모르는 분은 아래 글 참조해주세요.
https://tobe-expert-sw.tistory.com/39
[자료구조] Queue
큐(Queue) Queue란 선입선출(First In First Out)의 구조를 갖는 자료구조 -> 먼저 들어온 것이 가장 먼저 나감 출처 : https://en.wikipedia.org/wiki/Queue_(abstract_data_type) 큐(Queue)의 특징 - back(top) : Data가 들어가는
tobe-expert-sw.tistory.com
BFS 탐색과정
1. 루트에서 시작한다.
2. 자식 노드들을 [1]에 저장한다.
3. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
4. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
5. 위의 과정을 반복한다.
6. 모든 노드를 방문하면 탐색을 마친다.
- 출처 : https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89
너비 우선 탐색(BFS)의 특징
- 시작 노드에서 시작해서 거리에 따라 탐색
- 재귀 동작 X
- 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함
- Queue를 사용하여 구현하는 것이 일반적
- 모든 경로를 동시에 탐색하기 때문에 무한 Loop에 빠지지 않음
(DFS의 경우 무한한 길이는 가지는 경로가 존재하게 되면 무한 Loop에 빠질 수 있음)
너비 우선 탐색(BFS)의 장단점
- 장점
- 가중치가 없는 그래프에서 출발노드에서 목표노드까지의 최단 길이 경로 보장
- 단점
- 경로가 길어 탐색 경우의 수가 많아지게되면 많은 메모리가 필요해질 수 있음
- 그래프가 무한 그래프일 경우 해를 찾지도 못하고, 끝내지도 못한다.