克鲁斯克尔算法：通过权值从小到大排序来求最小生成树

克鲁斯克尔算法（Kruskal算法），与Prim算法类似，都是用来求最小生成树的算法，但算法的实现不同。通过将权重值从小到大排序来找到最小生成树。

克鲁斯克尔算法的步骤

1。将原始图的所有边按权重从小到大排序。

2。从权重最小的边开始，如果与这条边相连的两个节点不在图中的同一条连通边上，则按选定的方式固定该顶点。

3。重复步骤2，直到图的所有节点都连接起来，找到连通图的最小生成树。

克鲁斯克尔算法的时间复杂度

设V为图的顶点数，E为图的边数。平均时间复杂度为。

克鲁斯克尔算法示例

使用克鲁斯克尔算法求加权儒家最小生成树。

对图所有边的权重进行排序，边AD的最小权重为5，用高亮表示。

那么权重次低的边是FH，权重为6，标记为高亮。 （注意不要形成环）

然后权重次低的边有两条边AB和EH，权重为7。我们随机选择一条边AB，标记为高亮。 （注意不要形成环）

然后权重次低的边是EH，权重为7，标记为高亮。 （注意不要形成环）

然后权重次小的边是HG，权重8并标记高亮。 （注意不要形成环）

权重最低的最后一条边是DE，其权重为9，标记为高亮。现在图的所有顶点都相连了，红色相连的边就是最小生成树，最小生成树的权重之和为42。 注意：可以从权重相同的边中选择任意边，但是所选边不能与前一个边形成循环。如果权重最低的边与所选边形成循环，则跳过当前边并继续处理下一个权重最低的边。

总结

克鲁斯克尔算法和Prim算法一样，都是用来寻找最小生成树的算法。

对比两种算法，Kruskal算法主要扩展到边缘。如果边的数量很少，效率会很高，对于稀疏图有很大的优势；而 Prim 的密集图算法（即边缘算法）在许多情况下会更好。

作者：清尘聊天
来源：掘金