克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。

克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。

对于图7.18（a）所示的网，按照克鲁斯卡尔方法构造最小生成树的过程如图7.20所示：

图7.20中按权值由小到大的顺序排列的编辑是：（各边由起点序号，终点序号，权值表示）

1.(4,6,30) 2.(2,5,40) 3.(4,7,42) 4.(3,7,45)

5.(1,2,50) 6.(4,5,50) 7.(3,4,52) 8.(1,3,60)

9.(2,4,65) 10.(5, 6, 70)

克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个部分：首先是带权图G中e条边的权值的排序；其次是判断新选取的边的两个顶点是否属于同一个连通分量。对带权图G中e条边的权值的排序方法可以有很多种，各自的时间复杂度均不相同，对e条边的权值排序算法时间复杂度较好的算法有快速排序法、堆排序法等，这些排序算法的时间复杂度均可以达到O（elge）。判断新选取的边的两个顶点是否属于同一个连通分量的问题是一个在最多有n个顶点的生成树中遍历寻找新选取的边的两个顶点是否存在的问题，此算法的时间复杂度最坏情况下为O（n）。

克鲁斯卡尔算法的时间复杂度主要由排序方法决定，而克鲁斯卡尔算法的排序方法只与网中边的条数有关，而与网中顶点的个数无关，当使用时间复杂度为O（elog2e）的排序方法时，克鲁斯卡尔算法的时间复杂度即为O（log2e），因此当网的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果较好。

无向连通网的最小生成树首先是一棵生成树，即它应该是一个使网中所有顶点相连通而所需边的条数为最小的子网络，且其代价和在所有生成树中为最小。因此，可以从网的连通性角度来观察Kruskal算法。

初始时，最小生成树就是网中所有顶点的集合，它们之间没有任何一条边连接，即它们自成一个连通分量。而Kruskal算法的执行过程其实就是一个选取网中权值为最小的边的过程，即将两个小的连通分量连接为较大的连通分量，直至所有顶点都在一个连通分量中为止。每当选取网中的一条边时总会出现以下两种情况之一：

①该边所依附的两个顶点分属于不同的连通分量。这时，该边可以作为最小生成树的一条边，因为两个不同的连通分量通过这条边的连接而相连通，成为了一个连通分量。

②该边所依附的两个顶点属于同一个连通分量。如果选取这条边作为最小生成树的一条边，则必将构成环。因为连通分量中任意两个顶点间都有路径相通，一旦再加入一条边，该边所依附的两个顶点之间就有了两条路径，即构成了环。故属于这种情况的边即使其权值小也应该舍弃。