BFS(Breadth-First Search)
BFS(Breadth-First Search) 너비 우선 탐색. 이름 그대로 그래프에서 넓은 부분을 우선적으로 탐색하는 알고리즘을 말한다. BFS의 탐색 순서 BFS는 A에서 출발해서 A에서 인접한 노드인 B, C부터 우선적으로 모두 탐색한다. 그 다음 B, C에서 인접한 노드인 D, E, F, G. 그 다음 F, G는 마지막 노드이니, D, E에서 인접한 노드인 H, I, J를 하나씩 탐색하면 모든 노드의 탐색이 끝나게 된다. 이때, 각 단계의 노드들은 그 안에서 방문 순서가 바뀔 수는 있지만, 다른 단계의 노드와는 방문 순서가 바뀔 수 없다. 여기서 가장 처음 시작하는 0단계 노드에서 K단계 노드까지는 최단거리가 K가 된다. 최단거리는 즉, A에서 마지막 노드까지 가는 데 필요한 간선의 최소 개수와 ..
2023. 5. 19.
