본문으로 바로가기

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

트리나 그래프의 하나의 정점에서 시작해서 정점에 인접한 모든 노드를 먼저 탐색하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법으로 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.

 

BFS 탐색과정

  1. 루트에서 시작한다.
  2. 자식 노드들을 [1]에 저장한다.
  3. [1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
  4. [2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
  5. 위의 과정을 반복한다.
  6. 모든 노드를 방문하면 탐색을 마친다.

DFS,BFS (출처-나무위키)

왼쪽 그림과 같이 하나의 노드의 모든 루트를 깊게(deep) 탐색하고 다음 노드로 넘어가는 깊이우선탐색(DFS)과 오른쪽처럼 달리 동일한 깊이를 먼저 넓게(wide) 탐색하는 것을 볼 수 있습니다.

너비 우선 탐색(BFS)의 특징

  • BFS는 시작 노드에서 시작해서 거리에 따라 탐색
  • BFS는 재귀적으로 동작하지 않는다. (DFS는 재귀 호출 이용)
  • 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함
  • BFS는 재귀 호출(Recursion Call)을 이용하여 소스 코드로 구현하는 DFS와는 달리, 선입선출(FIFO) 원칙자료 구조  Queue를 사용하는 경우가 일반적입니다. 배열에서 사용하는 경우, 방향 데이터를 이용해 배열의 시작점에서 범위를 넓혀 가면서 탐색하는 것이다.
  • DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있습니다.
  • 전 세계의 모든 사람들의 관계를 그래프로 만들고, 'Jack' 과 'Kongnamoo' 의 관계를 잇는 간선을 찾는다고 가정해보면 BFS를 사용하면 Jack에게 관련된 간선들을 하나씩 파악해나가기 때문에 Kongnamoo를 비교적 빠르게 찾을 수 있지만, DFS로 파악할 경우 Jack의 자식노드를 모두 파악하고 가므로 Jack의 부모님, Jack의 외할머니...Jack의 외할머니의 친구의친구.. 등으로 무한한 길이로 빠져 영원히 종료하지 못하는 것이다. 때문에 DFS 에서는 너무 깊게 뻗어나가는 것을 막기 위해 때때로 limit를 걸어 둡니다.
  • ‘Prim’, ‘Dijkstra’ 알고리즘과 유사

너비 우선 탐색(BFS)의 장단점

장점

  • 가중치가 없는 그래프에서 출발노드에서 목표노드까지의 최단 길이 경로를 보장합니다.

단점

  • 경로가 길 경우에는 탐색 가지가 급격히 증가하므로 공간저장에 많은 메모리가 필요하게 됩니다.
  • 최악의 경우 해가 가장 깊은 곳에 위치해 있다면 깊이우선탐색(DFS)으로 모든 정점을 탐색한 것과 차이가 없거나 위치에 따라 안 좋은 성능이 나옵니다.
  • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
  • 무한 그래프(infinite graph)의 경우에는 해를 찾지도 못하고, 끝내지도 못한다.

Reference

https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89