生成树 离散数学─树 南京大学计算机科学与技术系

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

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

构造生成树：深度优先搜索 a c b e d b e 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)； }

depth-first search tree Normal spanning trees are also called depth-first search trees.

构造生成树：广度优先搜索 a c b e d c e 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; }

有向图的深度优先搜索 a b c d e f g h l i j k

有向图的深度优先搜索 http://pine.cs.yale.edu/pinewiki/DepthFirstSearch

回溯（八皇后） 在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}

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

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，矛盾。

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

作业 教材[10.4, 10.5] p.573：5, 14, 24, 29(c), 39 p.580：4, 7, 13, 21