[Algorithm] BFS - 깊이 우선 탐색

1. 너비 우선 탐색이란,
   • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
   • 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
   • 깊게 탐색하기 전에 넓게 탐색하는 것
   • 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때

     ➡️ 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
     → 깊이 우선 탐색의 경우 : 모든 친구 관계를 다 살펴봐야 할지도 모름
     → 너비 우선 탐색의 경우 : Ash와 가까운 관계부터 탐색

2. 너비 우선 탐색의 특징

   • 직관적이지 않은 면이 있다.
     • BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
   • BFS는 재귀적으로 동작하지 않는다.
   • 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
     • 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
   • BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
     • 선입선출(FIFO) 원칙으로 탐색
     • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
   • ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

3. 너비 우선 탐색의 과정

   

4. 너비 우선 탐색의 구현

   • 자료 구조 큐(Queue)를 사용

5. 너비 우선 탐색의 시간복잡도

   • BFS는 그래프(정점의 수 : N, 간선의 수 : E)의 모든 간선을 조회한다.
     • 인접 리스트로 표현된 그래프의 시간복잡도 = $O(N+E)$
     • 인접 행렬로 표현된 그래프의 시간복잡도 = $O(N^2)$
   • 깊이 우선 탐색과 마찬가지로 그래프 내에서 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

➰ References

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html