第3章树与最短路

1、第三章 树与最短路3.1 树及其等价定义3.2 生成树3.3 根数及其应用3.4 最短路算法3.5 中国邮路问题3.6 旅行商问题v3.1 树及其等价定义例：例：判断下列哪些图是树？判断下列哪些图是树？(a)(b)(c)例例：画出：画出5阶所有非同构的无向树。阶所有非同构的无向树。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。

2、。 。 。 。 。 。 。 。其非同构的图形为：其非同构的图形为： 解解： 有如下有如下6种情况种情况:(1,1,1,1,1,5)(1,1,2,2,2,2)(1,1,1,3,2,2)(1,1,3,3,1,1)(1,1,4,2,1,1)例：例：画出画出6阶所有非同构的无向树。阶所有非同构的无向树。abcdabcdabcd(1)(2)(3)Kruskal算法算法 一种求最小生成树的算法一种求最小生成树的算法例例:用用Kruskal算法求算法求下图所示的最小生成树下图所示的最小生成树abcdf5555136642bacd762f81443472356321hg例：例：铺设一个连接各个城市的光纤通信网

3、络。图中铺设一个连接各个城市的光纤通信网络。图中蓝色为蓝色为最小生成树最小生成树。例例 ：在图在图(a)中给出了一个连通图中给出了一个连通图, 求此图的生成树。求此图的生成树。(a)3.3 根根树及其应用树及其应用 一个有向图，略去方向后是树，则称这个有向一个有向图，略去方向后是树，则称这个有向图为图为有向树有向树。如果一棵有向树恰有一个结点入度为。如果一棵有向树恰有一个结点入度为0，其余所有结点入度为其余所有结点入度为1，此有向树称为，此有向树称为根树根树。在根树。在根树中，入度为中，入度为0的结点称为的结点称为树根树根，出度为，出度为0的结点称为的结点称为树叶树叶，出度不为，出度不为0的结

4、点称为的结点称为分枝点分枝点或或内点内点。从此定。从此定义可以看出，在根树中，除了树叶都是分枝点或内义可以看出，在根树中，除了树叶都是分枝点或内点外，树根也是分枝点点外，树根也是分枝点。 (1)(2)012345670123456701234567（a）是）是2叉树，（叉树，（b）是正则）是正则2叉树叉树（c）是完全）是完全2叉树。叉树。4 4 5 51 16 63 33 34 45 56 61 11 13 36 64 45 5Huffman算法算法 一种求最优二叉树的算法一种求最优二叉树的算法哈夫曼算法的步骤哈夫曼算法的步骤例例:求带权求带权1,3,4,5,6的最优二元树。的最优二元树。44

5、81338431134564411561481119最优二叉树在通信编码中的应用最优二叉树在通信编码中的应用又如又如：1,00,011,0101,01001,01000是是前缀码。前缀码。而而1,00,0101,0100,01001,01000不是不是前缀码，前缀码，因为因为0100是是01001的前缀，也是的前缀，也是01000的前缀。的前缀。例例： 0, 10, 110, 1111 1, 01, 001, 0001 等是前缀码等是前缀码而而 1,11,101,001,0011不是不是前缀码前缀码若使用前缀码中的若使用前缀码中的0 0、1 1序列表示英文字母，当接收者收序列表示英文字母，当接

6、收者收到到0 0、1 1组成的长串时，就可以惟一的、准确无误地分割组成的长串时，就可以惟一的、准确无误地分割成字母对应的成字母对应的0 0、1 1序列。序列。定理：定理：任意一个二叉树，可以产生惟一的前缀码。任意一个二叉树，可以产生惟一的前缀码。 证明：证明：在二叉树中，每一个分枝点引出的左侧边标在二叉树中，每一个分枝点引出的左侧边标记记0 0，右侧边标记，右侧边标记1 1。由根结点到树叶的路经上各边的标。由根结点到树叶的路经上各边的标记组成的记组成的0 0、1 1序列作为该片树叶的标记。显然，没有一序列作为该片树叶的标记。显然，没有一片树叶的标记是另一片树叶的标记的前缀。所有树叶的片树叶的标

7、记是另一片树叶的标记的前缀。所有树叶的标记构成了一个前缀码。标记构成了一个前缀码。010110101000100010101111例：例：右图所示的二元树右图所示的二元树产生的前缀吗为产生的前缀吗为11,00,011,0100,0101利用利用Huffman算法求出的最优算法求出的最优2叉树产生的前缀码称叉树产生的前缀码称为为最佳前缀码最佳前缀码。例例: 在通信中在通信中, 0,1,2,3,4,5,6,7出现的频率出现的频率如下如下: 0：30, 1：20, 2： 15 3：10, 4：10, 5： 5 6： 5, 7：5 求传输它们的求传输它们的最佳前缀码最佳前缀码1006040303020

