使用Prim算法優先隊列？

Question

我的工作解決在使用Prim算法和優先級隊列的圖表。我已經得到了一個包含處理邊和代碼本身的代碼的類。我還需要使用優先級隊列來查找最小生成樹。

會如何你們去解決這樣的問題？你會得到每個節點的所有邊緣，把它放入優先級隊列，然後從那裏出發？

Answer 1

對於普里姆算法，我的優先級隊列有pairs (weight, vertex)，重量排序。 這是僞代碼。請注意，如果某個頂點的邊緣優於所有遇到該邊緣的邊緣，則只需將邊緣添加到優先級隊列即可。

key[v] = Infinity for all vertex v 
vis[v] = false for all vertex v 
Q.Push(0, 1) // weight 0, and 1 is a valid vertex 
while (Q is not empty) : 
    curV = first element of Q 
    curW = second element of Q 
    Q.pop 
    if (vis[curV]) continue 
    add curV to spanning tree 
    for u in adjacency list of curV : 
    if (not vis[u] and key[u] > weight(u, v)): 
     Q.push(u, weight(u,v) 
     key[u] = weight(u,v)