我试图理解为什么Prim和Kruskal在处理稀疏图和密集图时具有不同的时间复杂度。在使用了几个演示它们如何工作的应用程序之后，我仍然对图的密度如何影响算法感到有些困惑。希望有人能给我指点方向。

I希望使用Prim算法创建迷宫。我已经成功地完成了这个任务，但现在我正在尝试通过改变选择潜在单元格加入迷宫的方式来使它更加“困难”。在我看来，“困难”处于两个极端之间： 极端＃1是完全随机选择潜在通道列表中的单元格，在该列表中每个分支以大约相等的速度发展。这有很多不同的分支，但一旦到达起点，...

我正在使用邻接矩阵，优先队列是数据结构。 经过我的计算，复杂度为V^3 log V: While循环：V 检查相邻顶点：V 检查队列是否已存在并更新：V log v 但是，我到处都看到复杂度是V^2 请解释一下。

作为我的问题所述，我想知道为什么在Prim's Algorithm中使用优先队列？它如何避免我们使用幼稚的方法（是的，我听说过，但不知道为什么）。 如果有人能逐步解释邻接表，我会非常高兴。我正在使用Cormen的书。 伪代码： Prim(G,w,r) //what is w (weigh...

有人能为我解释一下，为什么Prim算法使用邻接矩阵会导致时间复杂度为O(V2)？