너비 우선 탐색(BFS)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
BFS의 주요 특징
-
동작 방식: 시작 노드의 인접한 노드를 먼저 탐색하고, 그 다음 레벨의 노드로 이동하여 탐색을 계속한다.
-
구현 방법: 주로 큐(Queue) 자료구조를 사용하여 구현한다.
-
활용: 최단 경로 문제나 임의의 경로를 찾는 문제 등에 효과적이다.
BFS의 동작 방식
1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다. 그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일하다. 하나 차이점이 있다면 탐색을 위해 스택이 아닌 큐를 사용한다.
2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다. 이때 방문 배열을 체크하여 이미 방문한 노드를 큐에 삽입하지 않는다. 또한 큐에서 꺼낸 노드는 탐색 순서에 기록한다.
3. 큐 자료구조에 값이 없을 때까지 반복하기
큐에 노드가 없을 때까지 앞선 과정을 반복한다. 선입선출 방식으로 탐색하므로 탐색 순서가 DFS와 다르다.
시간 복잡도
BFS의 시간 복잡도는 O(V+E)이다.
장단점
장점:
-
답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
-
최단 경로가 존재하면 반드시 찾을 수 있다.
단점:
-
경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 메모리를 많이 사용한다.
-
해가 존재하지 않는다면 유한 그래프(finite graph)에 대해서만 모든 그래프를 탐색한 후에 실패로 끝난다.
