为什么在Prim算法中我们需要一个优先队列？

Question

作为我的问题所述，我想知道为什么在Prim's Algorithm中使用优先队列？它如何避免我们使用幼稚的方法（是的，我听说过，但不知道为什么）。

如果有人能逐步解释邻接表，我会非常高兴。我正在使用Cormen的书。

伪代码：

Prim(G,w,r) //what is w (weight?) and r?
  For each u in V[G]
    do key[u] ← ∞ // what is key?
       π[u] ← NIL  
  key[r] ← 0
  Q ← V[G]  
  While Q ≠ Ø
    do u ← EXTRACT-MIN(Q)
       for each v in Adj[u]
            if v is in Q and w(u,v) < key[v]
                 then π[v] ← u
                       key[v] ← w(u,v)

我在考虑使用std :: vector，然后使用std :: make_heap（）作为优先级队列来存储边缘。

- Mr.Anubis

---

这不是在书里解释了吗？ - Mitch Wheat

你会用什么替代优先队列？这对效率和正确性会有什么影响？ - outis

在这个伪代码中，您会在哪里添加到mstree？ - Alex Moore-Niemi

Answer 1

在Prim算法中，有一步需要获取“最近”的顶点。如果使用普通数组，这一步将花费O(N)的时间，但如果使用优先级队列（例如堆），这一步只需要花费O(logN)的时间。

因此，使用优先级队列的原因是为了降低算法的时间复杂度（这意味着它能让您的程序运行更快）。

**

更新：

**

这是来自Wikipedia的Prim算法描述。粗体部分是我提到的寻找最近顶点的部分:

输入: 一个非空连接的带权图，具有顶点V和边E（权重可以为负）。

初始化: Vnew = {x}，其中x是V中的任意节点（起始点），Enew = {}

重复直到Vnew = V: 选择一条具有最小权重的边（u，v），使得u在Vnew中而v不在（如果有多条相同权重的边，则可以选择任何一条） 将v添加到Vnew中，并将（u，v）添加到Enew中

输出: Vnew和Enew描述了一个最小生成树

- Chan Le

---

有一个步骤需要获取“最近”的顶点。你能告诉我最近顶点的意思吗？你是指最近的相邻顶点吗？因为当我们在图中进行切割时，我们谈论的是所有与集合A中的每个V相邻的顶点（安全边）。告诉我我理解得对吗？ - Mr.Anubis

我刚刚从维基百科添加了一些澄清内容，希望有所帮助 :) - Chan Le

Answer 2

你其实“不需要”它。事实上，Prim算法的一个天真实现只需对距离数组进行线性搜索即可找到下一个最近的顶点。Dijkstra算法的工作方式也完全相同。

人们使用它的原因是它显著加速了算法的运行时间。它从O（V ^ 2 + E）变为O（E * log（V））。

这个关键在于“提取最小值（Q）”函数。如果你天真地做，这个操作将需要O（V）的时间。但是使用堆，它只需要O（log V）的时间。

- tskuzzy

---

等一下.. extract-min(Q) <- 这不是常数时间吗？因为它只是从优先队列中取出第一个项目。 - Henley

不行，因为恢复堆结构需要 O(log V) 的时间。 - tskuzzy

Answer 3

我大致从记忆中完成这项任务，因此可能有些不一致，但它能够传达要点：

class Graph
  Set<node> nodes;   // The set of nodes in the graph
  MultiMap<Node, Edge> edges; // Map from Node, to a list of weighted edges connected to the node. If it weren't weighted, any spanning tree by definition would be a minimum spanning tree.

Graph Prim(Graph input):
   Graph MST = new Graph();
   PriorityQueue<Edge> candidateEdges;
   Node anyNode = input.pickAnyNodeAtRandom()
   candidateEdges.putAll(input.edges.get(anyNode));

   while MST.nodes.size() < input.nodes.size():
      edge = candidateEdges.takeLowest()  // THIS IS THE IMPORTANT PART         
      if edge.v1 in MST.nodes and edge.v2 not in MST.nodes:
         MST.nodes.add(edge.v2)       
         MST.edges.add(edge)
         candidateEdges.add(edge.v2.edges)

基本上，在算法的每个步骤中，您都在寻找与部分最小生成树中一个顶点相连、另一个不在树中的最小边，并将该边添加到树中。如何高效地完成此操作呢？如果您有一种有效地对连接到部分生成树中某个顶点的所有边进行排序的方法，那么只需通过迭代它们，直到找到一个带有可接受顶点的边即可。

如果没有这样的有序数据结构，您每次都必须遍历所有候选边才能找到最小值，而不能直接高效地获取最小值。

- James

---

非常好地解释了 :) 这是我在SO上找到的最好的解释之一。谢谢伙计 :D - Sushant Gupta

为什么我们需要找到最小值？无论如何，在创建父数组时，如果我们后来发现了一个最小值，我们就会进行更新。因此，即使我们在下一次迭代中选择了一个更大的值来替换最小值，如果后来发现了最小值，它也会被纠正。 - Arpan Banerjee

Answer 4

Prim算法使用两个集合，假设为U和V/U。

你从根节点开始（根节点是U中唯一的元素）。将所有与它相邻的顶点放入队列中，并设置权重[v] = dist[root,v]，其中v与root相邻。当你从队列中弹出时，你会取出一个顶点（假设为u），该顶点一端在U中，另一端在V/U中，并且具有这种属性的顶点最小。然后你设置它的权重，它的父节点为root等等，并将所有相邻节点放入队列中。现在队列中有所有与根节点相邻的节点以及所有与u相邻的节点，它们的权重也已经确定。因此，当你再次从队列中弹出时，你将得到一个距离U“最近”的V/U中的节点。

在实现中，他们最初使用无限大的优先级将每个顶点添加到队列中，但是随着你可以看到的权重逐渐更新。这也反映在优先队列中，保证了以上所述。

希望这有所帮助。

- George