问题标签 [kruskals-algorithm]

当图形具有多个连通分量时，我不确定如何实现 Kruskal 算法

根据我对 Kruskal 算法的理解，它反复将最小边添加到集合中。然后，当检查所有边时，它会返回最多的边集。

但是，如果我的图表断开连接怎么办？说我有：

假设 Cost( A - B ) = Cost( E - F ) = 1，其余边大于 1

当我运行 Kruskal 时，我会得到所有边缘的成本，但我想得到每个连接组件的成本，所以我对所有连接组件进行平均最小成本。

我有一个给定图表的最小生成树（MST）。我正在尝试为任何两个顶点计算唯一的子路径（它应该是 MST 的一部分，而不是图形），但我很难找到一种有效的方法。

到目前为止，我已经使用 Kruskal 的算法（使用不相交数据结构）来计算 MST（例如：10 个顶点 A 到 J）.. 但是现在我想计算 C 到 E.. 或 J 到 C 之间的子路径（假设图是无向的）。

任何建议，将不胜感激。

我在 C++ 中实现了 Kruskal 算法（使用不相交的数据集结构）。我试图找到为算法的总运行时间创建更坏情况测试用例的可能方法。然而，当我尝试创建测试用例时，我对什么会使算法导致最坏的情况感到困惑，并且想知道这里是否有人可能知道真正让 Kruskal 的算法陷入困境的可能场景。

到目前为止，我认为理论上可能测试 Kruskal 算法界限的主要测试将是所有权重都相同的测试用例。一个例子如下：

我最终遇到的是，无论我做什么，如果我试图减慢算法的速度，我最终会没有最小生成树，最终无法实际测试算法的边界。

在网格中生成迷宫的最佳算法是什么？

我听说过 Kruskal 的算法和递归回溯器等，但它们都依赖于墙壁。在整个细胞是墙壁的情况下，创造惊奇的最佳算法是什么？

我在浏览网站时注意到了这张照片。

在我看来，这是错误的，

如您所见，ES、GI、DF、EF 在这张图片中作为前 4 个给出。

不应该是ES，GI，DF，DS吗？

它应该是按词汇顺序排列的，那为什么它被标记为正确答案？我错过了什么？

PS，这是我大学的考试题之一。

我必须在 boost 库中使用 kruskals 算法来找到最小生成树的权重。我想我成功了

现在我需要找到顶点 0 和离它最远的那个之间的距离（权重总和）？关于我该怎么做的任何提示？

我正在考虑使用顶点迭代器，但后来我将权重存储在 weightMap 中，那么如果我遍历图形的顶点，我该如何访问它？

编辑：我修改了我的程序，决定使用 kruskal 和 prim

1.kruskal 用于生成树权重 2.prim 算法用于每个顶点到顶点 0 的距离（在生成树中存储在地图距离中）

不幸的是，出了点问题，距离 [*vertex] 是第三个顶点并没有给出答案 2，而是给出了一个

生成树的权重也是 14 而不是 7

我的虚拟输入是：

这是我的程序：

谢谢你 ：）

我正在尝试为 Kruskal 实施联合查找算法。我正在使用这个伪代码，我不理解下面的联合部分 step2（它不是递归调用），或者我什至很接近。如果这种方式不起作用，只要我理解它，我可以使用任何实现。提前谢谢。U 和 V 是我的边缘节点，现在只是整数。

我不明白第 2 步，到目前为止，这是我的代码：

我有点卡在这个程序上。到目前为止，我有一个用于图形的 Edge 对象。这个边缘对象需要一个权重和两个顶点对象。我为 Vertex 对象创建了一个类，并为 Edge 对象创建了一个类：

顶点：

Vertex 接受一个 Key 对象，它只是一个字符串和一个数字。

边缘：

当我尝试声明一个 Edge 对象时，它工作得很好。但是，当我创建第二个对象时，它会“覆盖”第一个对象。

当我调用方法来打印键的值（在本例中为 A 或 E）时，它工作得很好。但是，当我这样做时：

CD基本上覆盖了AE。所以当我试图从 AE 中得到“A”时，我得到 C。当我试图得到 E 时，我得到 D。

我已经在这个程序上停留了一段时间（其中有各种不同的问题），但对于我的生活，我无法弄清楚它为什么会这样做。谁能指出我的错误？

我正在实施 Kruskal 的算法。

在下面的代码中调用 graph() 后，节点的值发生了变化。我不太清楚为什么——如果有人能澄清这一点，我将不胜感激。我没有从图中访问节点的值，并且正在访问的数组的节点和边都分配在堆栈之外！

I was doing an analysis of minimum spanning trees and was wondering how the sorting time would effect the overall time complexity of Kruskal's algorithm?

Example:

1. If sorting can be done in O(n log log n)
2. If sorting can be done in O(n)

Would the answer still remain O(e log n) for both the cases or would it change?