0

min-heap ベースのプライオリティ キューを使用して Prim のアルゴリズムを実装する必要があります。グラフに頂点 A、B、C、および D が含まれており、undirected隣接リストが以下の場合... [(頂点名、隣接する頂点への重み) としてソートされます]

A -> B,4 -> D,3
B -> A,4 -> C,1 -> D,7
C -> B,1
D -> B,7 -> A,3

ラフグラフ:

A-4-B-1-C
|   /
3  7
| /
D

優先キューはどのようになりますか? 何を入れたらいいのかわからない。全部入れるべき？ABC と D だけを入力する必要があります。手がかりがありません。答えを本当に知りたいです。

4

3 に答える 3

0

プリムのアルゴリズムは次のとおりです。

Choose a node. 
Mark it as visited.
Place all edges from this node into a priority queue (sorted to give smallest weights first).  
While queue not empty:  
    pop edge from queue
    if both ends are visited, continue
    add this edge to your minimum spanning tree
    add all edges coming out of the node that hasn't been visited to the queue
    mark that node as visited

あなたの質問に答えるために、1 つのノードからエッジを配置します。

すべてのエッジを優先キューに入れると、クラスカルのアルゴリズムが得られます。これは、最小スパニング ツリーにも使用されます。

実行時間は、グラフをどのように表現するかによって異なります。隣接リストは、フィボナッチヒープを使用しない限り、クラスカルの複雑さを O(E log E) にし、プリムの複雑さを O(E log V) にします。この場合、O(E + V log V) を達成できます。

于 2013-12-20T00:10:08.810 に答える
0

頂点にウェイトを割り当てることができます。次に、これらの重みに基づいてプライオリティ キューを使用します。これは wiki からの参照です: http://en.wikipedia.org/wiki/Prim's_algorithm

MST-PRIM (G, w, r) {
for each u ∈ G.V
u.key = ∞
u.parent = NIL
r.key = 0
Q = G.V
while (Q ≠ ø)
u = Extract-Min(Q)
for each v ∈ G.Adj[u]
if (v ∈ Q) and w(u,v) < v.key
v.parent = u
v.key = w(u,v)
}

Q が優先キューになります。構造体を使用して頂点の情報を保持できます。

于 2014-11-08T19:52:05.417 に答える