210209 [Algorithm] 너비우선탐색 (BFS)

너비 우선 탐색(Breadth first search)

너비 우선 탐색이란

• 루트 노드(시작 지점)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.
• 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법이다.
• 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다.
• 활용 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.
  • 예시 : 지구상에 존재하는 모든 친구 관계를 그래프로 표현하고, Ash와 Vanessa 사이에 존재하는 경로의 가짓 수를 세는 경우
    • 깊이 우선 탐색의 경우 - 모든 친구 관계를 전부 살펴봐야 할지도 모른다.
    • 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색한다.

너비우선탐색의 특징

• 직관적이지 않을 수 있다. (?)
  • BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다.
• BFS는 재귀적으로 동작하지 않는다.
• 어떤 노드를 방문했었는지 여부를 반드시 저장해야한다. (이건 DFS도 마찬가지 아닌가?)
• BFS는 방문한 노드들을 차례로 저장하고, 선입선출 방식을 사용하는 큐(Queue)로 구현된다.
• 'Prim', 'Dijkstra' 알고리즘과 유사하다.