Pri的算法的解釋

我必須使用基於最小堆的優先級隊列來實現Prim的算法。如果我的圖形包含在頂點A，B，C，和d與下面undirected鄰接列表... [它被分類爲（頂點姓名，體重到相鄰頂點）]Pri的算法的解釋

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

優先級隊列的外觀如何？我不知道我應該把它放進去。我應該把一切都放在？我應該把A B C和D放在一起嗎？我沒有線索，我真的很想回答。

來源

2013-12-19 user3040019

Prim's: grow the tree by adding the edge of min weight with exactly one end in the tree. 
The PQ contains the edges with one end in the tree. 
Start with vertex 0 added to tree and add all vertices connected to 0 into the PQ. 
DeleteMin() will give you the min weight edge (v, w), you add it to the MST and add all vertices connected to w into the PQ. 

is this enough to get you started? 
--- 
so, in your example, the in the first iteration, the MST will contain vertex A, and the PQ will contain the 2 edges going out from A: 
A-4-B 
A-3-D

來源

2013-12-19 22:54:03 user3076574

這裏的Prim算法：

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

因此，要回答你的問題，你從一個節點把邊緣英寸

如果你把所有的邊緣進入優先級隊列，你有秩的算法，它也可用於最小生成樹。

這取決於你如何表現你的圖形，以運行時間是什麼。鄰接表使複雜度爲O（E日誌E）的秩的和普里姆的是O（E日誌V），除非你使用一個斐波那契堆，在這種情況下，就可以實現O（E + V登錄V）。

來源

2013-12-20 00:10:08 bdean20

您可以分配權重的頂點。然後使用基於這些權重的優先級隊列。這是從維基參考：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-08 19:52:05 DML

Pri的算法的解釋

回答

相關問題