问题标签 [kruskals-algorithm]

根据维基百科，我使用不相交集数据结构在 C++ 中实现了 Kruskal 算法，如下所示：

我的问题是：我需要这两行代码吗？如果是这样，它们的重要性是什么？

1. int px=findset(x),py=findset(y); 在合并而不是int px=parent[x],py=parent[y];
2. parent[x]=findset(parent[x]);在 findset 而不是return findset(parent[x]);

我尝试浏览图表并将某个 ID 的每个实例更改为更新的 ID，但它仍然导致了一个循环。解决非循环解决方案的计划是什么？

谁能提供这两种算法的一些应用程序，它们可以用于哪些应用程序和哪些应用程序？

参考 Ada 中的 Kruskal 算法，我不知道从哪里开始。

在实际编写程序之前，我试图仔细考虑所有内容，但是对于我应该使用哪些数据结构以及如何表示所有内容，我非常迷茫。

我最初的想法是在邻接列表中表示完整的树，但是阅读 Wikipedia 中的算法状态create a forest F (a set of trees), where each vertex in the graph is a separate tree，我不确定如何在不快速变得混乱的情况下实现这一点。

它说要做的下一件事是create a set S containing all the edges in the graph，但我再次不确定最好的方法是什么。我正在考虑一系列记录，带有to,from和weight，但我迷失在forest.

最后，我试图弄清楚我如何知道一条边是否连接两棵树，但我再次不确定做这一切的最佳方法是什么。

我有以下来自图论主题的代码，用于最小生成树的 kruskal 算法

哪个有效并用于以下输入

其中顶点数和边数为4，给我这样的输出

我的问题是有任何语义错误吗？我也使用了数组和许多变量，我可以缩短这段代码吗？我的（编程）语言是 c++

我正在从文件中读取表示并将其存储在邻接列表中。然后我以“graphviz 格式”输出图形并在图形上执行 MST 算法。最后，我以“graphviz 格式”输出 MST。我在 C++ 中这样做。

我的主要问题是算法。我正在实现 Kruskals 算法并且排序功能不起作用。

当我编译它时，我得到这个错误：

从 'void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) 实例化 [with _RandomAccessIterator = __gnu_cxx::__normal_iterator*, std::vector, std::allocator > > >, _Compare = bool (*)(Edges, Edges)] '</p>

这是我的代码：

我正在研究为给定图查找 MST 的 Kruskal 算法，并且我了解最初必须将所有顶点视为森林的基本概念。之后，您必须找到最小边并将边的顶点连接成一棵树。并递归地执行此操作，直到只剩下一棵包含所有顶点的树。

我遇到了这个算法的以下实现。

我不明白的是需要：

这两个 while 循环究竟做了什么？

编辑：还有——

I am implementing the Christofides algorithm for getting a 3/2-approximation to TSP in graphs that obey the triangle inequality. I already have code for computing a minimum spanning tree using Kruskal's algorithm and an adjacency matrix.

Now, I want to implement Christofides by doubling the edges and finding an Euler tour and then shortcutting duplicate nodes. How do I perform this step? I'd like the algorithm and (optionally) C code.

Thanks!

我已经使用邻接矩阵图表示在 C 中实现了 Kruskal 算法，问题是，它不断弹出分段错误错误，我一直试图找出问题所在，但我似乎找不到问题，请问有没有人看一下？谢谢。

这是我的代码：

这是我用于 Kruskal 算法的伪代码。我在这里使用的数据结构是邻接矩阵。我得到了增长的顺序n^2。我想知道它是否正确。