Prim算法中为什么需要优先级队列

Question

正如我的问题所说，我想知道为什么我们在 Prim 算法？ 它如何使我们免于使用幼稚的方式（是的，我听说过，但不知道为什么）。

如果有人可以逐步解释邻接表，我将非常高兴。我正在使用科门的书。

伪代码：

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();作为存储边的优先队列。

Answer 1

在 prim 的算法中，有一个步骤你必须获得“最近”的顶点。如果使用普通数组，此步骤将花费 O(N)，但如果使用优先级队列（例如堆），则只需要 O(logN)

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

**

更新：

**

这是 Prim 算法的描述，来自 维基百科。粗体部分是我讲的寻找最近顶点的部分：

输入：一个非空连通带权图，顶点为V，边为E（权重可以为负）。

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

重复直到Vnew = V：
选择权重最小的边 (u, v)，使得 u 位于 Vnew 中而 v 不在（如果存在多个具有相同权重的边，则可以选择其中任何一个）
将 v 添加到 Vnew，并将 (u, v) 添加到 Enew

输出：Vnew 和 Enew 描述最小生成树

Answer 2

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

人们使用它的原因是它显着加快了算法的运行时间。它从 O(V^2 + E) 变为 O(E*log(V))。

关键是 EXTRACT-MIN(Q) 函数。如果您天真地这样做，此操作将花费 O(V) 时间。对于堆，只需要 O(logV) 时间。

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)

基本上，在算法的每一步中，您都在寻找具有部分最小生成树中的一个顶点和一个顶点的最小边不在树中，并且您要将所述边添加到树中。你如何有效地做到这一点？如果您有办法有效地对部分生成树中连接到顶点的所有边进行排序，则可以简单地迭代它们，直到找到具有可接受顶点的边。

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

Answer 4

Prim 的算法使用两个集合 - 比如说 U 和 V/U。

您从根开始（根是 U 中唯一的元素）。
您将与其相邻的所有顶点放入队列中，其中weight[v] = dist[root,v]，其中v与root相邻。
因此，当您从队列中弹出时，您将获取一端位于 U 且一端位于 V/U 且具有该属性的最小顶点（假设为 u）。
你设置它的权重，它的父节点是根等等......并将它的所有 ajdacent 节点放入队列中。因此，现在队列具有与 root 关联的所有节点、与 root 关联的所有节点以及与 u 关联的所有节点及其各自的权重。 因此，当您从中弹出时，您将再次从 V/U 中获得一个距离 U “最近”的节点。

在实现中，他们最初将每个顶点以 INFINITY 优先级添加到队列中，但正如你所看到的，他们正在逐渐更新权重。这也反映在优先级队列中，保证了上面的文本。

希望有帮助。