-1

G(V,E)重み関数 を持つ無向連結グラフが与えられたw:E->R場合、エッジe(u,v)は E に属します。エッジ e を含む最小全域木があるかどうかを保証できる線形ランタイム複雑度で実行されるアルゴリズムはどれですか?

4

2 に答える 2

3

uから始まる深さ優先検索を実行し、指定されたエッジの重みと等しいかそれより重い重みを持つエッジを無視します。DFS がvにアクセスせずに完了する場合、これは、指定されたエッジが最も重いエッジであるサイクルがないことを意味します。したがって、指定されたエッジは最小スパニング ツリーに含まれます。

于 2013-01-30T19:05:56.283 に答える
2

これは、 Prim の最小スパニング ツリーを 2 回実装するように求めています。

  • 初めてアルゴリズムを通常どおり実行します。mst の重量をメモします。

  • 2 回目は、Prim のアルゴリズムが通常行うように空のツリーから開始するのではなく、既にツリーにあるノード u と v から開始します。これは、エッジ e(u,v) を持つことと同じです。次に、mst の構築を続けます。

  • 最後に、2 番目の mst が最初の mst と同じ重みである場合、エッジ e(u,v) は mst 内にある可能性があります。そうでない場合は、ライターの mst があります。

ちなみに、2*O(n) は O(n) のままです。

于 2013-01-31T03:13:33.547 に答える