问题标签 [kruskals-algorithm]

我使用 Kruskal 算法生成了一个最小生成树，我想知道如何存储路径

这是我的最小生成树

我使用 Kruskal 算法生成了这个最小生成树，我很难在两个节点之间生成路径。有人可以帮我处理伪代码吗？我尝试使用邻接列表和邻接矩阵

我必须生成简单的无向图，以在其上测试我的 Kruskal 算法。我有一个所有连接的结构，如下所示：

现在我需要生成相当数量的这些连接，以测试 Kruskal 的情况。Kruskal 的算法并不比这一代人难，可能是因为这是我第一次面对 Graphs。

JAVA中的MST算法有问题吗？

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

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

}*

谁能想出一种方法来修改 Kruskal 的最小生成树算法，使其必须包含某个边（u，v）？

所以我有一个任务，我能够编写一个代码并且它可以工作，但是对于大数字它太慢了，也许你可以帮助我改进它，时间限制是 3s。我想听听一些想法。在这个作业中，我们必须找到最小生成树。

输入将是：

那么输出应该是最小值。MST 的距离，如果没有 MST，则输出应为 -1。

这是一个例子：

这是代码：

我想在 C++ 中实现 Kriskal 的算法，但是......

DAA.exe 中 0x0127160d 处未处理的异常：0xC0000005：访问冲突读取位置 0xdd2021d4。

它在 getRoot 函数的这一行停止：

而（城市[根].prev！= NO_PARENT）

我认为问题在于城市数组中的数据。当我打印数组中的所有数据时，这不是我想要的。城市的名称是这样的“════════════════¤¤¤¤ллллллю■ю■”和数字（int） - 像这样（-842150451）。以下是完整代码。

以下是我们 CS 算法讲师的 Kruskal 最小生成树算法的伪代码。我想知道 MST 算法是否是不确定的。给定具有相同权重的两条边，如果在添加到 T 时没有一条边形成循环，算法将如何在它们之间做出决定。当然，如果它是随机的，那么我们无法确定将哪些确切边添加到 T 的结果？

谢谢！

Given an undirected connected graph with weights. w:E->{1,2,3,4,5,6,7} - meaning there is only 7 weights possible. I need to find a spanning tree using Prim's algorithm in O(n+m) and Kruskal's algorithm in O( m*a(m,n)).

I have no idea how to do this and really need some guidance about how the weights can help me in here.

令 G = (V,E) 为无向图。如果 G 的每个循环在 F 中至少有一条边，则一个边集 F ⊆ E 称为 反馈边集。

(a) 假设 G 未加权。设计一种有效的算法来找到最小尺寸的反馈边集。

(b) 假设 G 是一个带正边权重的加权无向图。设计一个有效的算法来找到一个最小权重的反馈边集。

我的解决方案（需要建议）：

a)最小尺寸反馈边集：由于图是未加权的，我们可以使用 DFS。我们像往常一样从任何顶点开始 DFS。当我们遇到一个后边缘时，我们将它插入到一组反馈边缘中。当 DFS 完成时，集合将是答案。

b)最小权重反馈边集：由于图是加权的，我们可以使用 Kruskal。但克鲁斯卡尔通常从重量最小的边缘开始。如果我们可以否定所有边权重，然后运行 ​​Kruskal，每当我们在同一组件的顶点之间获得一条边时，我们可以将其保存在反馈边集中。最后，否定边缘权重。我建议否定边缘权重的原因是因为我们需要最小的权重反馈集。使用否定权重，Kruskal 将从具有最小权重（实际上是最大）的边开始，并会找到具有较小权重的相同组件的边。

有人可以判断这个解决方案是否正确吗？