[Graph] BFS (너비 우선 탐색)

너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식이다. 그래프를 탐색하는 방법에는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)로 크게 2가지가 있다. 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형식의 자료구조인 큐를 활용한다. BFS는 시작 정점 기준 거리가 가까운 곳부터 먼곳으로 탐색을 진행하기 때문에, 특정정점까지 가는 최단거리를 구하는데 용이하며, BFS 탐색이 종료된 경우 직전에 방문한 정점이 시점과 가장 먼 정점이라는 것을 알 수 있다. 개요 시작정점 v를 결정하여 방문한다. 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있..