问题标签 [kruskals-algorithm]

我正在尝试开发一种聚类算法，该算法的任务是在一组 2D 点上查找 k 个类（将 k 作为输入），使用经过轻微修改的 Kruskal 算法来查找 k 个生成树而不是一个。

我使用 rand 指数将我的输出与建议的最优值 (1) 进行了比较，对于 k = 7，结果为 95.5%。比较可以在下面的链接中看到。

问题：

该集合有 5 个间隔明显的簇，这些簇很容易被算法分类，但是当 k > 5 时，结果相当令人失望，这就是事情开始变得棘手的时候。我相信我的算法是正确的，也许数据对于 Kruskal 方法来说特别糟糕。众所周知，Kruskal 之类的单链接凝聚聚类在某些问题上表现不佳，因为它将聚类质量的评估降低到一对点之间的单个相似性。

算法的思想很简单：

• 用数据集做一个完整的图，边的权重是这对之间的欧几里得距离。
• 按权重对边缘列表进行排序。
• 对于每条边（按顺序），如果它不形成循环，则将其添加到生成林中。当所有的边都被遍历完或者剩余的森林有 k 棵树时停止。

底线： 为什么算法会这样失败？是克鲁斯卡尔的错吗？如果是这样，为什么？有什么建议可以在不放弃 Kruskal的情况下改善结果吗？

(1)：Gionis, A.、H. Mannila 和 P. Tsaparas，聚类聚合。ACM Transactions on Knowledge Discovery from Data (TKDD)，2007.1(1)：p.1-30。

谁能解释为什么 Kruskal 产生的树与 Dijkstra 不同？

我知道 kruskal 在边缘的非降序上工作，但 Dijkstra 利用了优先级队列，但仍然无法理解为什么它们的结果树不同？

我正在计算这样的 kruskal 算法的时间复杂度（请参阅附件中的算法）

CLRS 算法：

是正确的还是我做错了什么，请告诉。

我在这里找到了使用 Kruskal 算法的最小生成树模板

他们使用整数权重，如果我想使用双重权重来实现代码，是否有可能？

我在这里和那里进行了更改，并不断给我错误。

这是我更改的内容：

和

我不知道为什么，但是这些更改使快速排序在void KruskalMST(struct Graph* graph)接下来的几行中无法工作

这是原始代码：

我正在学习最小生成树，我遇到了这个问题并决定试一试......

在随机生成的 100 个顶点和 800 条边的有向图网络上实现最小生成树算法

我被困在如何生成随机边缘和顶点......任何建议和想法......

玩转图论，我在 C++ 中实现了 Kruskal 算法并使用 GraphViz 进行可视化，但在运行代码以使用以下命令生成 png 文件时：

它显示了这一点：

我正在使用 ubuntu linux 来执行此操作，下面附上我的 c++ 代码

我假设我的命名空间没有错或有任何其他方法可以解决这个问题？

有人可以向我提供有关如何检查图形边缘是否形成循环的信息吗？任何信息都会非常有帮助。提前谢谢了。

我最近学习了图论，我试图实现 Kruskal 的算法来找到最小值。使用权重矩阵在图中生成树。我得到了一个矩阵的正确输出和一个超出范围的错误！它给了我一个错误：

我得到正确答案的矩阵如下：（注意：1000 用于表示无穷大的权重

我有一个问题，我正在研究 Kruskal 算法的实现，我完成了它，它正在工作，但是有一个问题，我使用了一个“静态”数组 2D，（由用户输入，但限制为 100 ）。如何在动态分配或使用向量中转换它？我更喜欢向量，但我不知道如何在向量的向量中“修改和插入”项目。任何人都可以帮助我吗？谢谢再见

有代码：

我分析了 Kruskal 算法的运行时间，得出了 O(ElogE+Elogv+v)

我问我的教授，他说如果图形非常稀疏，有许多孤立的顶点，V 支配 E，如果不是，那么 E 支配 V，我不明白为什么？我可以举一个例子，其中图形不是稀疏的，但 V 仍然大于 E

谁能帮我消除这种困惑？