1

最小全域木を見つけたとしましょう。ここで必要なのは、MST の A から Z へのパスだけです。これを O(n^2) 時間で行うにはどうすればよいでしょうか?

ルート A から始めます。次に、フォーム Ax (x は任意の頂点) のツリー内のすべてのエッジを調べます。

次に、AB、AC、AD などを見つけたとします。次に、それぞれについて、フォームのエッジを探します: Bx、Cx、Dx...これは明らかに O(n^2) ではありません。

では、MST を指定してパス A -> Z を見つけるためのより良い/効率的な方法は何ですか?

ありがとう

4

4 に答える 4

5

深さ優先探索で十分です。最悪の場合、O（| V | + | E |）です。入力がMSTであるという事実は、一般的なグラフのようにループ検出について心配する必要がないことを意味します。

于 2012-07-09T16:13:28.700 に答える
0

最小スパニングツリーを検索すると、すべての頂点を接続する最小サブグラフであることがわかります。つまり、すべてのエッジが最大で1回使用されます。すでにMSTを使用しているため、サイクルをチェックする必要なしに、DFSまたはBFSのいずれかを使用して目的のパスを見つけることができます。

于 2012-07-09T16:14:32.927 に答える
0

MSTの作成中に、parent []を埋めることができるため、その後、単純なバックトラッキングを使用して、DFSなしでパスを見つけることができます。

于 2012-07-09T18:03:16.863 に答える
0

考えてみれば、MST を見つけるための Prim のアルゴリズムは、実際には Dijkstra の変装にすぎません。そのため、最短パスが見つかった場合、MST はすでに最短パスを提供します (上記のように、DFS を考えてください)。

于 2012-07-09T18:12:51.160 に答える