6

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

如果有人可以逐步解释邻接列表，我将非常高兴。我正在使用 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(); 作为存储边的优先级队列。

4

4 回答 4

11

在 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 描述了一个最小生成树

于 2011-08-12T11:08:49.367 回答
6

你不需要它。事实上，Prim 算法的简单实现会简单地对距离数组进行线性搜索以找到下一个最近的顶点。Dijkstra 算法的工作方式完全相同。

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

关键是EXTRACT-MIN(Q)功能。如果您天真地进行操作，则此操作将需要O(V)时间。有了堆，只需要O(logV)时间。

于 2011-08-12T12:03:50.533 回答
4

大致从记忆中执行此操作，因此可能略有不一致，但它传达了要点：

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)

基本上，在算法的每一步，你都在寻找最小边，其中一个顶点在部分最小生成树中，一个顶点不在树中，你将把所说的边添加到树中。你如何有效地做到这一点？如果您有一种方法可以有效地对连接到部分生成树中某个顶点的所有边进行排序，则可以简单地遍历它们，直到找到具有可接受顶点的边。

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

于 2011-08-15T02:46:07.190 回答
1

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

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

在实现中，它们最初将每个顶点添加到具有 INFINITY 优先级的队列中，但它们会逐渐更新权重，如您所见。这也反映在优先级队列中，保证上面的文本。

希望能帮助到你。

于 2013-06-28T19:26:38.950 回答