Bread First Search(BFS)

소개

넓이 우선 탐색 - BFS

• 자료구조를 탐색하는 방법 중 하나로 하나의 정점으로부터 시작하여 인접한(가까운) 노드를 먼저 탐색한다.
  • 다른 표현으로, 같은 깊이(level)의 노드를 먼저 탐색함
• 주로, Graph나 Tree구조의 자료구조를 탐색한다.

  

알고리즘의 구현

• BFS는 Queue 형태의 자료구조로 구현된다.
• 방문한 node 또는 vertic을 기록해야한다.
• 선입선출 원칙으로 탐색한다.

BFS의 특징

• 두 노드 사이의 최단 거리를 찾거나 임의의 경로를 찾고 싶을 때 사용한다.
• 시간 복잡도가 인접 행렬로 구현된 그래프는 O(N^2), 인접 리스트로 구현된 그래프는 O(N+E)가 걸린다.
  • 단, N는 정점의 수, E는 간선을 의미함
• 재귀적으로 동작하지 않음

참고

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
https://en.wikipedia.org/wiki/Breadth-first_search