python - 使用 Prim 算法和优先队列？

Question

我正在使用 Prim 算法和优先级队列解决图表。我得到了一个包含处理边和图形本身的代码的类。我还需要使用优先级队列来查找最小生成树。

各位大佬遇到这样的问题怎么解决？您会获取每个节点的所有边，将其放入优先级队列，然后从那里开始吗？

Answer 1

对于 Prims 算法，我的优先级队列有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)