[필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해

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

BFS 너비 우선 탐색 방법

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색한다.

그렇게 되면 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문할 수 있다.

Queue를 활용해야만 순서대로 접근이 가능하다.

 

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.

 

ex)  지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 철수와 영희사이에 존재하는 경로를 찾는 경우

• 깊이 우선 탐색(DFS)의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색(BFS)의 경우 - 철수와 가까운 관계부터 탐색

 

Queue으로 이해하는 BFS

BFS 경로 => A, B, C, D

시간 복잡도와 장단점

시간복잡도

• 시간복잡도는 DFS와 똑같다. 모든 정점을 한 번씩 방문하여 인접한 간선을 검사하기 때문
• 인접 행렬에서의 시간 복잡도: O(V²)
• 인접 리스트에서의 시간 복잡도: O(V+E)
• V: 정점(노드)의 개수, E: 간선의 개수

장단점

•  장점
  • 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

• 단점:
  • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
  • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
  • 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

 

BFS를 활용하기 적합한 문제

• 최단거리 구해야 하는 문제

너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문이다.(장점)

 

• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS