问题标签 [prims-algorithm]

我正在编写 Prim 算法的实现，用于派生最小生成树。我的图表是Map<String, ArrayList>其中它们的键对应于状态名称，值是保存指向两个链接的指针的边。

Prim 算法说我应该从只包含起始节点的树开始，然后循环直到我的树等同于我的图。如何确定 aTreeMap<String, ArrayList>和的等价性Map<String, ArrayList>？

以下是我使用 Prim 算法将连通图转换为 MST 的伪代码。然而，我得到的复杂度是 n^3 而不是 n^2。请帮我找出不需要的步骤。我有一个邻接矩阵“a”来存储图边的权重，一个二维矩阵“检查”存储树中已经存在的顶点“1”和剩余的“0”。

另请注意，这也可以在 nlog(n) 中完成，但我不想引用任何现有的伪代码并想自己尝试。我将不胜感激优化我自己的方法的答案。

我知道 Prim 算法和 Dijkstra 算法之间的区别。前者产生一个 MST，而后者给出从源到所有节点的最短路径。从数学上讲，它们并不相同，因此我们并不总是期望这两种算法产生相同的结果。

但是，在尝试不同的示例时，我得到了相同的结果。Prim 算法和 Dijkstra 算法的伪代码看起来也非常相似。有人可以给我一个例子，其中 Prim 产生的 MST 在使用 Dijkstra 解决时无法获得，反之亦然。

另外，据我所知。这两种算法都使用以下方法。如果我错了，请纠正我：

找到最短的 ij，其中 i 来自已包含的集合和 j 来自尚未包含的集合，然后将 j 添加到集合中。

这个程序给了我最小生成树的权重和到起始节点的最长距离..但是在输入测试用例的数量和顶点数和边数后，它需要两条边和它们的权重，它给出了一些垃圾值。为什么?

该程序编译完美。它给两个以上的边缘带来了问题。我只是不知道为什么。谢谢

如何在斐波那契堆上的递减键操作中获得 O(1) 摊销复杂度？仅使用 BFS 在斐波那契堆中找到包含该元素的节点需要 O(n) 时间，这应该使得不可能获得 O(1) 摊销时间。

作为参考，这是我搜索相关节点的 BFS 实现：

这是我的减少键代码：

我已经编写了一个程序来实现 prims 的算法，但它没有按应有的方式工作。优先级队列上的顶点正在发生变化，一个顶点甚至没有改变它的权重和父级。

代码是

输出是：

虽然我正确的 MST Kruskal 算法的输出是

在评估代码时，我发现堆没有正常工作。当顶点 5 被提取时，它的权重是 4，父节点是 -10，这不应该发生，好像重量减少应该有一个父节点。并且此时其他顶点与相应的父节点的权重错误。

编辑：问题似乎出在 heapdecrease 函数中。因为如果我在遍历邻接列表后调用 buildminheap。然后我得到正确的结果。尽管据我所知 heapdecrease 函数是正确的，但它是错误的。

我发现 Prims 算法的时间复杂度无处不在O((V + E) log V) = E log V。但正如我们可以看到的算法：

时间复杂度似乎是O(V(log V + E log V))。但是如果它的时间复杂度是O((V + E) log V)。那么嵌套必须是这样的：

但是上面的嵌套似乎是错误的。

这是一道古老的考试题。

在 (V, E) 的什么条件下，我们应该使用数组（由顶点索引）而不是堆（Extract-Min 和 Decrease-Key 操作的对数时间实现）来实现 Prim 算法的最小优先级队列)?

在 (V, E) 的什么条件下，我们应该使用有序数组来实现 Prim 算法的最小优先级队列？

我正在尝试使用 prim 算法创建一个最小生成树，但我对实际堆有一个主要问题。我将我的图形邻接列表构造为顶点向量，每个顶点都有一个边向量。边包含权重、连接顶点和键。我不确定我的堆是否应该是一堆顶点或边。如果我将其设为顶点堆，则无法确定权重是否来自相同的父顶点和目标顶点，这使我认为我应该为每个顶点的边列表创建一个堆。所以我的最后一个问题是我应该创建一堆边还是一堆顶点？如果它是一个边列表，我应该使用边上的权重作为键，还是应该有一个单独的数据成员，称为键，我可以实际用于优先级队列？谢谢！

我必须使用基于最小堆的优先级队列来实现 Prim 算法。如果我的图包含顶点 A、B、C 和 D 以及下面的undirected邻接列表... [它被排序为（顶点名称，相邻顶点的权重）]

粗略图：

优先级队列会是什么样子？我不知道我应该在里面放什么。我应该把所有东西都放上去吗？我应该只放ABC和D吗？我不知道，我真的很想要一个答案。