第九讲 最小生成树
（教材：第九章 最小生成树）
算法三 (破圈法)
“破圈法”就是在图中任意取一个圈，从圈中去掉权最大的边，将这个圈破掉。重复这个过程，直到图中没有圈为止，保留下的边组成的图即为最小生成树。
用破圈法求上述图 9.1 所示网络的最小生成树。
解
在圈
中，去掉权最大的边 
，得图1；
在圈
中，去掉权最大的边 
，得图2；
在圈
中，去掉权最大的边 
，得图3；
在圈
中，去掉权最大的边 
，得图4。
此时，在图 3 中已经没有圈了，于是得最小生成树。
三. 斯坦纳最小树的概念和一些基本性质
1. 问题提出
19世纪初，斯坦纳提出：在欧氏平面上任给有限点集
，试求一点集
，用线段把点集 
连接起来，如何连接才能使连线的总长度最短？
这个问题很有实际意义，比如居民点自来水管的铺设、一地区电话线路的架设等问题都可抽象为斯坦纳问题。在欧氏平面上任给有限点集
，求一点集 
，使得连接点集 
中的点的连线的总长度最短。连结 
中的点，使其总长度最短的图，必然是边数最少的连通图，因此它是树，称为斯坦纳最小树，简记为
SRT。问题中原有的 
中的点为 SRT 上的固定点；
中的点称为 SRT 上的斯坦纳点，简称为斯坦纳点。