prim算法的解释

Question

我必须使用基于最小堆的优先级队列来实现Prim的算法。如果我的图包含顶点A、B、C和D以及下面的无向邻接列表...[它被排序为（顶点名称，相邻顶点的权重）]

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。我不知道，我真的很想得到答案。

Answer 1

可以为顶点指定权重。然后基于这些权重使用优先级队列。这是来自wiki的参考：http://en.wikipedia.org/wiki/Prims_算法

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将是您的优先队列。可以使用struct保存顶点的信息。

Answer 2

这是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

为了回答你的问题，你把边从一个节点放进去。

如果将所有边缘放入优先级队列，则得到 Kruskal 算法，该算法也用于最小生成树。

这取决于您如何表示图形的运行时间。邻接列表使Kruskal和Prim的复杂度O（E log E）为O（E logv），除非您使用fibonacci堆，在这种情况下，您可以实现O（E V log V）。

Answer 3

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