c++ - Prims 算法节点优先级

Question

所以我得到了这个 Prims-Algorithm 的伪代码，

INPUT: GRAPH G = (V,E)
OUTPUT: Minimum spanning tree of G

Select arbitrary vertex s that exists within V
Construct an empty tree mst
Construct an empty priority queue Q that contain nodes ordered by their “distance” from mst
Insert s into Q with priority 0

while there exists a vertex v such that v exists in V and v does not exist in mst do
    let v =     Q.findMin()
    Q.removeMin()
    for vertex u that exists in neighbors(v) do
        if v does not exist in mst then
            if weight(u, v) < Q.getPriority(u) then
                //TODO: What goes here?
            end if
        end if
    end for
end while
return mst

//TODO 中的内容

Answer 1

待办事项是

Q.setPriority(u) = weight(u, v);

此外，您的队列效果不佳。除 s 之外的节点的优先级应初始化为 ∞。

作为伪代码，我在下面重写了它：

MST-PRIM(G,w,s)
    for each u in G.V
        u.priority = ∞
        u.p = NULL //u's parent in MST
    s.key = 0
    Q = G.V // Q is a priority queue
    while(Q!=∅)
        u = EXTRACT-MIN(Q)
        for each v in u's adjacent vertex
            if v∈Q and w(u,v) < v.priority
                v.p = u
                v.priority = w(u,v)

你可以在 Introduce to Algorithm 的第 23.2 章找到它的原型。