就我的问题而言，我想知道为什么我们在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();作为存储边缘的优先级队列。
最佳答案
在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描述了最小生成树