너비 우선 탐색(BFS)

너비 우선 탐색(BFS) => 큐 사용

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
가장 가까운 정점을 먼저 방문하고 이후 멀리 떨어져 있는 정점을 방문하는 방식이다.

특징

• 직관적이지 않다.
• 큐를 사용한다. (선입 선출이 원칙이다)
• Prim, Dijkstra 알고리즘과 유사하다.

과정

결국 이동 순서는
0 -> 1
0 -> 2
0 -> 4
1 -> 2
2 -> 3
3 -> 4
이 된다.

시간 복잡도

인접 리스트로 표현된 그래프: O(N+E)
인접 행렬로 표현된 그래프: O(N^2)