第3章树与最短路

1、树树 连通且无回路的无向图称为连通且无回路的无向图称为无向树无向树, ,简称简称树树, ,常常用用T T表示树。表示树。( (即树是不包含回路的连通图即树是不包含回路的连通图) ) 平凡图称为平凡树。平凡图称为平凡树。 若无向图若无向图G G至少有两个连通分支且每个连通分支至少有两个连通分支且每个连通分支都是树都是树, ,则称则称G G为森林。为森林。 在无向树中，悬挂顶点称为在无向树中，悬挂顶点称为树叶树叶，度数大于或，度数大于或等于等于2 2的顶点称为的顶点称为分支点分支点。 注意：树一定是简单连通图。注意：树一定是简单连通图。例：例：判断下列哪些图是树？判断下列哪些图是树？v1v2v3v

2、4v5v1v2v3v4v5v1v2v4v3v5(a)(b)(c)解解: 图图(a)是树是树, 因为它连通又不包含回路。图因为它连通又不包含回路。图(b), (c)不是树不是树, 因为图因为图(b)虽连通但有回路虽连通但有回路, 图图(c)虽无回路但不连通。虽无回路但不连通。 在图在图(a)中中, v1、 v4、 v5为为均为叶，均为叶， v2、 v3均为分支节点。均为分支节点。定理：定理：设设G=G= V,EV,E 是无向图，是无向图，|V|=n|V|=n，|E|=m|E|=m，则下列各命题，则下列各命题是等价的：是等价的： G G是树。（是树。（1 1） G G中无回路且每一对结点之间有且仅

3、有一条路。中无回路且每一对结点之间有且仅有一条路。(5)(5) G G中无回路且中无回路且m=nm=n1 1。(2)(2) G G是连通的且是连通的且m=nm=n1 1。(3)(3) G G是连通的且对任意是连通的且对任意 ,G-e,G-e不连通。不连通。(4)(4) G G中无回路且对任何中无回路且对任何 ，G+eG+e恰好一个圈。恰好一个圈。(6)(6)证明证明： G G是树，所以是树，所以G G是连通的，是连通的， u u V V， v v V V，u u和和v v之间存之间存在一条路。若路不惟一，设在一条路。若路不惟一，设L1L1和和L2L2都是都是u u和和v v之间的路，则之间的路

4、，则L1L1和和L2L2至少有一个异于至少有一个异于u u或者或者v v的公共结点，这样的公共结点，这样L1L1和和L2L2组组成了成了G G中的一个回路，与中的一个回路，与G G是树矛盾。是树矛盾。 ( )eE G( )eE G 先证先证G中无回路。若中无回路。若G中存在某个结点中存在某个结点v上的上的自回路，自回路， u V，由条件知，由条件知u到到v存在一条路存在一条路L1：uv，因为，因为v上有自回路，所以上有自回路，所以u到到v存在另一条存在另一条路路L2：uv，这与，这与G中每一对结点之间存在惟一中每一对结点之间存在惟一的路矛盾。若的路矛盾。若G中存在长度大于等于中存在长度大于等于

5、2的一条回路，的一条回路，则回路上两个结点之间存在不同的路。这与条件则回路上两个结点之间存在不同的路。这与条件是矛盾的。所以是矛盾的。所以G中无回路。中无回路。 以下用归纳法证明以下用归纳法证明m=n1。 当当n=1时，时，G为平凡图，为平凡图，m=0=11=n1。结。结论成立。论成立。 设设nk时，结论成立。下证时，结论成立。下证n=k+1时，结论时，结论也成立。也成立。 设设nk时，结论成立。下证时，结论成立。下证n=k+1时，结论时，结论也成立。也成立。 设设e=(u,v)是是G中的一条边，由于中的一条边，由于G中无回中无回路，所以路，所以 G- e (在在G删除边删除边e所得的子图所得

6、的子图)有两个连有两个连通分支通分支G1和和G2，设它们的边数和结点数分别，设它们的边数和结点数分别为：为：m1，n1和和m2，n2。于是有。于是有n1k和和n2k，由，由归纳假设知：归纳假设知：m1=n11和和m2=n2-1，则：，则：m=m1m21=n1-1n2-11=n-1。 只须证明只须证明G是连通的。若不然，设是连通的。若不然，设G有有t(t2)个连通分支个连通分支G1，G2，Gt，Gi中均无中均无回路，都是树。由回路，都是树。由可知，可知，mi=ni1，i=1,t。于是。于是m=m1m2mt =n1-1n2-1nt-1=n1n2nt-t=nt，由于，由于t2，这，这与与m=n1矛盾

7、。所以矛盾。所以G是连通图。是连通图。 设设e是是G的任意边，删除的任意边，删除e得子图得子图G1，G1中的边数中的边数m1=m-1，G1中的结点数中的结点数n1=n，m1=m1=n-1-1=n-2=n1-2n1-1，所以，所以G1不是连不是连通图（引理）。通图（引理）。 先证先证G中无圈。若中无圈。若G中有圈，删去圈上中有圈，删去圈上任一边仍连通，矛盾。任一边仍连通，矛盾。 再证对任何再证对任何 ,G+e恰好有一个圈：因为恰好有一个圈：因为G是连通且已证是连通且已证G无圈，故无圈，故G是树。由是树。由(2)知，任知，任意两个结之间都有一条路相连，故意两个结之间都有一条路相连，故G+e中必有中

