c++ - 为什么我们需要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();作为存储边的优先级队列。

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