algorithm - prim算法的解释

Question

我必须使用基于最小堆的优先级队列来实现 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吗？我不知道，我真的很想要一个答案。

Answer 1

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

Answer 2

您可以为顶点分配权重。然后根据这些权重使用优先级队列。这是来自 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 将是您的优先队列。您可以使用 struct 来保存顶点的信息。

Answer 3

这是 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 log V)，除非您使用斐波那契堆，在这种情况下您可以达到 O(E + V log V)。