8、必有一个含有一个含有 e的圈；另一方面，若的圈；另一方面，若G+e中有两个中有两个圈含有圈含有e，则，则(G+e)-e=G中仍然含有一个圈，矛中仍然含有一个圈，矛盾。盾。 只须证明只须证明G是连通的，是连通的， u,v V，uv，若若u,v相邻，则相邻，则u与与v连通。否则，连通。否则，G+（u,v）恰）恰好含有一个圈，故好含有一个圈，故u 与与v在在G中连通。由于中连通。由于u与与v是任意的，所以是任意的，所以G是连通图。是连通图。( )eE G定理：定理： 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T中中 至少有两片树叶。至少有两片树叶。证证 : 因为因为T是非平凡树是非平凡树,

9、所以所以T中每个顶点的度中每个顶点的度数都大于等于数都大于等于1, 设设T有有k片树叶片树叶, 则有则有(n-k)个顶点度数大于等于个顶点度数大于等于2,由握手定理可知由握手定理可知 2m=d(vi) k+2(n-k)由由m=n-1,将此结果代入上式后解得将此结果代入上式后解得 k 2。例例：画出：画出5阶所有非同构的无向树。阶所有非同构的无向树。解解：设：设Ti为为5阶无向树阶无向树,则则Ti的边数为的边数为4， Ti的度的度序列之和为序列之和为8，(Ti)4, (Ti)1, 可能的度可能的度序列为：序列为： (1) 1,1,1,1,4; (2) 1,1,1,2,3; (3) 1,1,2,2

10、,2; 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。解解：由握手定理：由握手定理 2m=d(vi) 及及n = m+1, 设设G有有t个个1顶点顶点, 则有下列关系式则有下列关系式 22+13+4 3+t =2 m =2 x(n-1) =2 x(2+1+3+t-1) 解得：解得：t = 9 。例例：无向树：无向树G有有2个个2度结点，度结点，1个个3度结点，度结点，3个个4度结点，则其度结点，则其1度结点数为多少？度结点数为多少？ 解解：设：设G有有t个个4度分支点，则有下列关系式度分支点，则有下列关系式 8 1+2 3+ t 4 =2 (8+2+t-1) 解得：解得：t = 2

11、 则则G中共有中共有12个顶点，个顶点，11条边，度数序列之条边，度数序列之 和为和为22， (Ti)=4, (Ti)=1, 度序列为：度序列为： 1,1,1,1,1,1,1,1,3,3,4, 4 其非同构的图形为：其非同构的图形为：例例 ：无向树：无向树G有有8片树叶，片树叶，2个个3度分支点，其度分支点，其余分支点均为余分支点均为4度，问度，问G有多少个有多少个4度分支点？度分支点？画出其非同构的情况。画出其非同构的情况。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。

12、。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。其非同构的图形为：其非同构的图形为： 解解： 有如下有如下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阶所有非同构的无向树。阶所有非同构的无向树。生成树生成树 设设G为无向图，若为无向图，若G的生成子图是一棵的生成子图是一棵树，则该树称为树，则该树称为G的的生成树生成树。设。设G的生成树的生成树为为T，则，则T中的边称为树枝。在中的边称为树枝。在G中但不在中但

13、不在生成树生成树T中的边称为中的边称为弦弦。T的所有弦的集合的所有弦的集合的导出子图称为的导出子图称为T的的余树余树。注意：注意：余树不一定是树。余树不一定是树。 一个无向连通图，如果它本身不是树，一个无向连通图，如果它本身不是树，它的生成树是不唯一的。但所有的连通图都它的生成树是不唯一的。但所有的连通图都具有生成树。具有生成树。 例例：在下图中，：在下图中，(2)为为(1)的一棵生成树的一棵生成树T， (3)为为T的余树，但（的余树，但（3）不是树。）不是树。abcdeabcdeabcd(1)(2)(3) 定理：定理：无向图无向图G G具有生成树的充分必要条件是具有生成树的充分必要条件是G

14、G为连通图。为连通图。 证明证明：若无向图：若无向图G G具有生成树，显然具有生成树，显然G G为连通图。为连通图。以下证明若无向图以下证明若无向图G G为连通图，则为连通图，则G G具有生成树。具有生成树。 若连通图若连通图G G无回路，则无回路，则G G本身就是一棵生成树；若本身就是一棵生成树；若G G至少有一个回路，删除此回路的一边，得到子图至少有一个回路，删除此回路的一边，得到子图G G1 1，它，它仍然连通，并与仍然连通，并与G G有相同结点集。若有相同结点集。若G G1 1无回路，则无回路，则G G1 1就就是一棵生成树；若是一棵生成树；若G G1 1仍有一个回路，再删除仍有一个回

15、路，再删除G G1 1回路上的回路上的一边。重复上述过程，直至得到一个无回路的连通图，一边。重复上述过程，直至得到一个无回路的连通图，该图就是一棵生成树。该图就是一棵生成树。 由该定理的证明过程可以看出，一个连通图可以有由该定理的证明过程可以看出，一个连通图可以有多个生成树。因为在取定一个回路后，就可以从中去掉多个生成树。因为在取定一个回路后，就可以从中去掉任一条边，去掉的边不同，可能得到的生成树也不同。任一条边，去掉的边不同，可能得到的生成树也不同。 推论推论1: 无向连通图无向连通图G有有n个结点和个结点和m条边，则条边，则mn1。 证明证明：由上述定理的证明知，：由上述定理的证明知，G有

