答え-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)