5

Prim の MST アルゴリズムの時間計算量は、隣接O(|V|^2)行列表現を使用する場合です。

隣接行列を使用してプリムのアルゴリズムを実装しようとしています。これを 参考にしています。

V = {1,2...,n}
U = {1}
T = NULL
while V != U:

     /* 
         Now this implementation means that 
         I find lowest cost edge in O(n).
         How do I do that using adjacency list? 
     */

     let (u, v) be the lowest cost edge 
                such that u is in U and v is in V - U;

     T = T + {(u,v)}
     U = U + {v}

編集：

  1. Prim のアルゴリズムをよく理解しています。
  2. ヒープと優先キューを使用して効率的に実装する方法を知っています。
  3. より良いアルゴリズムについても知っています。
  4. グラフの隣接行列表現を使用して、O(|V|^2) の実装を取得したいと考えています。

非効率な実装が欲しい

4

3 に答える 3

6

uが U にあり、vが VU にあるような最小コスト エッジ ( u , v ) を見つけることは、優先キューで行われます。より正確には、優先キューには、VU からの各ノードvと、 vから現在のツリー U への最低コスト エッジが含まれます。つまり、キューには、正確に |VU| が含まれます。要素。

新しいノードuを U に追加した後、以前よりも低コストのエッジがuの隣接ノードに到達できるかどうかを確認して、優先キューを更新する必要があります。

プライオリティ キューの選択によって、時間の複雑さが決まります。プライオリティ キューを単純な配列として実装することで、O(|V|^2) を取得できますcheapest_edges[1..|V|]。これは、このキューで最小値を見つけるのに O(|V|) 時間がかかり、その |V| を繰り返すためです。回。

擬似コード:

V = {2...,n}
U = {1}
T = NULL
P = array, for each v set P[v] = (1,v)

while V != U

    (u,v) = P[v] with v such that  length P[v]  is minimal

    T = T + {(u,v)}
    U = U + {v}

    for each w adjacent to v
        if length (v,w) < length P[w] then
            P[w] = (v,w)
于 2010-08-06T11:59:31.153 に答える
0

ダイクストラのアルゴリズムのように、現在の部分ツリーに接続されているノードを最小コスト エッジ (サイクルを生成しない) で選択します。ウィキペディアは、あなたが持っている疑似コードよりも Prim をよりよく説明していると思います。それを見て、さらに質問がある場合はお知らせください。

于 2010-08-06T10:21:26.647 に答える
0

エッジをコストで並べ替えてから、コストの順にエッジを反復できます。そのエッジが 2 つの異なるサブグラフを結合する場合は、そのエッジを使用します。

ここに実装があります。頂点の数（N）、辺の数（M）、辺の順番（A、B、Cost）を読み取り、辺を出力します。これがクラスカル アルゴリズムです。

同じ入力を使用した、ヒープを使用した Prim のアルゴリズムの実装については、こちらを参照してください。

于 2010-08-06T13:50:25.907 に答える