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

Question

正如我的问题所说,我想知道为什么我们在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(); 作为存储边缘的优先级队列.

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)时间.