生成树

回顾 表达式的（逆）波兰记法 二叉搜索树 前缀码与Huffman编码

提要 生成树 深度优先搜索 广度优先搜索 有向图的深度优先搜索 回溯 最小生成树算法

生成树 定义：若图G的生成子图是树，则该子图称为G的生成树。 无向图G连通 当且仅当 G有生成树 证明(充分性显然)：

构造生成树：深度优先搜索 a c b e d f b f c a e d

深度优先搜索算法 Procedure DFS(G: 带顶点v1, …,vn的连通图) T:=只包含顶点v1的树； visit(v1)； Procedure visit(v: G的顶点) for v每个邻居w { if w不在T中 then { 加入顶点w和边{v, w}到T； visit(w)； }

回溯（八皇后） 在n×n格的棋盘上放置彼此不受攻击的n个皇后。 从空棋盘开始 尝试第1列，第1行，…n行； 尝试第2列，第1行，…n行； …. 尝试第k+1列，第1行，…n行； …

回溯（子集和） 给定一组正整数x1, …, xn ，和为M的一个子集？ 从空子集开始 尝试添加一项， 和等于M，结束； 没有合适添加项，去掉和的最后一项，

回溯（子集和） 举例：{31, 27, 15, 11, 7, 5}, 和为39的子集？  {31} {27} {31, 7} {27, 11} {31, 5} {27, 7} {27, 7, 5}

构造生成树：广度优先搜索 a c b e d f c f b d a e

广度优先搜索算法 Procedure BFS(G: 带顶点v1, …,vn的连通图) T:=只包含顶点v1的树; L:=空表; 把v1放入表L中 While L非空 { 删除L中的第一个顶点v; for v的每个邻居w { if w既不在L中也不在T中 then { 加入w到L的末尾; 加入顶点w和边{v, w}到T; }

例 不同的生成树 Breadth first Breaking cycles Depth first

最小生成树 Minimum Spanning Tree 考虑边有权重的连通无向图。其生成树可能不 唯一。定义生成树的权重为其所含各边之和。 一个带权连通图的最小生成树是其权重最小的 生成树。 注意，这里的最小(Minimum)并不意味着唯一。 最小生成树有广泛的应用。

Prim算法（求最小生成树） 1: E={e}, e是权最小的边 2: 从E以外选择与E里顶点关联，又不会与E中的边构成回路的权最小的边加入E 3: 重复第2步，直到E中包含n-1条边 算法结束

Prim算法（举例） 铺设一个连接各个城市的光纤通信网络（单位：万元）。 f e b a c d 54 60 36 38 8 40 48 20 45 28 15 30 62 25 12 10 h g

Prim 算法的正确性 令T为Prim算法的输出，并假设T按照边被选择的顺序包含了边{t1,t2,…,tn-1}。定义Ti={t1,t2,…,ti}。 只需证明Ti在一个MST中。 假设Tk在一个MST T'中，如果tk+1不属于T'，则T' + tk+1存在回路。 令sl为T'中不在Tk的最小边（index最小，显然sl的一个端点在Tk中）。这也就意味着，当选择tk+1时sl也可选而没有被选，即tk+1的权重不大于sl的权重。那么T' - sl + tk+1为包含Tk+1的MST。 tk+1 s1 sl sr-1 sr

Kruskal算法（求最小生成树） 1: E={ } 2: 从E以外选择不会与E中的边构成回路的权最小的边加入E 3: 重复第2步，直到E中包含n-1条边 算法结束

Kruskal算法（举例） f e b a c d h g 12 10 54 30 15 8 38 28 25 48 20 40 45 36 铺设一个连接各个城市的光纤通信网络（单位：万元）。 f e b a c d 54 60 36 38 8 40 48 20 45 28 15 30 62 25 12 10 h g

Kruskal算法（举例） 后面证明：Kruskal算法的正确性 B 26(9) 27 21(4) C A 42 E 36 29 D 34 25(8) 33 22 16(1) I 18(3) 21(5) 21(6) H F 25(7) J 28 17(2) 53 G 后面证明：Kruskal算法的正确性

引理（更换生成树的边） T与T'均是图G的生成树，若eET且eET’，则必有e'ET’, e'ET, 且T-{e}⋃{e'}和T'-{e'}⋃{e}均是G的生成树。 设e=uv, T-{e}必含两个连通分支，设为T1, T2。因T'是连通 图，T'中有uv-通路，其中必有一边满足其两个端点x,y分 别在T1, T2中，设其为e'，显然T-{e}⋃{e'}是生成树。 而T’-{e’}中x,y分属两个不同的连通分支，但在T*=T’- {e’}⋃{e}中，xu-通路+e+vy通路是一条xy-通路，因此T’- {e’}⋃{e}连通，从而 T'-{e'}⋃{e}是生成树。 T1 T2 u x v y e e'

Kruskal算法的正确性 显然T是生成树。 按在算法中加边顺序，T中边是e1,e2,…ek-1, ek,…en-1。 假设T不是最小生成树。对于任意给定的一棵最小生成树T’, 存在唯一的k, 使得ekET’ ，且eiET’使得(1ik). 设T’是这样的一棵最小生成树，使得上述的k达到最大。 根据前述引理，T’中存在边e’ ，e’不属于T, 使得T*=T’-{e’}⋃{ek}也是生成树。 e’T’与e1,e2,…ek-1不会构成回路，因此w(e’)w(ek). 所以w(T*)w(T’), 即T*也是最小生成树。但T*包含e1,e2,…ek-1,ek，矛盾。 w(e’)w(ek)：因为算法选择了ek

Generic Algorithm for MST Problem Input: G: a connected, undirected graph w: a function from VG to the set of real number Generic-MST(G,w) 1 A0 2 while A does not form a spanning tree 3 do find an edge (u,v) that is safe for A 4 AA{(u,v)} 5 return A 通用框架 Safe：an edge (u, v) is safe for A if and only if A ∪ {(u, v)} is also a subset of some MST Output: a minimal spanning tree of G

“避圈法”与“破圈法” 上述算法都是贪心地增加不构成回路的边，以求得最优树，通常称为“避圈法”； 从另一个角度来考虑最优树问题，在原连通带权图G中逐步删除构成回路中权最大的边，最后剩下的无回路的子图为最优树。我们把这种方法称为“破圈法”。

作业 见课程网站