问题标签 [prims-algorithm]

“因此，Prim 算法的总时间为 O(V lg V + E lg V) = O(E lg V)，这与我们实现 Kruskal 算法的渐近相同。”

来自http://serverbob.3x.ro/IA/DDU0137.html

但是为什么 O(V lg V + E lg V) = O(E lg V) ？

是因为 E 至少是 V-1 吗？

对于编程作业，我正在实现 Prim 算法，测试用例的输入文件格式如下：

输入的第一行将是一个整数 C，表示测试用例的数量。每个测试用例的第一行包含两个整数 N 和 E，其中 N 表示图中的节点数，E 表示边数。然后是 E 行，每行有 3 个整数 I、J 和 P，其中 I 和 J 表示边的节点（无向图，其中 0 ≤ I, J

尽管即使我正在启动代码（我是编程新手），但我不明白为什么我的代码只读取测试用例的条目，我做错了什么？

这是读取文件 entradaA.in 的代码：

输入文件 (entradaA.in) 看起来像这样

正如我的问题所说，我想知道为什么我们在Prim 算法中使用优先队列？它如何使我们免于使用幼稚的方式（是的，我听说过，但不知道为什么）。

如果有人可以逐步解释邻接列表，我将非常高兴。我正在使用 Cormen 的书。

伪代码：

我正在考虑使用 std::vector 然后 std::make_heap(); 作为存储边的优先级队列。

谁能提供这两种算法的一些应用程序，它们可以用于哪些应用程序和哪些应用程序？

我正在尝试将 Prim 算法与boost 库的prim_minimum_spanning_tree函数一起使用，使用包含我所有图形点的文件。我使用boost 库的kruskal_minimum_spanning_tree函数成功创建了我想要的图形。

但是使用prim_minimum_spanning_tree我只能得到每个点的直接父级，所以我的图表不完整。

我使用了 boost 文档中给出的示例：

对于 prim： http: //www.boost.org/doc/libs/1_47_0/libs/graph/example/prim-example.cpp

和克鲁斯卡尔一个http://www.boost.org/doc/libs/1_47_0/libs/graph/example/kruskal-example.cpp

一个具体的例子：我有这个点文件：

使用我得到的 krukal 函数：

使用 prim 函数，我得到：

我有那些图的绘图，但我不能发布图像也不能发布几个链接。但正如你所见，我错过了 3 个链接。

如何使用 prim 函数获得与 kruskal 相同的结果？

谢谢，

PS：我使用示例的代码作为基础并尝试了一堆修改但没有成功，在网络或文档上找不到任何有用的信息。

有谁知道更改 prim 的算法如何处理未连接的图？我知道我必须使用森林，但我不知道如何在 Haskell 中实现它。

我最近使用 MS Prism 开始了一个新项目。在我的一个 UI 模块中，我有资源文件，我需要将它们添加到应用程序资源字典中。所以我编写了这段代码来做到这一点：

在我的资源文件中，我有 Datatemplate 的 Setter，它看起来像这样：

问题是在加载资源文件时抛出“'System.Windows.Setter'的初始化引发异常。” 但是当我删除这个设置器时，它工作正常。任何想法？

所以我需要一些帮助来找到一个最小生成树。假设我有邻接列表形式的图表：

第一个字母表示您正在查看哪个节点，数字表示与任何其他节点的连接数。例如，A 有两个连接 - B 和 I 各有一个。之后，字母后面的数字只是表示边的权重。B 的权重为 12，我的权重为 25。所以我最初计划将整个事物表示为一个名为 的字符串数组Graph[8]。每行将是阵列中的不同插槽。我很难弄清楚如何使用 Prims 或 Kruskalls 算法来实现这一点。

我正在尝试在 javascript 中创建一个随机迷宫生成器。

那里可能已经有工作示例，但我正在尝试自己解决这个问题（嗯，尽可能多）

我遇到的问题是我的脚本只运行了几个块然后停止。

我认为问题在于我对我所遵循的解释的理解（来自这个维基百科页面http://en.wikipedia.org/wiki/Maze_generation_algorithm）

该算法是 Prim 算法的随机版本。

1. 从一个充满墙壁的网格开始。

2. 选择一个单元格，将其标记为迷宫的一部分。将单元格的墙壁添加到墙壁列表中。

3. 虽然列表中有墙：

   1. 从列表中随机选择一面墙。如果对面的牢房还没有进入迷宫：

      1. 使墙壁成为通道，并将另一侧的单元格标记为迷宫的一部分。

      2. 将单元格的相邻墙添加到墙列表中。

   2. 如果对面的牢房已经在迷宫中，则将墙从列表中删除。

正如我所强调的那样，我的问题是与此相反的 部分。这是否意味着我们墙列表中的任何相邻单元格？还是有别的意思？

我已经用相邻的单元格尝试过它，它最终只是把自己挡住了。

任何想法，将不胜感激。

如果我能让它工作，我会在完成后发布代码。正如我所说，在获得完整解决方案的帮助之前，我想自己走得更远。

JAVA中的MST算法有问题吗？

我正在尝试在 java 中为 MST 编写代码

在这里，图已经给出，我正在尝试编写 addCheapest 方法来添加节点（不在路径上），当添加到路径中时，在某个位置，最小化路径在图中所有节点和所有位置的成本可以添加它们；将其添加到该位置。

}*