中文一般译作克鲁斯卡尔算法

Joseph Kruskal(犹太裔美国人,1928年1月29日–2010年9月19日)在1956年发表

用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用




时间复杂度为O(eloge)(e为网中的边数),所以适合于求边稀疏的网的最小生成树

克鲁斯卡尔算法的时间复杂度主要由排序方法决定,而其排序方法只与网中边的条数有关,而与网中顶点的个数无关,当使用时间复杂度为O(elog2e)的排序方法时,克鲁斯卡尔算法的时间复杂度即为O(log2e)


伪代码:



参考:

最小生成树之Prim算法和Kruskal算法

最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示