8、2015151055501010101010110100100000000010001001100101110111传传1, 01传传0, 0001传传5 ,001传传2, 101传传4 ,00001传传6 100传传3, 00000传传7。决策树决策树 若树的每个内点都对应着一次决策若树的每个内点都对应着一次决策, ,这些这些顶点顶点的子树的子树都对应着该决策的每种可能结果都对应着该决策的每种可能结果, ,这样这样的有序的有序树称为树称为决策决策树树。例例：有：有8 8枚外观相同的硬币枚外观相同的硬币, ,其中有其中有7 7枚重量相同枚重量相同, ,而剩余而剩余的一枚伪币较轻的一枚伪币较轻,

9、 ,要求以比较重量的方法用要求以比较重量的方法用一架一架天平去找天平去找出伪币。出伪币。解解: :用用1-81-8标记硬币标记硬币, ,每次衡量有每次衡量有3 3种可能种可能: :左旁低下左旁低下, ,保持保持水平水平, ,右旁低下右旁低下, ,下图给出这一解决过程的下图给出这一解决过程的决策图。决策图。图中图中表示不会出现的结果。表示不会出现的结果。决策树的结点左侧标记着状态决策树的结点左侧标记着状态,这里表示包含有这里表示包含有伪币伪币的的硬币集合硬币集合,右侧标记测试内容右侧标记测试内容。1,2,3,81,2,3对6,7,8右旁低下左旁低下1,2,31对332154876二叉树的遍历二叉

