普里姆算法節點優先級

Question

所以我得到這個僞代碼爲Prims算法，

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

TODO是

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

再說，你不要排隊工作不好。除s之外的節點的優先級應初始化爲∞。

爲僞代碼，我rewrited它下面：

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) 

你可以找到它的原型在介紹到算法chapter23.2。