算法之「克鲁斯克尔（Kruskal）算法」

克鲁斯克尔算法（Kruskal's algorithm）跟普里姆算法一样，是一种用来查找最小生成树的算法，但算法的实现不一样，它是通过对权值从小到大顺序排列来查找最小生成树的。

克鲁斯克尔算法步骤

1.将原图中所有的边按权值从小到大排序。

2.从权值最小的边开始，如果这条边连接的两个节点于图中不在同一个已连接的边中，则记录该顶点为已选择。

3.重复步骤2，直至图中所有的节点都连通，就找到了连通图的最小生成树。

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

假如我们有 V 表示图中的顶点数，E 表示图中的边数。平均时间复杂度为 。

克鲁斯克尔算法示例

用克鲁斯克尔算法找到加权连通图的最小生成树。

通过对图中所有边的权值进行排序，得到 AD 边的权值最小为 5，并高亮标记。

然后下一条权值最小的边是 FH，权值为 6，并高亮标记。（注意不要构成环）

然后下一条权值最小的边有两条 AB 和 EH，权值为 7，我们任意选一条边 AB，并高亮标记。（注意不要构成环）

然后下一条权值最小的边是 EH，权值为 7，并高亮标记。（注意不要构成环）

然后下一条权值最小的边是 HG，权值为 8，并高亮标记。（注意不要构成环）

最后一条权值最小的边是 DE，权值为 9，并高亮标记。现在图中所有顶点都连接了，红色连接的边就是最小生成树，最小生成树的权值之和为 42。

注意：在权值相同的边，我们可以任意选择一条边，但选择的边不能跟以前的边构成环。如果当权值最小的边跟已选择的边构成了环，就跳过当前的边，继续下一条权值最小的边。

总结

克鲁斯克尔算法跟普里姆算法一样，是一种用来查找最小生成树的算法。

对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。

PS:

清山绿水始于尘，博学多识贵于勤。

我有酒，你有故事吗？

微信公众号：「 清尘闲聊 」。

欢迎一起谈天说地，聊代码。