第九讲 最小生成树
（教材：第九章 最小生成树）
二. 最小生成树，求最小生成树的三种算法
算法一 (克鲁斯凯尔，Kruskal)
算法一的中心思想是每次添加权尽可能小的边，使新的图无圈，直至得到生成树为止。该方法形象地简称为“最小边加入法”。其步骤如下：
(1) 把
内的所有的边按照权的大小由小到大排列。
(2) 按(1)排列的次序依次检查
中的每一条边，如果这条边与已得到的图不产生圈，则取这一条边为所求生成树的一部分。
(3) 若已取到
条边，算法终止。此时以 
为顶点集，以取所取的 
条边为边集的图即为最小生成树。
〔例1〕 求下图 9.1 （教材 p110 ）所示网络的最小生成树。
解 将各边的权按非减次序排列，得网络中的 8 条边的排列次序为
首先取权最小的两条边
和 
为所求最小生成树 
的两条边，然后检查边 
。由于边 
、
和 
构成圈，故不取边 
。接下来考虑边 
。由于
、
和 
不构成圈，故取 
。然后检查边 
。由于 
、
、
和 
不构成圈，故取 
。再看 
，它与 
、
构成圈，故不取。同样地，
也不可取，因为 
与 
、
、
构成圈，而 
与 
、
构成圈。因此由 
、
、
和 
构成的生成树 
为网络 
的最小生成树(如图9.2)。