16、生成树，有生成树，设为设为T。 |E(G)|=m，其中，其中，E(G)是图是图G的边构的边构成的集合。成的集合。|E(T)|=n1, 其中，其中，E(T)是树是树T的边的边构成的集合。而构成的集合。而|E(G)|E(T)|，所以，所以mn1。推论推论2： 在无向连通图中，一个回路和任何一在无向连通图中，一个回路和任何一棵生成树的补至少有一条公共边。棵生成树的补至少有一条公共边。 证明：证明：若有一个回路和一棵生成树的补若有一个回路和一棵生成树的补无公共边，那么，这个回路包含在该生成树无公共边，那么，这个回路包含在该生成树中，这与树的定义矛盾。中，这与树的定义矛盾。 推论推论3 3： 在无向连通

17、图中，一个边割集和在无向连通图中，一个边割集和任何一棵生成树至少有一条公共边。任何一棵生成树至少有一条公共边。 证明：证明：若有一个边割集和一棵生成树若有一个边割集和一棵生成树无公共边，那么，删除这个边割集所得的无公共边，那么，删除这个边割集所得的子图必包含该生成树，从而该子图是连通子图必包含该生成树，从而该子图是连通的。这与边割集的定义矛盾。的。这与边割集的定义矛盾。 设设G为无向连通图，有为无向连通图，有n个结点和个结点和m条边。条边。T为为G的生成树，的生成树，T有有n个结点和个结点和n-1条边。所以要得到条边。所以要得到G的一棵生成树，必须的一棵生成树，必须删除删除G的的m-(n-1)

18、=mn1条边。条边。 最小生成树最小生成树 设无向连通带权图设无向连通带权图G=,TG=,T是是G G的一的一棵生成树，棵生成树，T T的各边权之和称为的各边权之和称为T T的的权权，记作，记作W(T)W(T)。G G的所有生成树中权最小的生成树称为的所有生成树中权最小的生成树称为G G的的最小生成树最小生成树。 求最小生成树的算法很多，我们只介绍求最小生成树的算法很多，我们只介绍避圈避圈法（法（克鲁斯克尔克鲁斯克尔Kruskal算法）。算法）。 设设n阶无向连通带权图阶无向连通带权图G=有有m条条边边,不妨设不妨设G中无环中无环(否则可先删去否则可先删去)，算法为：，算法为：(1) 将将m条

19、边按权从小到大顺序排列，设为条边按权从小到大顺序排列，设为 e1,e2, ,em。(2) 取取e1在在T中，然后依次检查中，然后依次检查e2, ,em ，若，若ej (j=2,3, ,m)与与T中的边不能构成回路，则取中的边不能构成回路，则取ej在在T中，否则放弃中，否则放弃ej，考虑下一条边，直至，考虑下一条边，直至jm。(3) 算法停止时得到的算法停止时得到的T为为G的最小生成树。的最小生成树。Kruskal算法算法 一种求最小生成树的算法一种求最小生成树的算法例：例：下图下图 (a)给出了一个赋权图给出了一个赋权图G，用，用kruskal算法求出算法求出G的最小生成树。的最小生成树。 解

20、：解：先将先将m条边按权由小到大排列：条边按权由小到大排列： (v4,v5)，(v1,v8)，(v5,v7)，(v6,v7)，(v4,v6)，(v5,v6)， (v2,v7)，(v2,v5)，(v7,v8)，(v2,v3)，(v3,v4)，(v1,v2)。它们的权分别是：它们的权分别是：3,4,5,6,6.5,7,7.5,8,10.5,11,12,13。 逐次取边：逐次取边：(v4,v5),(v1,v8),(v5,v7),(v6,v7),(v2,v7),(v7,v8), (v2,v3) 构成的生成树在下图构成的生成树在下图 (b)，这是，这是G的最小生成树。最的最小生成树。最小生成树小生成树T

21、的权的权C(T)=3+4+5+6+7.5+10.5+11=47。 例例: :用避圈法求下图所示的最小生成树用避圈法求下图所示的最小生成树abcdef5555136642解解: W(T)=1+2+3+4+5 =15，图中黄色为最，图中黄色为最小生成树。小生成树。bacd762fe81443472356321hg例：例：铺设一个连接各个城市的光纤通信网络。铺设一个连接各个城市的光纤通信网络。图中蓝色为图中蓝色为最小生成树最小生成树。普里姆算法的基本思想：普里姆算法的基本思想： 假设假设N=(V,E)是连通图，是连通图，TE是是N上最小生成树上最小生成树中边的集合。算法从中边的集合。算法从U=u0(

22、u0V)，TE=开始开始，重复执行下述操作：在所有，重复执行下述操作：在所有uU, v V-U的的边边(u,v)E中找一条代价最小的边中找一条代价最小的边(u0,v0)并入集并入集合合TE，同时，同时v0并入并入U，直至，直至U=V为止。此时为止。此时TE中中必有必有n-1条边，则条边，则T=(V,TE)为为N的最小生成树的最小生成树。 简单地说简单地说： 取图中任意一个顶点 u U作为生成树的根，之后往生成树上添加新的顶点 v V-U。在添加的顶点 v和已经在生成树上的顶点u 之间必定存在一条边(u,v)，并且该边的权值在所有连通顶点集U 和 V-U 之间的边中取值最小。之后继续往生成树上添

