当图形具有多个连接的组件时，我不确定如何实现Kruskal算法
根据我对Kruskal算法的理解，它会反复将最小边缘添加到集合中。然后，在检查完所有边缘后，它将返回最有效的一组边缘。
但是，如果我的图形断开连接怎么办？说我有:
A - B - C - D
E - F
并说Cost(A-B)= Cost(E-F)= 1，其余边缘大于1
当我运行Kruskal时，我将获得所有边缘的成本，但是我想获得所连接组件的EACH成本，因此我对所有所连接组件进行平均最小成本。
最佳答案
好吧，Kruskal的算法的工作原理如下:
它将一个接一个地添加(联合)边缘，并专门维护不交集。
听起来好像您正在为每组连接的顶点都拥有一个最小生成树(这样您就可以使用这些单独的树的合计最小加权成本)，是吗？
因此，您在选择Kruskal而不是Prim时是正确的(后者不会在未连接的图形上运行)。
Kruskal将在断开连接的图形上运行良好；它将为每个连接的组件找到最小的生成树。
“对于未连接的图形，Kruskal的算法返回的森林为
生成树–图的每个组成部分。” (a great paper on Spanning Trees by Michael P. Fourman— a Prof. of CS at University of Edinburgh)
或者，您可以在仅包含已连接组件的每个子图上运行Prim's。
祝您好运(如果您还没有很长的时间来解决您的问题)。
Kruskal's Algorithm Pseudo-Code
关于algorithm - 具有断开图的Kruskal算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22238914/