问题标签 [kruskals-algorithm]

我创建了一个 Kruskal 函数，以便它可以在图形上找到最小的路径。但是我用冒泡排序做到了，我正在尝试使用 qsort 使其工作并使我的结构动态化，这样它可以让我更有效率。

使用的所有功能都可以正常工作，但如果您对此有疑问，请询问我，以便我发布。我正在使用联合查找作为pd(dynamcc partition)链接。

我的代码是：

我们已经看到生成树和切割是密切相关的。这是另一个连接。让我们删除 Kruskal 算法添加到生成树的最后一条边；这将树分成两个组件，从而在图中定义了一个切割 (S,S)。我们能说什么？假设我们正在处理的图是未加权的，并且它的边是随机均匀排列的，以便 Kruskal 算法处理它们。这是一个值得注意的事实：至少有 1/n^2 的概率，(S,S) 是图中的最小割，其中割的大小 (S, S) 是 S 和 S 之间交叉的边数. 这意味着重复该过程 O(n^2) 次并输出找到的最小切割以高概率产生 G 中的最小切割：用于未加权最小切割的 O(mn^2 log n) 算法。

• 这不取决于通过 Kruskal 算法处理图形的 n^2 种独特方法这一事实吗？我的意思是，如果Kruskal 算法只有3 种独特的方式来处理具有 10 个节点的图，那么重复该过程 n^2 次将不会产生 n^2 独特的“最后一条边”。在唯一的最终切割少于 n^2 个（即少于 n^2 个唯一的“最后边缘”）的情况下，它将如何工作？

• 如果总共有少于 n^2 条边怎么办？例如，您可以有一个只有 9 条边的 10 个节点的连通图，这意味着无论您重复该算法多少次，您都不会有 n^2 个唯一的“最后一条边”。在这种情况下它将如何工作？

• 循环遍历每个边缘并检查边缘是否是最小切割不是更容易吗？在 n 个节点的图中，唯一边的最大数量为 n + n-1 + n-2... + 1 条边，小于 n^2。考虑到 n^2 小于 n^2 log n，为什么不直接遍历所有边，因为这样更快？

我正在尝试实现 kruskal 算法，该算法在无向加权图 G(V,E) 上找到最小生成树。我的实现使用不相交集来使算法更快。这是代码：

它编译没有错误，但它没有给我任何结果。例如，当我给它这个输入时：

它根本不会产生任何输出。谁能帮我？提前致谢。

编辑：我发现我认为错误在哪里，并带有评论。由于tree是空的，我的结论if(!same_component(array[g.edges[i].v], array[g.edges[i].u]))是总是false。所以错误一定出在same_component函数上，但我无法发现它。

我在教科书中偶然发现了这个问题：

“一般来说，Prim、Kruskal 和 Dijkstra 算法的时间复杂度取决于什么？”

一个。图中的顶点数。
湾。图中的边数。
C。两者都是关于图中顶点和边的数量。

解释你的选择。

因此，根据 Wikipedia Prim、Kruskal 和 Dijkstra 的算法，最坏情况的时间复杂度分别O(ElogV)为O(ElogV)和O(E+VlogV)。所以我猜答案是c？但为什么？

Prim 和 Kruskal 的算法都产生最小生成树。根据割属性，对于这些算法，树的总成本将是相同的，但是这两种算法是否有可能以相同的总成本给出不同的 MST，因为我们在面临多个选择时按字母顺序选择它. 例如，我们比较 max(source,dest)，对于边 A->B 和 B->C，我们比较 A->B 中的 A 和 B->C 中的 B。

谢谢

我在将结果保存到输出文件时遇到问题。该功能可能有问题，但我找不到并修复它。有人知道出了什么问题吗？

程序代码：

这是输入文件（“In0303.txt”）：

这就是应该在输出文件中创建的内容：（“Out0303.txt”）：

我正在阅读 wikipeida 并发现 Kruskal 的伪代码如下：

我不确定是什么FIND_SET()，维基百科有以下描述：

如果该边连接两棵不同的树，则将其添加到森林中，将两棵树组合成一棵树。

所以我想它会检查是否连接了两棵不同的树，但这到底意味着什么？

可能的重复：
Kruskal vs Prim

你什么时候会使用 Kruskal 算法而不是 Prim 算法来找到最小生成树？哪种输入图和节点更适合每种类型？在什么情况下，在空间和时间方面使用其中一种更有效？

他们的特定输入是否使一个比另一个好得多？

就像标题一样。对于 Kruskal 算法，将节点保存在内存中的最佳方法是什么，为什么？

我正在阅读教科书Introduction to Algorithms，CLRS我想在 c 中实现mstusingkruskal算法，我想知道的是，我应该使用哪个图形实现，邻接表还是邻接矩阵？edges我认为在使用邻接表时排序并不直观，当edge像这样定义邻接表时，邻接表中的表示令人困惑：

在对边缘进行排序时，我想使用一个指针数组来指向上面定义的节点，问题是上面定义的结构找不到start point边缘的，但​​是end point. 所以我改变了这样的结构：

我想问的是：这样定义邻接表可以吗？还是有更好的做法？或者我应该使用邻接矩阵（因为我看到有些人在搜索互联网时使用矩阵实现 kruskal）？为什么？对不起英语不好。任何帮助将不胜感激。