3 
 1 Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T
 2 While the vertices of G connected by T are disjoint:
 3   Begin with an empty set of edges E
 4   For each component:
 5     Begin with an empty set of edges S
 6     For each vertex in the component:
 7       Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S
 8     Add the cheapest edge in S to E
 9   Add the resulting set of edges E to T.
10 The resulting set of edges T is the minimum spanning tree of G.

ウィキペディアより。セットに参加しているので、外側のループはlogVであることを理解しています。しかし、内部ループが発生します。

セットを追跡するために同値関係を使用する場合、それはセットを表す要素のみを取得していることを意味するため、すべての要素を持っているわけではないため、2 つのセット間で最小の重みを持つエッジを決定することはできません。 . 子への参照を保持するように構造を変更する場合でも、各セットのすべての子を取得する必要があります。つまり、最悪のシナリオ、各セットの O(V/2) = O(V) です。

その後、2 つのコンポーネントを接続する最小のエッジを見つける必要があります。これは、2 つのコンポーネントを接続するすべてのエッジを調べることを意味します。したがって、各ノードを反復処理して、そのエッジが他のコンポーネントの要素に接続されているかどうかを確認する必要があります。接続している場合は、現在の最小エッジよりも小さいかどうかを確認します。

つまり、ノードを反復する外側のループと、そのノードのエッジを反復する内側のループ - O(V E)。O(logV) ループ内にあるため、O(logV V*E) が得られます。

さて、すべてのエッジを繰り返し処理する必要があるように思えますが、2 つのコンポーネント間の最小エッジをどのように選択するのでしょうか? 特定のエッジが異なるコンポーネントのノードを接続しているかどうかはわかりますが、それらを接続しているノードの重みが最小かどうかはわかりません。そして、最小の重量のものを取得すると、それらが接続されない可能性があります.

4

1 に答える 1

2

ハッシュテーブルが許可されている場合、それがO（Elog N）アルゴリズムになる方法がわかります。すべてのコンポーネントは、異なるハッシュセットとして保存されます。最初、各セットには単一のノードが含まれています。すべてのコンポーネントの最小の「ブリッジ」を見つけるステップは、各エッジを最大2回検査し、ハッシュセットで一定時間のルックアップを想定しているため、O（E）時間がかかります。次に、セットをマージします。これにはO（N）時間がかかります。グラフが接続されているため、E> = N-1であるため、反復ごとの総コストはO（E）になります。

- 編集 -

throwawayacctのコメントに続いて、ハッシュ構造はまったく必要ありません。各反復で、前の反復から得られたフォレストグラフがあるため、O（E）時間で連結成分を再計算できます。これは、たとえば、すべてのノードからの単純なDFSトラバーサルによって実行できます。これにより、各コンポーネントに一意の「色」が設定されます。次に、ブリッジを見つけるためにエッジをスキャンするとき、異なる色のノードを接続しているエッジのみを考慮します。

于 2010-07-28T08:09:53.283 に答える