问题标签 [prims-algorithm]

我想知道 dijkstra 和 prim 的算法，当他们在多个顶点之间进行选择时会发生什么，并且有多个顶点具有相同的权重。

例如

示例图片 http://img688.imageshack.us/img688/7613/exampleu.jpg

Prim 的 MST 算法的时间复杂度是O(|V|^2)如果您使用邻接矩阵表示。

我正在尝试使用邻接矩阵来实现 Prim 的算法。我用这个 作为参考。

编辑：

1. 我非常了解 Prim 的算法。
2. 我知道如何使用堆和优先级队列有效地实现它。
3. 我也知道更好的算法。
4. 我想使用图形的邻接矩阵表示并获得 O(|V|^2) 实现。

我想要低效的实施

嘿，我写这个（fortran）的目的是找到一堆点的最小生成树（它们的syscount）。我知道这种方法有效，因为我今天早些时候用 javascript 编写了它。虽然 js 很慢，但我想看看 fortran 会快多少！！唯一的问题是它不起作用，我遇到了一个烦人的错误；

prims.f95:72.43:

if((check == 1) .and. (path(nodesin(j))(k) < minpath)) 然后

错误：在 (1) 处的表达式中应有右括号

这到底是怎么回事？！该行的第 43 个字符是“路径”的“h”

另外，我对fortran还很陌生，所以我还有其他一些问题；

我可以用 && 代替 .and 吗？?

是否有许多其他语言版本的 for(object in list){} 循环？

是否有 php 函数 in_array 的版本？即 bool in_array(needle,haystack)，如果有，是否有比以下更好的方法：

然后使用检查变量来查看它是否存在？

（我之前没有在stackoverflow上发布过任何东西。如果我违反了很多礼仪，请不要生气！）

可能的重复：
Kruskal vs Prim

krukshal 算法或 Prims 算法哪一个更适合找到最小生成树？

我可以编写 Prim 和 Kruskal 的算法来在 C++ 或 Java 中找到最小生成树，但我想知道如何在 Haskell 中用 O(mlogm) 或 O(mlogn) 实现它们（纯函数程序更好）。非常感谢。

请建议资源来学习如何使用 Prim 算法在有向图中找到最小生成树，以及使用 Bellman-Ford 算法来计算有向图中的最短路径。

任何人都可以帮助我如何使用 PRIM 算法查找 MST。突出显示 MST 的边缘并写下将节点添加到 MST 的顺序。谢谢

我知道Prim 的算法，也知道它的实现，但我总是跳过我现在想问的部分。有人写道，Prim 的斐波那契堆算法实现是O(E + V log(V))，我的问题是：

• 简而言之，斐波那契堆是什么？
• 它是如何实施的？和
• 如何用斐波那契堆实现 Prim 算法？

我整天都在努力理解 Dijkstra 的算法并实施，但没有取得显著成果。我有一个城市及其距离的矩阵。我想要做的是给定一个起点和一个终点，找到城市之间的最短路径。

例子：

我开始想知道是否有其他方法可以解决这个问题。如果我从原点应用 Prim 算法，然后循环遍历创建的整个树，直到找到目标点会怎样？

我如何描述一组具有 V 顶点和 E 边的图，其中确认 Prim 算法的优先级队列实现的最坏情况运行？