탐색 알고리즘 (BFS)

대표적인 그래프 탐색 알고리즘에는 DFS 와 BFS 가 있다 이중 이번 포스팅에서는 BFS에 대해 다뤄 볼 것이다.

BFS 란?

• 대표적인 그래프 탐색 알고리즘으로 너비 우선 탐색(Breadth First Search) 의 줄임 말이며 그래프의 모든 노드를 탐색하는데 같은 레벨에 위치한 노드를 먼저 탐색하고 다음 레벨로 넘어가는 순서의 탐색 알고리즘이다.

• 시간 복잡도는 O (V + E) (V :node의 수, E : edge의 수)

ex)

• 위와 같은 형태의 트리가 있을 경우 순서는
  0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
  순으로 같은 레벨의 노드를 탐색후 다음 레벨의 노드를 탐색하는 순서를 볼 수 있다.

• 코드 보기

(코드에 대한 설명은 차차 문제와 함께 업로드 하겠다.)