2

グラフ内のすべての辺の重みが 1 から |V| の範囲の整数であるとします。Prim のアルゴリズムをどれくらい速く実行できますか? ある定数 W に対してエッジの重みが 1 から W の範囲の整数である場合はどうなるでしょうか?

MST-PRIM(G,w,r)
1.  for each u∈  G.V
2.       u.key=inf
3.       u.π=NIL
4.  r.key=0
5.  Q=G.V
6.  while Q != Ø 
7.     u=EXTRACT-MIN(Q)
8.     for each v ∈  G.Adj[u]
9.         if v∈  Q and w(u,v)<v.key
10.          v. π=u
11.          v.key=w(u,v)

私の教科書によると:

プリムのアルゴリズムの実行時間は、最小優先度キュー Q の実装方法によって異なります。Q をバイナリ最小ヒープとして実装すると、BUILD-MIN-HEAP 手順を使用して、O(V) の 1 ~ 5 行目を実行できます。時間。while ループの本体は |V| を実行します。各 EXTRACT-MIN 操作には O(lg V) 時間がかかるため、EXTRACT-MIN へのすべての呼び出しの合計時間は O(VlgV) です。行 8 ~ 11 の for ループは、すべての隣接リストの長さの合計が 2|E| であるため、全体で O(E) 回実行されます。for ループ内では、Q にあるかどうかを示す各頂点のビットを保持し、頂点が Q から削除されたときにビットを更新することにより、9 行目の Q のメンバーシップのテストを一定時間で実装できます。行 11 の割り当てには、バイナリ最小ヒープが O(lg V) 時間でサポートする、最小ヒープに対する暗黙の DECREASE-KEY 操作が含まれます。したがって、

行 1 ~ 4 には O(V) 時間が必要です。BUILD-MIN-HEAP プロシージャが線形時間を必要とする理由についていくつかの説明を読みましたが、理解できませんでした。MIN-HEAP プロシージャの時間計算量が O(V) である理由を説明していただけますか?

さらに、最小ヒープでは、最小要素がルートにあると考えました。では、各 EXTRACT-MIN 操作に O(lg V) の時間がかかるのはなぜですか?

すると、for ループが O(Σ_{v in VG} deg(v)) 回実行されますね。なぜ Σ_{v in VG} deg(v)=2E なのか説明していただけますか?

また、ある定数 W に対してエッジの重みが 1 から W の範囲の整数であることがわかっているとしたら、何が違うでしょうか?

編集

グラフ内のすべての辺の重みが 1 から |V| の範囲の整数であるとします。Prim のアルゴリズムをどれくらい速く実行できますか?

プリムのアルゴリズムができるだけ速く実行されるように、上記のアルゴリズムで何を変更できますか?

4

1 に答える 1

3

答え-1

最初の質問は、stackoverflow from- this questionにあります。

答え-2

Extract min 操作は O(1) 時間でルートから最小要素を取得しますが、それに伴い、O(1) 時間で最小要素を与える次の Extract min 操作を行う操作を実行する必要があります。私たちは何をしますか?ルート要素を右端のリーフ ノードと入れ替えてから、そのリーフ ノードを削除し、ルートをヒープ化します。これにより、新しいルートからリーフ ノードに浸透する可能性があり、O(logn) の複雑さを意味します。(2^h=n の場合、h=log2(n))。

答え-3

無向グラフの場合

なぜ2Eなのか。わかった!各ノードには、それに接続されたエッジがあります(接続されていない場合、次数はゼロです)。現在、ノードの次数は n であり、接続されているエッジが n 個あることを意味します。では、例を見てみましょう

1---2
|  /
| /
3
1 has degree=2
2 has degree=2
3 has degree=2
-+-+-+-+-+-+-+-
so sum(deg(v))=2+2+2=6= 2*(no of edges);

なんでそうなの?この状況を握手 b/2 の友人としてモデル化することができます。各ノードは友達を表し、各エッジは握手を表します。あなたがBと握手したら、Bもあなたと握手します。そのため、各ハンドシェイク (エッジ) はノード (フレンド) によって 2 回考慮されます。

:有向グラフの場合、結果は次のようになりますE

答え-4

これらのリンクはすでに説明しています。これをチェックして、すべてが明確になることを願っています

1.リンク1

2.リンク2

ここで明確にしましょう。アルゴリズムとは - コーメンでは、このように与えられます -

MST-PRIM(G, w, r)
 1  for each u ∈ V [G]  ~~~~~~~~~> O(V)
 2       do key[u] ← ∞
 3          π[u] ← NIL
 4  key[r] ← 0
 5   Q ← V [G]          ~~~~~~~~~> If binary min-heap used then heapification's comlexity is O(V)
 6   while Q ≠ Ø        ~~~~~~~~~> Executed |V| times
 7       do u ← EXTRACT-MIN(Q)~~~> O(logV) in binary heap
 8          for each v ∈ Adj[u] ~~~> For each vertex the degree of that vertex times it will loop. So total O(E) times
 9              do if v ∈ Q and w(u, v) < key[v]
