[알고리즘] 너비 우선 탐색 (Breadth-first search, BFS)

너비 우선 탐색(Breadth-first search, BFS) ① 너비 우선 탐색이란? ▷ 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘입니다.▷ 프림의 최소 스패닝 트리 알고리즘 등이 너비 우선 탐색을 골격으로 하고 있습니다. ▷ 위의 그림을 너비 우선 탐색을 사용하면 H0(단계) -》 H1(단계) -》H2(단계) 순으로 방문합니다.▷ k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k입니다. (H0(단계) : 0단계, H1(단계) : 1단계, H2(단계) : 2단계)▷ 최단거리는 이동하는 데 필요한 최소 개수의 간선으로 보면됩니다.▷ 각 정점을 방문할 때마다 모든 인접 정점들을 검사합니다. 이 중 처음 보는 정점을 발견하면 방문 예정이라고 기록해 둔 뒤, 모든 인접 정점을 검사한 후..