23、加顶点，直至生成树上U含有 n 个顶点为止。Prim算法算法ABCDEF6515366452A,C,F,D,B,EBE3BE3EA,C,F,D,BCB5CE6CB5B,EA,C,F,DFD2CE6FD2CB5B,D,EA,C,FCF4CF4CE6AD5CB5B,D,E,FA,CAC1AD5AC1AB6B,C,D,E,FATEFEDCBV-UUABCDEF15342算法分析：算法分析： 普里姆算法的时间复杂度为普里姆算法的时间复杂度为O O( (n n2 2) )。 该算法与网中的边的数目无关。该算法与网中的边的数目无关。 适用于求边稠密的网的最小生成树适用于求边稠密的网的最小生成树。返回 避圈

24、法避圈法是贪婪地增加不构成回路的边，以是贪婪地增加不构成回路的边，以求得最小生成树。求得最小生成树。 从另一个角度来考虑最小生成树问题，由从另一个角度来考虑最小生成树问题，由G的圈（回路）最优条件，我们也可以在原连的圈（回路）最优条件，我们也可以在原连通权图通权图G中逐步删除构成回路中中逐步删除构成回路中权最大的边权最大的边，最后剩下的无回路的生成子图为最小成树。我最后剩下的无回路的生成子图为最小成树。我们把这种方法称为们把这种方法称为“破圈法破圈法”。例例 ：在图在图(a)中给出了一个连通图中给出了一个连通图, 求此图的求此图的生成树。生成树。(a)根树及其应用根树及其应用 一个有向图，略去

25、方向后是树，则称这个一个有向图，略去方向后是树，则称这个有向图为有向图为有向树有向树。如果一棵有向树恰有一个结。如果一棵有向树恰有一个结点入度为点入度为0，其余所有结点入度为，其余所有结点入度为1，此有向树，此有向树称为称为根树根树。在根树中，入度为。在根树中，入度为0的结点称为的结点称为树根树根，出度为出度为0的结点称为的结点称为树叶树叶，出度不为，出度不为0的结点称的结点称为为分枝点分枝点或或内点内点。从此定义可以看出，在根树。从此定义可以看出，在根树中，除了树叶都是分枝点或内点外，树根也是中，除了树叶都是分枝点或内点外，树根也是分枝点。分枝点。 (1)(2)v0v1v2v3v4v5v6v

26、7v0v1v2v3v4v5v6v7例例: 下图下图(1)为一棵根树。为一棵根树。V0为树根为树根, v1,v4, v3, v6, v7为树为树叶叶, v2, v5为内点为内点, v0, v2, v5为均为分支点为均为分支点, 由于在根树中由于在根树中有向边的方向均一致有向边的方向均一致, 故可省掉其方向故可省掉其方向, 如图如图(2)。v0v1v2v3v4v5v6v7从树根到从树根到T的任意顶点的任意顶点v的通路（路径）长度称为的通路（路径）长度称为v的的层数层数，层数最大顶点的层数称为，层数最大顶点的层数称为树高树高，平凡树也称为，平凡树也称为根树。根树。例：例： 下下图中图中, v1,v2

27、, v3,在第一层上，在第一层上，v4, v5 在第二层上，在第二层上，v6, v7在第三层上。树高为在第三层上。树高为3。家族树家族树 设设T为非平凡的根树，为非平凡的根树，u，v为其两个为其两个顶点，顶点， a)若若u可达可达v，则称，则称u是是v的祖的祖先，先，v是是u的后代；的后代； b)若若u邻接到邻接到v，则称，则称u是是v的父亲，的父亲，v是是u的儿子；的儿子；c)若若u，v有相同的父亲，则称有相同的父亲，则称u，v是兄弟；是兄弟；d)d)称称v v及其后代的导出子图为及其后代的导出子图为T T以以v v为根的根子树。为根的根子树。uv1v2v3n在根树中，若每个结点的出度小于或

28、等于在根树中，若每个结点的出度小于或等于m，则称该树为，则称该树为m叉树叉树。n在在m叉树中，若每个结点的出度恰等于叉树中，若每个结点的出度恰等于0或或m，则称该树为，则称该树为完全完全m叉树叉树。n在完全在完全m叉树中，若所有树叶层数相同，叉树中，若所有树叶层数相同，则称该树为则称该树为正则正则m叉树叉树。 当当m=2时，时，m叉树就是二叉树，完全叉树就是二叉树，完全m叉叉树就是树就是完全二叉树完全二叉树。（a）是）是2叉树，（叉树，（b）是正则）是正则2叉树叉树（c）是完全）是完全2叉树。叉树。定理定理：在完全：在完全m叉树中，其树叶数为叉树中，其树叶数为t，分，分枝点数为枝点数为i，则，

