问题标签 [kruskals-algorithm]

我正在尝试用 C++ 构建 Kruskal 算法并编写了其中的一部分，代码如下：

但是由于某种原因， vertex_sets 数组在 (int j = 0... 循环期间发生了变化，我不确定为什么会发生这种情况，因此打印语句。使用输入

我得到一个输出

这意味着由于某种原因，在循环的第四次迭代期间，索引 0 处的 vertex_sets 的值从 0 变为 3，我不知道为什么。任何人都可以看到为什么会这样吗？

如果使用 BFS 实现 Kruskal 算法来检查是否添加一条边并创建一个循环，那么该算法的整体 Big-O 运行时间是多少？

据说 Kruskal 的 MST 构造算法是贪心的，但该算法选择全局最小值，而不是像 Prim 算法那样选择局部最小值。有人可以解释一下 Kruskal 的算法是如何被认为是一种贪婪的方法吗？

如果对空间没有限制，考虑到图是稀疏的，那么选择执行 kruskals 算法的最佳数据结构是什么。

我正在考虑使用单链表实现

克鲁斯卡尔算法如下：

根据我的教科书：

在第 1 行初始化集合 A 需要 O(1) 时间，在第 4 行对边进行排序的时间是 O(E lgE)。第 5-8 行的 for 循环对不相交集森林执行 O(E) FIND-SET 和 UNION 操作。随着 |V| MAKE-SET 操作，这些操作总共需要 O((V+E)α(V)) 时间，其中 α 是一个增长非常缓慢的函数。因为我们假设 G 是连通的，所以我们有 |E| <= |V|-1，因此不相交集操作需要 O(E α(V)) 时间。此外，由于α(V)=O(lgV)=O(lgE)，Kruskal算法的总运行时间为O(E lgE)。观察到 |E|<|V|^2，我们有 lg |E|=O(lgV)，因此我们可以将 Kruskal 算法的运行时间重述为 O(E lgV)。

你能解释一下为什么我们推断在第 4 行中对边缘进行排序的时间是 O(E lgE) 吗？另外，我们如何得到总时间复杂度为 O((V+E)α(V)) ？

此外，假设图中的所有边权重都是从 1 到 |V| 的整数。你能让 Kruskal 的算法运行多快？如果对于某个常数 W，边权重是从 1 到 W 范围内的整数怎么办？

时间复杂度如何取决于边的权重？

编辑：

此外，假设图中的所有边权重都是从 1 到 |V| 的整数。你能让 Kruskal 的算法运行多快？

我想到了以下几点：

为了使 Kruskal 算法运行得更快，我们可以应用计数排序对边进行排序。

• 第 1 行需要 O(1) 时间。
• 第 2-3 行需要 O(v) 时间。
• 第 4 行需要 O(|V|+|E|) 时间。
• 第 5-8 行需要 O(|E|α(|V|)) 时间。
• 第 9 行需要 O(1) 时间。

因此，如果我们使用计数排序来解决边缘，Kruskal 的时间复杂度将是

你能告诉我我的想法是否正确吗？

还：

如果对于某个常数 W，边权重是从 1 到 W 范围内的整数怎么办？

我们将再次使用计数排序。算法将是相同的。我们发现时间复杂度如下：

• 第 1 行需要 O(1) 时间。
• 第 2-3 行需要 O(|V|) 时间。
• 第 4 行需要 O(W+|E|)=O(W)+O(|E|)=O(1)+O(|E|)=O(|E|) 时间。
• 第 5-8 行需要 O(|E|α(|V|)) 时间。
• 第 9 行需要 O(1) 时间。

所以时间复杂度为：

我正在尝试在 C++ 中实现 Kruskal 算法。我按照 youtube 视频中的说明进行操作，其中使用了矢量。尽管代码在视频中显示准确运行，但相同的代码甚至无法在我的 PC 中编译。我无法弄清楚问题所在。这是代码：#include #include using namespace std;

我说的是union-find-disjoint 数据结构。互联网上有很多关于如何实现这一点的资源。到目前为止，我已经了解了两种联合优化技术。第一个是通过变量 Rank 来“平衡”树，它表示最深节点的深度，因此是 find() 的上限。第二个优化是：设置一个对象的父节点为头节点，同时调用find()（设置中还包含了对象的父节点，所以变成了级联优化）。

但是，当实现同时使用它们两者时，它们通常会不加思索地将两者合并在一起。具体来说，GeeksforGeeks（仅作为示例，没有任何个人内容）这样做。这不会导致排名“损坏”和 O(log n) 复杂性吗？

例如，如果我有一长串节点（5 到 4 到 3 到 2 到 1 到 0，这是头部）并且我调用 find() 到 2，则排名保持 5，即使它应该是 3。

我正在实现 Kruskal 算法，我发现了这段代码：

我不知道真正的意思，请帮忙？:)

我有兴趣学习如何在 C++ 中在 O(n log n) 上运行 Kruskal 算法。我已经使用在 O(n^2) 上运行的解决方案实现了该算法，其代码如下。

我知道应该可以在 O(n log n) 上运行 Kruskal，但我不知道如何做到这一点。我将不胜感激任何和所有提示。

所以我需要解决这个图表，我对如何解决它有一个大致的想法，但如果我做错了，请纠正我。

所以要找到 MST 我需要在图上执行 Kruskals 算法

这是我的这个 Kruskals 算法的伪代码

克鲁斯卡尔(V,E) A = null; 对于每个 v 包含在 V 中，使不相交集 (v) 按权重对 E 进行排序，对于每个 (v1, v2) 包含在 E 中，如果

所以我要做的第一件事就是找到距离最短的节点，对吧？

1)

我假设 S 到 H 的距离最短，因为 d(h,s) = -3

所以 A = {(h,s)}

所以现在我们遵循这个模式

2) A = {(h,s),(s,f)}

3) A = {(h,s),(s,f)(s,n)}

4) A = {(h,s)(s,f)(s,n)(f,k)}

5) A = {(h,s)(s,f)(s,n)(f,k)(s,m)} （我们跳过 H 到 N 因为一条从 h 到 n 的路径已经通过s)

6) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)}

7) A = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)(b,m)}

所以现在既然有一条连接到所有边缘的路径，我们就很好了，对吧？

但我不明白的是有距离[u，v]比通过多个顶点的路径[u，v]短。例如 d[d,m] 比 p[d,m] 先通过 B 短。难道我做错了什么？