깊이 우선 검색을 사용하여 MST를 만드시겠습니까?

Question

나는 대칭 그래프를 가지고 임의의 정점에서 다른 정점까지의 가장 짧은 경로를 가진 트리를 만들었습니다. 최소 스패닝 트리 (MST)를 구성하기 위해 트리를 사용할 수 있습니까? 내 알고리즘은 깊이 우선 알고리즘과 유사합니다.

Answer 1

최악의 경우, 최단 경로 트리가 최소 스패닝 트리를 찾는 데 도움이되지 않습니다. 우리가 MST를 찾고자하는 그래프를 생각해보십시오. 큰 꼭지점을 가진 원본 정점을 서로 다른 정점에 추가합니다. 그 소스로부터의 최단 경로 트리는 선험적으로 알고있는 매우 긴 에지로 구성되어 있으므로이 경우 최단 경로 트리가 유용하지 않습니다.