10、树的遍历二叉树的遍历二叉树的遍历 访问一棵根树的每个顶点一次且仅一次称为树的遍历。遍历一棵二叉树的方法常有如下三种：（1）中序遍历法中序遍历法：访问顺序为“左子树、树根、右子树”；（2）前序遍历法前序遍历法：访问顺序为“树根、左子树、右子树”；（3）后序遍历法后序遍历法：访问顺序为“左子树、右子树、树根”。 例：例：试用三种周游方式行遍下图。试用三种周游方式行遍下图。中序行遍法访问此树中序行遍法访问此树：(a(b+c)+def ) (g+(h-i)j)前序行遍法访问此树：前序行遍法访问此树：(+(a (+b c )d (e f ) +g(- h i j )后序行遍法访问此树：后序行遍法访问此树

11、：a b c + def+ gh i - j + 定理的证明定理的证明3.4 最短路问题最短路问题问题的提出问题的提出: 路径路径路径长度路径长度: 非带权图的路径长度非带权图的路径长度是指此路径上边的条数。是指此路径上边的条数。带权图的路径长度带权图的路径长度是指路径上各边的权之和是指路径上各边的权之和.例例:一位旅客要从一位旅客要从A城到城到B城：城：1. 他希望选择一条途中中转次数最少的路线；他希望选择一条途中中转次数最少的路线；2. 他希望选择一条途中所花时间最短的路线；他希望选择一条途中所花时间最短的路线；3. 他希望选择一条途中费用最小的路线；他希望选择一条途中费用最小的路线；54

12、3210 100 6030101020 5 50这些问题均是带权图上的最短路径问题这些问题均是带权图上的最短路径问题。1. 边上的权表示一站边上的权表示一站2. 边上的权代表距离边上的权代表距离3. 边的权代表费用边的权代表费用 Dijkstra算法算法下面给出该算法的框图：下面给出该算法的框图：通过一个实例来说明通过一个实例来说明Dijkstra算法是如何工作的：算法是如何工作的：0次迭代次迭代1次迭代次迭代a，SaL(a)(a,b)044L(b)L(a)(a,c)022L(c)L(a)(a,d)0L(a)(a,e)0L(a)(a,z)0L(b)4，L(c)2，L(d)L()L(z)2次迭代

13、次迭代c，Sa,cL(c)(c,b)213L(b)L(c)(c,d)2810L(d)L(c)(c,e)21012L(e)L(c)(c,z)2L(b)3，L(d)10，L()12，L(z)45623108abcdz用用Dijkstra算法算法求求a和和z之间最短路所用的步骤。之间最短路所用的步骤。 3次迭代次迭代b，Sa,c,bL(b)(b,d)358L(d)L(b)(b,e)3L(b)(b,z)3L(d)8，L()，L(z) 4次迭代次迭代d，Sa,c,b,dL(d)(d,e)8210L()L(d)(d,z)8614L(z)L()10，L(z)14 5次迭代次迭代，Sa,c,b,d,eL()(

14、e,z)10313L(z)L(z)13 结结 束束z，Sa,c,b,d,e,z从从a到到z的最短路的长度为的最短路的长度为13。45623108abcdz用用Dijkstra算法算法求求a和和z之间最短路所用的步骤。之间最短路所用的步骤。 Floyd算法算法求下图各点间的最短路径求下图各点间的最短路径213465121733621D1 2 3 4 5 6123456v解：*d14min+,1+3,2+1, +, +, +,类似可得：类似可得：S213465121733621Floyd-Warshall算法算法例：例：求下图各点间的最短路径求下图各点间的最短路径213465121733621D1

15、 2 3 4 5 6123456解：解：比较经过顶点号比较经过顶点号1的矩阵的矩阵213465121733621D(0)1 2 3 4 5 61234561 2 3 4 5 6123456无改变无改变解：解：比较经过顶点号比较经过顶点号2的矩阵的矩阵2134651217336211 2 3 4 5 61234561 2 3 4 5 612345648解：解：比较经过顶点号比较经过顶点号3的矩阵的矩阵2134651217336211 2 3 4 5 61234561 2 3 4 5 61234564233解：解：比较经过顶点号比较经过顶点号4的矩阵的矩阵2134651217336211 2 3

16、4 5 61234561 2 3 4 5 6 123456654 解：解：比较经过顶点号比较经过顶点号5的矩阵的矩阵2134651217336211 2 3 4 5 61234561 2 3 4 5 6123456无改变无改变解：解：比较经过顶点号比较经过顶点号6的矩阵的矩阵2134651217336211 2 3 4 5 61234561 2 3 4 5 6 123456无改变无改变1 2 3 4 5 6123456 1962年我国的管梅谷首先提出并研究了如下的问题：邮递员从邮局出发经过他投递的每一条街道，然后返回邮局，邮递员希望找出一条行走距离最短的路线。这个问题被称为中国邮递员问题中国邮

17、递员问题。3.5 中国中国邮递员问题邮递员问题 我们把邮递员的投递区域看作一个连通的带权无向图，其中的的顶顶点看作街道的交叉口和端点，街道看点看作街道的交叉口和端点，街道看作边作边，权看作街道的长度，解决中国邮递员问题，就是在连通带权无向图中，寻找经过每边至少一次至少一次且权和最最小的回路小的回路。123456789101112 2 4 55 3 6 4 6 4 65 4 4 7 9 3 8A1 10 9 8 2 6 11 4 12 6 7 5 5 4 3 4 7 7 3 4 5 6 5 3 4 6 4 2 4 5 9 3 8 9 3 8B445 5 4 4 7 7993 8 8 6 4 63

18、 61 10 9 8 2 11 12 7 3 4 5 6 C44 6 4 6 6 65 4 4 4 4 7 9 3 8 5 3 6 41 2 10 9 5 8 2 11 12 7 3 4 5 6 D44 5 4 4 7 3 3 2 4 5 5 3 6 466 6641 10 9 8 9 8 2 11 12 7 3 4 5 6 E 2 4 5 5 5 3 6 4 4 2 5 6 4 6 5 4 4 7 9 3 831 10 9 8 2 11 12 7 3 4 5 6 F 旅行售货员问题是在加权完全无向图中，求经过每个顶点恰好一次的(边)权和最小的哈密尔顿圈，又称之为最优哈密尔顿圈最优哈密尔顿圈。

19、如果我们将加权图中的结点看作城市，加权边看作距离，旅行售货员问题就成为找出一条最短路线，使得旅行售货员从某个城市出发，遍历每个城市一次，最后再回到出发的城市。3.6 3.6 旅行旅行售货员问题售货员问题最邻近算法最邻近算法给出旅行推销员问题的近似解给出旅行推销员问题的近似解步骤如下：步骤如下：(1)(1)由任意选择的结点开始，找出于该结点邻近由任意选择的结点开始，找出于该结点邻近的点，形成一条有边的初始路。的点，形成一条有边的初始路。(2)(2)以表示最新加到这条路上的结点，从不在路以表示最新加到这条路上的结点，从不在路上的所有结点中选一个和最靠近的结点，把连接与这上的所有结点中选一个和最靠近

20、的结点，把连接与这一结点的边加到这条路上，重复这一步骤直到这条路一结点的边加到这条路上，重复这一步骤直到这条路包含图中所有结点。包含图中所有结点。例：例： 用用“最邻近算法最邻近算法”给出下面加权图中有充给出下面加权图中有充分小权的哈密顿路。分小权的哈密顿路。D1218AFBC1669 715131835132119解解： ADCBEFA 的权和为55，BCADEFB的权和为53，CBADEFC的权和为42，DABCFED的权和为42，EADCBFE的权和为51，FCBADEF的权和为42。说明说明: : “最邻近插入方法最邻近插入方法”是是“最邻近法最邻近法”的的一种改进方法一种改进方法. .该方法是在每次迭代中都构成一个闭该方法是在每次迭代中都构成一个闭的旅行路线。求解时的旅行路线。求解时, ,在已经建立旅程以外的顶点中在已经建立旅程以外的顶点中, ,寻找最临近于旅程中某个顶点的顶点寻找最临近于旅程中某个顶点的顶点, ,然后将其插