10                    then π[v] ← u
11                         key[v] ← w(u, v)~~~> decrease key operation in min-heap(binary) O(logV) times.

したがって、複雑さの合計 = O(V)+O(VlogV)+O(ElogV) = O((V+E)logV) //VlogV が V を支配します。

ここで、すべてのエッジの重みが 1 から |V| の範囲にある場合 次に、リスト A[1..|V|] の配列を取得できます。ここで、辺の重みが 1(E1)、3(E2)、2(E3)、5(E4)、7(E5)、3(E6) で、7 つの頂点と 6 つの辺があるとします。

最初はリストの配列

A  [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
    0   1   2   3   4   5   6   7

次に、並べ替えをカウントする方法を適用します。エッジの重みごとに、そのエッジを対応する配列の場所に配置します

エッジ E1 に遭遇した後、配列は次のようになります。

A  [ ] [E1] [ ] [ ] [ ] [ ]  [ ] [ ]
    0    1    2  3   4    5   6   7

その後、エッジ E2 に対して

A  [ ] [E1] [ ] [E2] [ ] [ ] [ ] [ ]
    0   1    2   3    4   5   6   7

したがって、すべてのエッジをトラバースした後、

                  E6
                  | 
A  [ ] [E1] [E3] [E2] [ ] [E4] [ ] [E5]
    0    1    2    3   4    5   6   7

おそらくこれで、|V| についていくつかの回答が言及された理由が理解できると思います。リストまたは |W| この図からリストします。

これで、O(V) 時間で配列からすべての最小値を取得できるようになりました。通常、広範囲の重みの場合、ヒープ データ構造を使用してエッジを格納します。

ただし、この場合、重みは 1 .. |V| のいずれかです。そのため、単純にエッジを |V| に格納できます。重みが 1 から |V| までのエッジ用の個別のリスト。

重みが最小のエッジを見つけるには、最初のリストから 1 つを取得します。空の場合は、2 番目のリストからエッジを取得します。

リストから要素にアクセスして削除するのは O(1) であり、リストから一番上の要素を削除するだけです。したがって、Prim のアルゴリズムは O(V*W+E) で実行されます。

したがって、W=O(V) の場合、O(V^2+E) で実行されます。

重みの範囲が 1..W (W=O(1) 定数) の場合、同様に複雑度は O(V*W+E) になります。~O(V+E)。

疑似コード

Cで

構造体エッジ { int u,v,w; } struct listnode { エッジ e; struct listnode *next; }

struct listnode ** A;
A=malloc(sizeof(struct list *)*N);
Intilally all of A[i]=NULL;

A[i]=malloc(sizeof(struct listnode),1);
(*A[i]).e.u=..
(*A[i]).e.v=..
(*A[i]).e.w=..

 create the array of lists don't insert anythiing.
 Then just select a vertex say s
 keep an array visisted[1..|V|]
 visited[s]=true;
 no_of_visited=1;
 recently_visted=s;
 while(all nodes are not visited)   //no_of_visited!=|V|
 {
    insert all edges from s-x (adjacent) in the array of lists.(s is recently visited) provided x is not visited
    get the minimum weight one
    if it is u-w and w is not visited
    {
        visited[w]=true;
        no_of_visited++;
        recently_visited=w;
        insert(u,w) in spanning tree
    }

}

複雑性分析

アルゴリズム:

重みが 1..|W| の範囲内にあるとします。

Then just select a vertex say s ~~~~~~~~~~> O(1)
 //keep an array visisted[1..|W|]
 for i=1 to |W| 
     visited[i]=false;   ~~~~~~~~~~> O(|W|) 
 visited[s]=true; ~~~~~~~~~~> O(1)
 no_of_visited=1; ~~~~~~~~~~> O(1)
 recently_visted=s; ~~~~~~~~~~~ O(1)
 while(all nodes are not visited) ~~~~~O(V)  //no_of_visited!=|W|
 {
    insert all edges from s-x (adjacent) in the array of lists.(s is recently visited) provided x is not visited ~~~~~O(|E|) altogether
    get the minimum weight one          ~~~~~O(|W|) 
    if it is u-w and w is not visited   --O(1)
    {
        visited[w]=true;               
        no_of_visited++;
        recently_visited=w;
        insert(u,w) in spanning tree    --O(1)
    }

}

複雑さ=O(|W|)+O(|W|.|V|)+O(|E|)~O(E+V W) W=O(V)の場合、T(V,E)= O(E+V V)=O(E+V^2)

于 2015-04-13T13:36:36.633 に答える