当图形具有多个连通分量时，我不确定如何实现 Kruskal 算法
根据我对 Kruskal 算法的理解，它反复将最小边添加到集合中。然后，当检查所有边时，它会返回最多的边集。
但是，如果我的图表断开连接怎么办？说我有：
A - B - C - D
E - F
假设 Cost( A - B ) = Cost( E - F ) = 1，其余边大于 1
当我运行 Kruskal 时，我会得到所有边缘的成本，但我想得到每个连接组件的成本，所以我对所有连接组件进行平均最小成本。
问问题
5227 次
1 回答
0
好吧，克鲁斯卡尔的算法是这样工作的：
它将一一添加（联合）边，并专门维护不相交的集合。
听起来您希望为每组连接的顶点创建一个最小生成树（这样您就可以使用这些单独的树的聚合的最小加权成本），是吗？
因此，您选择 Kruskal 而不是 Prim 是正确的（后者不会在断开连接的图上运行）。
Kruskal 将在您的断开连接的图表上运行得很好；它将为每个连接的组件找到一个最小生成树。
“对于未连接的图，Kruskal 的算法返回一个生成树的森林——一个用于图的每个组件。” （Michael P. Fourman 的一篇关于生成树的精彩论文——爱丁堡大学计算机科学教授）
或者，您可以在每个仅包含连接组件的子图上运行 Prim。
祝你好运（如果你还没有发现你的问题）。
于 2020-04-20T02:32:29.680 回答