[ 알고리즘 ] 너비우선탐색 BFS - JAVA

[ 특징 ]

그래프 완전 탐색

시작노드에서 출발해 시작노드를 기준으로 가장 가까운 노드를 먼저 방문한다.

그렇기에 목표노드까지 경로가 여러 개일 경우 최단경로를 보장한다.

큐 or FIFO를 이용해 구현한다.

 

[ 시간복잡도 ]

O(V+E)

 

[ 구현시 고려해야 하는 점 ]

DFS와 동일하게 방문했던 노드는 다시 방문하지않는다.

 

 

[ 큐로 알아보는 탐색 순서 ]

탐색순서 1 - 2 - 3 - 5 - 6 - 4