[Algorithm] BFS : 너비 우선 탐색(Java)

DFS와 함께 가장 널리 사용되는 그래프 탐색 알고리즘인 너비 우선 탐색(Breadth First Search, BFS)에 대해 알아보자. 다익스트라(Dijkstra) 알고리즘이나 최소 스패닝 트리를 찾는 프림(Prim) 알고리즘 등이 BFS를 기반으로 하고 있다. 동작 과정 BFS는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이기 때문에 DFS에 비해 매우 직관적이다. 위의 그래프를 보자. a를 탐색의 시작점이라 하면, a에서부터 최소 몇 개의 간선을 지나야 도달할 수 있는가를 기준으로 그래프의 정점들을 나눌 수 있다. 간선 $i$개 지나야 도착할 수 있는 정점의 집합을 $H_i$라고 부르자. 그러면 BFS는 $H_0$에 속한 a를 가장 먼저 방문하고, 그 후 $H_1, H_2$ 그리고 ..