问题标签 [minimum-spanning-tree]

今天，由于这张幻灯片的第 13 页，我与某人讨论了 Kruskal 最小生成树算法。

该演示文稿的作者说，如果我们使用（双）链表实现不相交集，则性能为Make和Find的性能将分别为O(1)和O(1)。运算Union(u,v)的时间为min(nu,nv)，其中nu和nv是存储 u 和 v 的集合的大小。

我说过我们可以通过使每个成员的表示指针指向一个包含指向集合的真实表示的指针的定位器来将Union(u,v)的时间缩短为O(1) 。

在 Java 中，数据结构如下所示：

对不起，简约的代码。如果可以这样制作，那么每个不相交集操作（Make,Find,Union）的运行时间将是O(1)。但与我讨论过的人看不到改进。我想知道你对此的看法。

Find/Union 在各种实现中的最快性能是什么？我不是数据结构方面的专家，但是通过在互联网上快速浏览，我发现没有恒定时间数据结构或算法可以做到这一点。

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

如果生成树 T0 的任何边包含在某个最小生成树 T* 中，这是否意味着 T0 也是最小生成树？

现在，我试图在纸上画一些图表来证明它不是。如果有，请纠正我，如果没有，请帮我找一个例子。

提前致谢。

请帮助我了解如何从图的邻接矩阵中获得最小生成树！我用java写了关于它的课程，截止日期是16.12.2010，但我觉得它会失败。现在我的程序可以：

1. 绘制节点
2. 绘制边缘
3. 在绘图的地下室生成图形的邻接矩阵，边的权重
4. 找到连接到节点的最小边
5. 并具有其他一些测试/测试功能

但我不知道如何在 Java 中实现 Prim / Kruskal 算法。我尝试在谷歌中找到一些解决方案，但只找到需要工作 .obj 文件的 Java-applet，我也无法运行它。

我编写了一些简单的控制台 java 模式，现在可以生成和打印图形的邻接矩阵。任何人都可以添加返回图的最小生成树的邻接矩阵的函数，如下所示：

在哪里：

• graph - 在 n 中生成图
• 顶点数量（节点）

提前致谢！

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

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

可能重复：
所有最小生成树实现

如何以有效的方式在无向图中找到所有最小生成树？

这是元旦，仍然无法解决我关于生成树算法的问题。我还不能插入图片，所以我不得不尝试用文字来解释环境。

它有 36 个节点，到每个节点的距离是均匀的。问题是如果距离是均匀的，那么从 ID 为 1 的节点（根）到最后一个 ID 为 36 的节点以哪种方式传递消息并不重要。因为距离是均匀的，所以没有节省时间、节能或消息保存算法对吗？我希望有人能理解我的问题

编辑：

1. 环境

   /li>

这是我选择的生成树。ID 为 36 的节点通过 30,24,18,12,6,5,4,3,2,1（一个是根）向其发送信息，然后节点 1 向基站发送信息。因为它没有任何成本，所以我选择哪条路径将信息从节点 36 发送到节点 1 并不重要，因为成本仍然相同。

1. 我的生成树算法

   • 启动时，仅标记根。
   • 根向它的邻居发送搜索消息
   • 如果一个节点没有被标记，当它收到来自其他节点的搜索消息时：
   • 它标记自己
   • 选择ID最低的节点作为“父节点”，向其他节点回复“非父节点”
   • 如果节点已经被标记，它会回复“非父节点”
   • 如果一个节点已被标记并收到父消息，则它将发送者标记为子节点

2. 我不能向你们展示流程图，因为我没有插入图像的特权。

3. 伪代码（没做过）

4. 结论 - 在这里我应该写下我的算法的优点和缺点，但现在我想不出任何优点和缺点

我在某些度量空间（例如配备Jaccard Distance ）中有大量点（数量 n > 10000 ）。我想将它们与最小生成树连接起来，使用度量作为边缘的权重。

• 是否存在运行时间少于 O(n ² ) 的算法？
• 如果没有，是否有一种算法运行时间少于 O(n ² ) 平均时间（可能使用随机化）？
• 如果没有，是否有一种算法可以在少于 O(n ² ) 的时间内运行并给出最小生成树的良好近似值？
• 如果不是，是否有理由不存在这种算法？

先感谢您！

编辑下面的海报： 寻找最小生成树的经典算法在这里不起作用。他们的运行时间有一个 E 因素，但在我的情况下 E = n ²因为我实际上考虑了完整的图表。我也没有足够的内存来存储所有 >49995000 个可能的边。

我看过一个关于顶点覆盖问题（VC，已知 Np 完全问题）的 2 近似算法的问题，但我不知道答案。问题如下：使用“生成树”找到顶点覆盖问题的 2 近似算法。好吧，已经为 VC 提出了许多贪婪的方法，但是使用“生成树”的特殊算法具有挑战性。任何想法？