使用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)