算法思想：设无向连通带权图G＝（V，E），其中V为结点的集合，E为边的集合。设带权图G的最小生成树T由结点集合和边的集合构成，其初值为T＝（V，｛｝），即初始时最小生成树T只由带权图G中结点集合组成，各结点之间没有一条边。然后，按照边的权值递增的顺序考察带权图G中边集合E的各条边，若被考察的边的两个结点属于T的两个不同的连通分量，则将此边加入到最小生成树T中，同时，把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树。具体步骤如下。

假设N＝（V，｛E｝）是连通网，将N中的边按权值从小到大的顺序排列；

①将n个顶点看成n个集合；

②按权值从小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；

③重复②直到所有的顶点都在同一个顶点集合内。

可以看出，克鲁斯卡尔算法逐步增加生成树的边，与普利姆算法相比，可称为“加边法”。

下面我们以图7－26（a）中的连通网为例，克鲁斯卡尔算法的执行过程如图7－26（b）～（f）所示。

图7－26 克鲁斯卡尔算法执行示意图

克鲁斯卡尔算法：算法时间复杂度为O（elog2e），e为网的边的数目；适合于求边稀疏的网的最小生成树。