algorithm - 深さ優先検索で MST を作成しますか?

Question

対称グラフがあり、ランダムな頂点から他の頂点へのすべての最短パスを持つツリーを作成しました。ツリーを使用して最小スパニング ツリー (MST) を構築できますか? 私のアルゴリズムは深さ優先アルゴリズムに似ています。

Answer 1

最悪の場合、最短パス ツリーは最小スパニング ツリーを見つけるのに役立ちません。MST を見つけたいグラフを考えてみましょう。同じ長さのエッジを持つソース頂点を他の各頂点に追加します。そのソースからの最短パス ツリーは非常に長いエッジで構成されており、アプリオリにわかっているため、この場合、最短パス ツリーは役に立ちません。