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

개념

루트노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 넓게(wide) 탐색하는 것
• 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용
  • Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 민석이와 재훈이 사이에 존재하는 경로를 찾는 경우
  • 깊이 우선 탐색을 사용하면 → 모든 친구 관계를 다 살펴봐야 할지도 모른다
  • 넓이 우선 탐색을 사용하면 → 민석이와 가까운 관계부터 탐색
• BFS가 DFS보다 좀 더 복잡

특징

• 직관적이지 않고 시작노드부터 거리에 따라 단계별로 탐색
• 재귀적으로 동작하지 않는다
• 어떤 노드를 방문했었는지 여부를 반드시 검사 → 안하면 무한루프
• 방문한 노드를 차례대로 꺼낼 수 있는 자료구조인 **큐(Queue)**를 사용한다.
  • 선입선출(FIFO)
  • 파이썬에서는 deque()
  • 자바에서는 ArrayDeque()
• 프림 알고리즘, 다익스트라 알고리즘과 유사

작동과정