29、则 (m-1)i=t-1。 证明证明：由定理的条件知，该树有：由定理的条件知，该树有it个个结点，该树边数为结点，该树边数为it-1。 另一方面，由完另一方面，由完全全m叉树定义知，该树出度的和为：叉树定义知，该树出度的和为：mi，这，这也是该树的边数，于是有也是该树的边数，于是有mi=it-1。 整理整理后有后有(m-1)i=t-1。 最优二叉树最优二叉树： 设设T是一棵二叉树，有是一棵二叉树，有t片树叶片树叶v1，v2， ，vt，分，分别带权别带权W!，W2， ，Wt，则称，则称T为赋权二叉树或带权为赋权二叉树或带权二叉树。在赋权二叉树二叉树。在赋权二叉树T中，中， 称为树称为树T的权。记

30、的权。记为为W(T)。在所有有。在所有有t片树叶的二叉树中，如果片树叶的二叉树中，如果t片树叶分片树叶分别带权别带权W!，W2， ，Wt，权，权W(T)最小的二叉树，称最小的二叉树，称为最优二叉树。为最优二叉树。 )(1itiivlW 在下图所示的三棵树中在下图所示的三棵树中,都是带权都是带权1,3,4,5,6的二元的二元树树,W(T1)=47, W(T2)=54, W(T3)=42,但它们中有无但它们中有无最最优二叉树。优二叉树。是否有最优二叉树？最优权重是多少？是否有最优二叉树？最优权重是多少？T T1 1T T2 2T T3 34 4 5 51 16 63 33 34 45 56 61

31、11 13 36 64 45 5Huffman算法算法 一种求最优二叉树的算法一种求最优二叉树的算法 设设T T是有是有t t片叶子的二叉树片叶子的二叉树, ,其中其中t t片叶子分别片叶子分别带有权带有权 1 1, , 2 2, , , t t, ,称称T T为加权二叉树为加权二叉树, ,称为二叉树称为二叉树T T的权的权, ,其中其中l li i为带权为带权 i i的树叶的树叶v vi i的层数。的层数。 在所有带权在所有带权 1 1, , 2 2, , , t t的二叉树中的二叉树中, ,带权最带权最小的二叉树称为最优二叉树。小的二叉树称为最优二叉树。 19521952年年, ,哈夫曼给

32、出了求最优二叉树的算法哈夫曼给出了求最优二叉树的算法, ,该该算法的算法的 核心思想为核心思想为: :从带权从带权 1 1+ + 2 2, , 3 3, , , t t的最的最优二叉树可得到优二叉树可得到带权带权 1 1, , 2 2, , , t t的最优二叉树的最优二叉树. . 基本步骤如下基本步骤如下: :( )ti iiW Tl哈夫曼算法的步骤哈夫曼算法的步骤 给定实数给定实数 1, 2, t且且 12 t(1)连接连接 1, 2 为权的两片叶子为权的两片叶子,得一分枝点得一分枝点,其权为其权为 1+ 2。(2)在在 1+ 2, 3, t中选出两个最小的权中选出两个最小的权,连接它们对

33、应的顶点连接它们对应的顶点(不一定都是树叶不一定都是树叶)得分得分枝点及所带的权。枝点及所带的权。(3)重复重复(2),直到形成直到形成t-1个分枝点个分枝点, t片叶子为止。片叶子为止。例例: :求带权求带权1,3,4,5,61,3,4,5,6的最优二元树。的最优二元树。4 44 48 81 13 33 38 84 43 31 11 13 34 45 56 64 44 411115 56 61 14 48 811111919 连接权为连接权为w1,w2的两片树叶的两片树叶, 得一个分支点其权为得一个分支点其权为w1+w2 在在w1+w2 ,w3, ,wt中中选出两个最小的权选出两个最小的权,

34、 连接连接它们对应的顶点它们对应的顶点(不一定不一定是树叶是树叶), 得得 分支点及所分支点及所带的权。带的权。 重复重复 , 直到形成直到形成t-1个分支点个分支点, t片树叶为止片树叶为止(若得到的权比后续的两若得到的权比后续的两个权大个权大,则另开分支则另开分支)最优二叉树在通信编码中的应用最优二叉树在通信编码中的应用 设设 = 1 2 n-1 n为长为为长为n的符号串的符号串, 称其子串称其子串 1 , 1 2 , , 1 2 n-1 分别为该符号串的长分别为该符号串的长度为度为1,2, n-1的的前缀。前缀。 设设B=1 ,2 , ,m 为一个符号串集合为一个符号串集合, 若对于任意

35、的若对于任意的i , j B, i j, i , j , 互不为前互不为前缀缀, 则称则称B为为前缀码。前缀码。 若符号串中若符号串中i(i=1,2, , m)只出现只出现0, 1两两个符号个符号, 则称则称B为为二元前缀码二元前缀码。又如又如： 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,10

36、1,001,0011 不是前缀码不是前缀码若使用前缀码中的若使用前缀码中的0、1序列表示英文字母，当接收者序列表示英文字母，当接收者收到收到0、1组成的长串时，就可以惟一的、准确无误地组成的长串时，就可以惟一的、准确无误地分割成字母对应的分割成字母对应的0、1序列。序列。定理：定理：任意一个二叉树，可以产生惟一的前任意一个二叉树，可以产生惟一的前缀码。缀码。 证明：证明：在二叉树中，每一个分枝点引出在二叉树中，每一个分枝点引出的左侧边标记的左侧边标记0，右侧边标记，右侧边标记1。由根结点到。由根结点到树叶的路经上各边的标记组成的树叶的路经上各边的标记组成的0、1序列作序列作为该片树叶的标记。显

37、然，没有一片树叶的为该片树叶的标记。显然，没有一片树叶的标记是另一片树叶的标记的前缀。所有树叶标记是另一片树叶的标记的前缀。所有树叶的标记构成了一个前缀码。的标记构成了一个前缀码。由上面做法知，由上面做法知， vi处的符号串的前缀均在处的符号串的前缀均在vi所所在的通路上除在的通路上除vi外的顶点处达到，因而所得外的顶点处达到，因而所得符号串集合为二元前缀码。符号串集合为二元前缀码。 010110101000100010101111例：例：右图所示的二元树右图所示的二元树产生的前缀吗为产生的前缀吗为11,00,011,0100,0101利用利用Huffman算法求出的最优算法求出的最优2叉树产

38、生的叉树产生的前缀码称为前缀码称为最佳前缀码最佳前缀码。例例: 在通信中在通信中, 0,1,2,3,4,5,6,7出现的频率如下出现的频率如下 0：30, 1：20, 2： 15 3：10, 4：10, 5： 5 6： 5, 7：5 求传输它们的求传输它们的最佳前缀码最佳前缀码100604030302020151510555010101010101101001000000000100010011001011101解解:将各字符出现的频率作为其相应将各字符出现的频率作为其相应的权的权 1=5, 2=5, 3=5, 4=10, 5=10, 6=15, 7=20, 8=30为为8个权个权,利用利用H

39、uffman算法求出的算法求出的最优最优2叉树如图所示叉树如图所示(码长取码长取3,如如101传传5)图中方框中的图中方框中的8个码子是个码子是最佳前缀码最佳前缀码。树。树T是带权是带权 1, 2, 8的最优二叉树。带权为的最优二叉树。带权为 i的树叶的树叶vi对应的码子传输出现频率为对应的码子传输出现频率为 i, 的数字，即的数字，即11传传1, 101传传401传传0, 0001传传5 001传传2, 101传传4 11传传1, 00001传传6 100传传3, 00000传传7。决策树决策树 若树的每个内点都对应着一次决策若树的每个内点都对应着一次决策, ,这些顶这些顶点的子树都对应着该

40、决策的每种可能结果点的子树都对应着该决策的每种可能结果, ,这样的这样的有序树称为有序树称为决策树决策树。例例：有：有8 8枚外观相同的硬币枚外观相同的硬币, ,其中有其中有7 7枚重量相同枚重量相同, ,而而剩余的一枚伪币较轻剩余的一枚伪币较轻, ,要求以比较重量的方法用一要求以比较重量的方法用一架天平去找出伪币。架天平去找出伪币。解解: :用用1-81-8标记硬币标记硬币, ,每次衡量有每次衡量有3 3种可能种可能: :左旁低下左旁低下, ,保持水平保持水平, ,右旁低下右旁低下, ,下图给出这一解决过程的决策下图给出这一解决过程的决策图。图中图。图中表示不会出现的结果。表示不会出现的结果

41、。决策树的结点左侧标记着状态决策树的结点左侧标记着状态, ,这里表示包含有伪币这里表示包含有伪币的硬币集合的硬币集合, ,右侧标记测试内容右侧标记测试内容。1,2,3,81,2,3对6,7,8右旁低下左旁低下1,2,31对332154876说明说明: :( (1)1)决策树的每一内部结点对应于一个部分解决策树的每一内部结点对应于一个部分解; ;每个叶子对应于一个解。每一内部结点联结于一个每个叶子对应于一个解。每一内部结点联结于一个获得新信息的测试。从每一结点出发的每一枝标记获得新信息的测试。从每一结点出发的每一枝标记着不同的测试结果。一个解决过程的执行对应于通着不同的测试结果。一个解决过程的执

42、行对应于通过从根到叶的一条路。一个决策树是所有可能的解过从根到叶的一条路。一个决策树是所有可能的解决路的集合。决路的集合。(2)(2)可以用决策树估计排序的最坏情况时间。排序问题可可以用决策树估计排序的最坏情况时间。排序问题可描述为描述为: :将将n n个元素个元素x x1 1,x,x2 2, , ,x xn n按升序或降序排列。这按升序或降序排列。这里将研究的排序算法基于二叉比较里将研究的排序算法基于二叉比较, ,即一次比较两个元即一次比较两个元素，每次这样的比较都缩小了可能的排序集合。因此素，每次这样的比较都缩小了可能的排序集合。因此, ,基于二叉比较的排序算法可以表示成二叉树基于二叉比较

43、的排序算法可以表示成二叉树, ,其中每个其中每个内点表示两个元素的一次比较内点表示两个元素的一次比较, ,每个树叶表示每个树叶表示n n个元素个元素的的n!n!种排列种的一种。种排列种的一种。二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历 访问一棵根树的每个顶点一次且仅一次称为树的遍历。遍历一棵二叉树的方法常有如下三种：（1）中序遍历法中序遍历法：访问顺序为“左子树、树根、右子树”；（2）前序遍历法前序遍历法：访问顺序为“树根、左子树、右子树”；（3）后序遍历法后序遍历法：访问顺序为“左子树、右子树、树根”。 例：例：试用三种周游方式行遍下图。试用三种周游方式行遍下图。中序行遍法访问此树中序

44、行遍法访问此树：(a(b+c)+def ) (g+(h-i)j)前序行遍法访问此树：前序行遍法访问此树：(+(+(a (+b c )a (+b c )d (d (e f ) +g (e f ) +g (- h i j )(- h i j )后序行遍法访问此树：后序行遍法访问此树：a b c + de f+ g h i - j + 图图G G的一个顶点的一个顶点v v的的离径离径R(v)R(v)定义为定义为: : 所有满足所有满足R(vR(v)=R(G)=R(G)的顶点的顶点v v都称为都称为G G的中心的中心. .显然一个图的直径为显然一个图的直径为: : ),(max)()(uvdvRGVu

45、()( )min ( )v V GR GR v()max ( )v V GR v图图G的半径的半径R(G)定义为：定义为：例例.求下图求下图G的每个结点的离径及图的每个结点的离径及图G的直径的直径,半径和中心半径和中心.u1u3u6u2u5u4定理定理 设设P=u1u2ulul+1是树是树T的一条最长路的一条最长路,则则(1)T的直径为的直径为l;(2)若若l为奇数为奇数,设设l=2k-1,则则T的半径为的半径为k,T有两个有两个相邻的中心相邻的中心,即为即为ukuk+1.并且每一条长为并且每一条长为l的路的路都通过这两个中心都通过这两个中心.(2)若若l为偶数为偶数,设设l=2k,则则T的半

46、径为的半径为k,T中只有一中只有一个中心个中心,即为即为uk+1.并且每一条长为并且每一条长为l的路都通过的路都通过该中心该中心.定理的证明证:(1)由于P=u1u2ulul+1是是T中的一条最长路中的一条最长路,故故d(u1,ul+1)=l即为即为T的直径的直径.(2)设设u是是T中的任意一个结点中的任意一个结点,则则d(u,u1)+d(u,u2k)= d(u1,u)+d(u,u2k) d(u1,u2k)=2k-1,因因此此u的离径的离径R(u) k.从而从而T的半径的半径R(T) k. 对于对于T中任意一个结点中任意一个结点u,若若u在在P上上,显然有显然有d(u,uk) k.若若u不在不

47、在P上上,由由T的连通性的连通性,P中必存在一中必存在一个顶点个顶点ui(2 i 2k-1=l),T中有一条连接中有一条连接u与与ui的路的路Q,使使u1,.,ui-1,ui+1,u2k都不在都不在Q上上. 因为因为P是是T中的最长路中的最长路,故有故有:d(u,ui) i-1; d(u,ui) l+1-i 若若i k,因为因为d(ui,uk)=k-i,故故d(u,uk)=d(u,ui)+d(ui,uk) i-1+k-ik,则则d(u,uk)=d(u,ui)+d(ui,uk) l+1-i+i-k= l+1-k=2k-k=k(l=2k-1)所以对所以对T中的任意结点中的任意结点u有有d(u,uk

48、) k,故故R(uk) k,从从而而R(T) k.综合上述论证易得综合上述论证易得R(T) =k,且且R(uk)=k,即即uk为为T的一个中心的一个中心.同理可证同理可证uk+1为为T的一个中心的一个中心. 下证长为下证长为l的任意一条路的任意一条路P一定过中心一定过中心uk与与uk+1.设设P的两个端点分别是的两个端点分别是u和和u,则则u和和u均不在均不在P上上.对对P上的任意两个内部点上的任意两个内部点ui和和uj,由由T的连通性的连通性,T中一定中一定存在存在u-ui路路Q1和和u-uj路路Q2,使得使得(V(Q1)-ui) V(P)=; (V(Q2)-uj) V(P)=.不妨设不妨设

49、i j.因为因为T是树是树,故故P=Q1 P(ui,uj) Q2. 若若i j k,则则 d(u,u) d(u,ui)+ d(ui,uj)+ d(uj,u) (i-1)+(j-i)+(j-1)=2(j-1) 2(k-1)2k-1=l同理同理,若若ki j,则则d(u,u) l.与与P为长是为长是l的的u-u路矛路矛盾盾.因此因此i kj,所以结论正确所以结论正确. 同理可证同理可证(3).最短路问题 一、问题的提出一、问题的提出 )(G赋权图（网络）：赋权图（网络）： G=(V, E) 中，给每条边中，给每条边 a= 赋予一个非负实数权赋予一个非负实数权 wij ，得到一个有向网，得到一个有向

50、网络络 路径非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和带权图的路径长度是指路径上各边的权之和距离矩阵距离矩阵 对上述网络，定义对上述网络，定义 D=(dij)n n，n=|V| wij 当当 E dij = 其它其它带权路径长度带权路径长度 对上述网络，路径对上述网络，路径 v1, v2 , ,vk 的带权路径长度定义为的带权路径长度定义为1,11ki iidw最短路问题在实际工作中应用最短路问题在实际工作中应用1、通讯网络中最可靠问题、通讯网络中最可靠问题2、最大容量问题、最大容量问题3、统筹方法中求关键路线、统筹方

51、法中求关键路线4、背包问题、背包问题5、选址问题、选址问题6、工件加工顺序问题、工件加工顺序问题7、中国邮递员问题、中国邮递员问题背包问题背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。 例一位旅客要从一位旅客要从A城到城到B城城1.他希望选择一条途中中转次数最少的路线；他希望选择一条途中中转次数最少的路线；2.他希望选择一条途中所花时间最短的路线；他希望选择一条途中所花时间最短的路线；3.他希望选

52、择一条途中费用最小的路线；他希望选择一条途中费用最小的路线；v5v4v3v2v1v0 100 6030101020 5 50这些问题均是带权图上的最短路径问题。这些问题均是带权图上的最短路径问题。1. 边上的权表示一站边上的权表示一站2. 边上的权代表距离边上的权代表距离3. 边的权代表费用边的权代表费用 Dijkstra算法 Floyd算法 Floyd-Warshall算法 Dijkstra算法算法 Dijkstra算法是由荷兰计算机科学家算法是由荷兰计算机科学家狄克斯特拉狄克斯特拉（Dijkstra）于）于1959 年提出的，因此又叫狄克斯特拉算法。年提出的，因此又叫狄克斯特拉算法。是从一

53、个顶点到其余各顶点的最短路径算法，解决的是有向是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。图中最短路径问题。 荷兰计算机科学教授荷兰计算机科学教授Edsger W.Dijkstra(1930-) 在在1972年获年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。望的奖项之一。 Dijkstra算法是求出一个连通加权简单图中从结点算法是求出一个连通加权简单图中从结点a到结到结点点z的最短路。边的最短路。边(i,j)的权的权(i,j)0，且结点，且结点x的标号为的标号为L(x)。结束时，结束时，L(z

54、)是从是从a到到z的最短长度。的最短长度。 举例来说，如果图中的顶点表示城市，而边上的举例来说，如果图中的顶点表示城市，而边上的权重权重表表示城市间开车行经的距离。示城市间开车行经的距离。 Dijkstra算法可以用来找到两个算法可以用来找到两个城市之间的最短路径。城市之间的最短路径。 Dijkstra算法基本思想:把图中所有结点分为两组，每一个结点对应一个距离值。 第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度； 第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度。 按最短路径长度递增的顺序把第二组的结

55、点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。设源点为v0v初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点） v然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：v若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值vm的距离值+Wmi），则要修改vi的距离（vi的距离值vm的距离值+Wmi）。修改后

56、再选距离值最小的一个结点加入到第一组中，。 如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。EvvEvvwdistiiii),(),(000procedure Dijkstra(G:所有权都为正数的加权连通简单图)G带有顶点av0,v1,vnz和权(vi,vj)，若(vi,vj)不是G的边，则(vi,vj)for i:1 to nL(vi)L(a):0S: （初始化标记，a的标记为0，其余结点标记为，S是空集while z S beginu:不属于S的L(u)最小的一个顶点S:Su for 所有不属于S的顶点

57、v if L(u)(u,v)L(v) then L(v):L(u)(u,v) 这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记 endL(z)从a到z的最短长度 下面给出该算法的框图：下面给出该算法的框图： 0次迭代 L(a)0L(b)L(c)L(d)L(e)L(z)S1次迭代ua，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(e)L(z)2次迭代uc，Sa,cL(c)(c,b)213L(b)L(c)(c,d)2810L(d)L(c)(c,e)21012L(e)L(

58、c)(c,z)2L(b)3，L(d)10，L(e)12，L(z)3次迭代ub，Sa,c,bL(b)(b,d)358L(d)L(b)(b,e)3145623108abcdez用Dijkstra算法求a和z之间最短路所用的步骤。 L(b)(b,z)3L(d)8，L(e)12，L(z)4次迭代ud，Sa,c,b,dL(d)(d,e)8210L(e)L(d)(d,z)8614L(z)L(e)10，L(z)145次迭代ue，Sa,c,b,d,eL(e)(e,z)10313L(z)L(z)13结 束uz，Sa,c,b,d,e,z从a到z的最短路的长度为13。DijkstraDijkstra算法只求出图中一

59、个特定的顶点到其他各定点的最算法只求出图中一个特定的顶点到其他各定点的最短路。但在许多实际问题中，需求出任意两点之间的最短路，短路。但在许多实际问题中，需求出任意两点之间的最短路，如全国各城市之间最短的航线，选址问题等。当然，要求出如全国各城市之间最短的航线，选址问题等。当然，要求出一个图的任意两点间的最短距路，只需将图中每一个顶点依一个图的任意两点间的最短距路，只需将图中每一个顶点依次视为始点，然后用次视为始点，然后用DijkstraDijkstra算法就可以了。算法就可以了。DijkstraDijkstra算法可以应用与物流配送中算法可以应用与物流配送中 OSPFOSPF（open sho

60、rtest path first, open shortest path first, 开放最短路径优先）算开放最短路径优先）算法是法是DijkstraDijkstra算法在网络路由中的一个具体实现。算法在网络路由中的一个具体实现。 Floyd算法如果有一个矩阵D=d(ij)，其中d(ij)0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=无穷大。通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。【分析】 对于任何一个城市而言，i 到 j 的最短距离不外乎存在经过 i 与 j 之间的k和不经过k两种可能，所以可以令k=1，2，3，.，n(n是城市