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