问题标签 [prims-algorithm]

我正在查看 Prim 算法的Wikipedia 条目，我注意到它与邻接矩阵的时间复杂度为 O(V^2)，而其与堆和邻接列表的时间复杂度为 O(E lg(V))，其中 E 是边数和 V 是图中的顶点数。

由于 Prim 算法用于更密集的图中，E 可以接近 V^2，但是当它接近时，堆的时间复杂度变为 O(V^2 lg(V))，大于 O(V^2)。显然，与仅搜索数组相比，堆将提高性能，但时间复杂度另有说明。

算法实际上是如何随着改进而变慢的？

对于我的 CS 类，我需要在 Java 中实现 Prim 算法，并且我在优先级队列步骤中遇到问题。我有优先级队列的经验，并且了解它们通常可以工作，但我在某个特定步骤时遇到了麻烦。

我创建了一个包含键值（我假设它是连接到节点的最轻的边缘）和父节点的节点类。我的问题是我不明白将节点添加到优先级队列中。当父节点设置为 NIL 并将键设置为 ∞ 时，将所有节点添加到优先级队列对我来说没有意义。

我想知道什么时候应该使用Prim 的算法，什么时候使用Kruskal 的算法来找到最小生成树？它们都有简单的逻辑，相同的最坏情况，唯一的区别是实现可能涉及一些不同的数据结构。那么决定因素是什么？

我使用的伪代码：

根据我的理解：

• 第 1 行：执行V-1次数。
• 第 2 行：所有顶点的度数之和时间......即2E时间

对于第 2 行：第 3 行和第 4 行需要时间，因为我们正在逐一log E添加/删除所有边缘。PQ

所以总计time= V-1+2E.logE=E.log E

但是书上说是这样E.logV，你能解释一下为什么会这样吗？

我已经在 C (www.bubbllellicious.es/prim.tar.gz) 中实现了Prim 的算法，但我只是想知道如何将其转换为Kruskal 的算法。

看起来它们非常相似，但我无法想象如何将旧代码修改为新代码。给点建议什么的就好了。我知道这很容易，但我仍然是 C 编程的 n00b ......

JGraphT有一个很好的斐波那契堆类。如何使用它来实现Prim 的最小生成树算法？

我正在尝试用 JGraphT 实现 Prim 的最小生成树算法。它看起来怎么样？

我遇到的一个问题是 JGraphT 对所有事情的处理方式都像它所指示的那样。所以有时有必要做出一些尴尬的调用来逆转g.getEdgeSource(e)，g.getEdgeTarget(e)如果他们没有碰巧是正确的。

我最初尝试使用 JGraphT 的 Fibonacci Heap 来实现这一点，但它太难了，所以我只是做了一个常规的 PQ。

我没有将不存在的边的权重设置为无穷大，而是没有将其添加到队列中。

建议？风格问题？明显的低效率？我应该使用的代码而不是我自己的代码？

我直观地觉得，如果使用 Prim 的算法来查找图的最小生成树，那么选择哪个根节点都没有关系 - 生成的 MST 无论如何都会具有相同的权重。这个对吗？

我一直在学习 Cormen 等人的书，我对他们提供的算法有点困惑。我已经通过维基百科了解 Prim 算法的概念是如何工作的，但我无法使用我书中提供的算法来模仿这种工作方式。

请参阅本章的在线副本： http ://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf

算法在上述链接的第 13 页给出，示例图在前一页。

现在，在示例案例中使用算法，在第一步中：

u <--- 节点 A 到 ExtractMin(Q)。然后根据图表在 Adj[u] 中有两个条目：节点 b 和节点 h。

现在首先设置 v <---- 节点 b。然后检查 v 是否属于 Q。确实如此。检查是否 w(u,v) < key[v]。真的。所以 PI[v] <--- u 和 key[v] <--- w(u, v)。我得到了这么多。这显示在第 12 页图表的 (b) 中。

但是算法说“对于 Adj[u] 中的每个 v”。

所以下一步应该设置v <---节点h。然后检查 v 是否属于 Q。确实如此！w(u,v) < key[v]？这是！因为 key[v] = 无穷大！但是该图显示了 (c) 部分的不同步骤！

啊啊啊！为什么？

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