第3章樹(shù)與最短路

1、樹(shù)樹(shù) 連通且無(wú)回路的無(wú)向圖稱為連通且無(wú)回路的無(wú)向圖稱為無(wú)向樹(shù)無(wú)向樹(shù), ,簡(jiǎn)稱簡(jiǎn)稱樹(shù)樹(shù), ,常常用用T T表示樹(shù)。表示樹(shù)。( (即樹(shù)是不包含回路的連通圖即樹(shù)是不包含回路的連通圖) ) 平凡圖稱為平凡樹(shù)。平凡圖稱為平凡樹(shù)。 若無(wú)向圖若無(wú)向圖G G至少有兩個(gè)連通分支且每個(gè)連通分支至少有兩個(gè)連通分支且每個(gè)連通分支都是樹(shù)都是樹(shù), ,則稱則稱G G為森林。為森林。 在無(wú)向樹(shù)中，懸掛頂點(diǎn)稱為在無(wú)向樹(shù)中，懸掛頂點(diǎn)稱為樹(shù)葉樹(shù)葉，度數(shù)大于或，度數(shù)大于或等于等于2 2的頂點(diǎn)稱為的頂點(diǎn)稱為分支點(diǎn)分支點(diǎn)。 注意：樹(shù)一定是簡(jiǎn)單連通圖。注意：樹(shù)一定是簡(jiǎn)單連通圖。例：例：判斷下列哪些圖是樹(shù)？判斷下列哪些圖是樹(shù)？v1v2v3v

2、4v5v1v2v3v4v5v1v2v4v3v5(a)(b)(c)解解: 圖圖(a)是樹(shù)是樹(shù), 因?yàn)樗B通又不包含回路。圖因?yàn)樗B通又不包含回路。圖(b), (c)不是樹(shù)不是樹(shù), 因?yàn)閳D因?yàn)閳D(b)雖連通但有回路雖連通但有回路, 圖圖(c)雖無(wú)回路但不連通。雖無(wú)回路但不連通。 在圖在圖(a)中中, v1、 v4、 v5為為均為葉，均為葉， v2、 v3均為分支節(jié)點(diǎn)。均為分支節(jié)點(diǎn)。定理：定理：設(shè)設(shè)G=G= V,EV,E 是無(wú)向圖，是無(wú)向圖，|V|=n|V|=n，|E|=m|E|=m，則下列各命題，則下列各命題是等價(jià)的：是等價(jià)的： G G是樹(shù)。（是樹(shù)。（1 1） G G中無(wú)回路且每一對(duì)結(jié)點(diǎn)之間有且僅

3、有一條路。中無(wú)回路且每一對(duì)結(jié)點(diǎn)之間有且僅有一條路。(5)(5) G G中無(wú)回路且中無(wú)回路且m=nm=n1 1。(2)(2) G G是連通的且是連通的且m=nm=n1 1。(3)(3) G G是連通的且對(duì)任意是連通的且對(duì)任意 ,G-e,G-e不連通。不連通。(4)(4) G G中無(wú)回路且對(duì)任何中無(wú)回路且對(duì)任何 ，G+eG+e恰好一個(gè)圈。恰好一個(gè)圈。(6)(6)證明證明： G G是樹(shù)，所以是樹(shù)，所以G G是連通的，是連通的， u u V V， v v V V，u u和和v v之間存之間存在一條路。若路不惟一，設(shè)在一條路。若路不惟一，設(shè)L1L1和和L2L2都是都是u u和和v v之間的路，則之間的路

4、，則L1L1和和L2L2至少有一個(gè)異于至少有一個(gè)異于u u或者或者v v的公共結(jié)點(diǎn)，這樣的公共結(jié)點(diǎn)，這樣L1L1和和L2L2組組成了成了G G中的一個(gè)回路，與中的一個(gè)回路，與G G是樹(shù)矛盾。是樹(shù)矛盾。 ( )eE G( )eE G 先證先證G中無(wú)回路。若中無(wú)回路。若G中存在某個(gè)結(jié)點(diǎn)中存在某個(gè)結(jié)點(diǎn)v上的上的自回路，自回路， u V，由條件知，由條件知u到到v存在一條路存在一條路L1：uv，因?yàn)椋驗(yàn)関上有自回路，所以上有自回路，所以u(píng)到到v存在另一條存在另一條路路L2：uv，這與，這與G中每一對(duì)結(jié)點(diǎn)之間存在惟一中每一對(duì)結(jié)點(diǎn)之間存在惟一的路矛盾。若的路矛盾。若G中存在長(zhǎng)度大于等于中存在長(zhǎng)度大于等于

5、2的一條回路，的一條回路，則回路上兩個(gè)結(jié)點(diǎn)之間存在不同的路。這與條件則回路上兩個(gè)結(jié)點(diǎn)之間存在不同的路。這與條件是矛盾的。所以是矛盾的。所以G中無(wú)回路。中無(wú)回路。 以下用歸納法證明以下用歸納法證明m=n1。 當(dāng)當(dāng)n=1時(shí)，時(shí)，G為平凡圖，為平凡圖，m=0=11=n1。結(jié)。結(jié)論成立。論成立。 設(shè)設(shè)nk時(shí)，結(jié)論成立。下證時(shí)，結(jié)論成立。下證n=k+1時(shí)，結(jié)論時(shí)，結(jié)論也成立。也成立。 設(shè)設(shè)nk時(shí)，結(jié)論成立。下證時(shí)，結(jié)論成立。下證n=k+1時(shí)，結(jié)論時(shí)，結(jié)論也成立。也成立。 設(shè)設(shè)e=(u,v)是是G中的一條邊，由于中的一條邊，由于G中無(wú)回中無(wú)回路，所以路，所以 G- e (在在G刪除邊刪除邊e所得的子圖所得

6、的子圖)有兩個(gè)連有兩個(gè)連通分支通分支G1和和G2，設(shè)它們的邊數(shù)和結(jié)點(diǎn)數(shù)分別，設(shè)它們的邊數(shù)和結(jié)點(diǎn)數(shù)分別為：為：m1，n1和和m2，n2。于是有。于是有n1k和和n2k，由，由歸納假設(shè)知：歸納假設(shè)知：m1=n11和和m2=n2-1，則：，則：m=m1m21=n1-1n2-11=n-1。 只須證明只須證明G是連通的。若不然，設(shè)是連通的。若不然，設(shè)G有有t(t2)個(gè)連通分支個(gè)連通分支G1，G2，Gt，Gi中均無(wú)中均無(wú)回路，都是樹(shù)。由回路，都是樹(shù)。由可知，可知，mi=ni1，i=1,t。于是。于是m=m1m2mt =n1-1n2-1nt-1=n1n2nt-t=nt，由于，由于t2，這，這與與m=n1矛盾

7、。所以矛盾。所以G是連通圖。是連通圖。 設(shè)設(shè)e是是G的任意邊，刪除的任意邊，刪除e得子圖得子圖G1，G1中的邊數(shù)中的邊數(shù)m1=m-1，G1中的結(jié)點(diǎn)數(shù)中的結(jié)點(diǎn)數(shù)n1=n，m1=m1=n-1-1=n-2=n1-2n1-1，所以，所以G1不是連不是連通圖（引理）。通圖（引理）。 先證先證G中無(wú)圈。若中無(wú)圈。若G中有圈，刪去圈上中有圈，刪去圈上任一邊仍連通，矛盾。任一邊仍連通，矛盾。 再證對(duì)任何再證對(duì)任何 ,G+e恰好有一個(gè)圈：因?yàn)榍『糜幸粋€(gè)圈：因?yàn)镚是連通且已證是連通且已證G無(wú)圈，故無(wú)圈，故G是樹(shù)。由是樹(shù)。由(2)知，任知，任意兩個(gè)結(jié)之間都有一條路相連，故意兩個(gè)結(jié)之間都有一條路相連，故G+e中必有中

8、必有一個(gè)含有一個(gè)含有 e的圈；另一方面，若的圈；另一方面，若G+e中有兩個(gè)中有兩個(gè)圈含有圈含有e，則，則(G+e)-e=G中仍然含有一個(gè)圈，矛中仍然含有一個(gè)圈，矛盾。盾。 只須證明只須證明G是連通的，是連通的， u,v V，uv，若若u,v相鄰，則相鄰，則u與與v連通。否則，連通。否則，G+（u,v）?。┣『煤幸粋€(gè)圈，故好含有一個(gè)圈，故u 與與v在在G中連通。由于中連通。由于u與與v是任意的，所以是任意的，所以G是連通圖。是連通圖。( )eE G定理：定理： 設(shè)設(shè)T是是n階非平凡的無(wú)向樹(shù)，則階非平凡的無(wú)向樹(shù)，則T中中 至少有兩片樹(shù)葉。至少有兩片樹(shù)葉。證證 : 因?yàn)橐驗(yàn)門(mén)是非平凡樹(shù)是非平凡樹(shù),

9、所以所以T中每個(gè)頂點(diǎn)的度中每個(gè)頂點(diǎn)的度數(shù)都大于等于數(shù)都大于等于1, 設(shè)設(shè)T有有k片樹(shù)葉片樹(shù)葉, 則有則有(n-k)個(gè)頂點(diǎn)度數(shù)大于等于個(gè)頂點(diǎn)度數(shù)大于等于2,由握手定理可知由握手定理可知 2m=d(vi) k+2(n-k)由由m=n-1,將此結(jié)果代入上式后解得將此結(jié)果代入上式后解得 k 2。例例：畫(huà)出：畫(huà)出5階所有非同構(gòu)的無(wú)向樹(shù)。階所有非同構(gòu)的無(wú)向樹(shù)。解解：設(shè)：設(shè)Ti為為5階無(wú)向樹(shù)階無(wú)向樹(shù),則則Ti的邊數(shù)為的邊數(shù)為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, 設(shè)設(shè)G有有t個(gè)個(gè)1頂點(diǎn)頂點(diǎn), 則有下列關(guān)系式則有下列關(guān)系式 22+13+4 3+t =2 m =2 x(n-1) =2 x(2+1+3+t-1) 解得：解得：t = 9 。例例：無(wú)向樹(shù)：無(wú)向樹(shù)G有有2個(gè)個(gè)2度結(jié)點(diǎn)，度結(jié)點(diǎn)，1個(gè)個(gè)3度結(jié)點(diǎn)，度結(jié)點(diǎn)，3個(gè)個(gè)4度結(jié)點(diǎn)，則其度結(jié)點(diǎn)，則其1度結(jié)點(diǎn)數(shù)為多少？度結(jié)點(diǎn)數(shù)為多少？ 解解：設(shè)：設(shè)G有有t個(gè)個(gè)4度分支點(diǎn)，則有下列關(guān)系式度分支點(diǎn)，則有下列關(guān)系式 8 1+2 3+ t 4 =2 (8+2+t-1) 解得：解得：t = 2

11、 則則G中共有中共有12個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，11條邊，度數(shù)序列之條邊，度數(shù)序列之 和為和為22， (Ti)=4, (Ti)=1, 度序列為：度序列為： 1,1,1,1,1,1,1,1,3,3,4, 4 其非同構(gòu)的圖形為：其非同構(gòu)的圖形為：例例 ：無(wú)向樹(shù)：無(wú)向樹(shù)G有有8片樹(shù)葉，片樹(shù)葉，2個(gè)個(gè)3度分支點(diǎn)，其度分支點(diǎn)，其余分支點(diǎn)均為余分支點(diǎn)均為4度，問(wèn)度，問(wèn)G有多少個(gè)有多少個(gè)4度分支點(diǎn)？度分支點(diǎn)？畫(huà)出其非同構(gòu)的情況。畫(huà)出其非同構(gòu)的情況。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。

12、。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。其非同構(gòu)的圖形為：其非同構(gòu)的圖形為： 解解： 有如下有如下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)例：例：畫(huà)出畫(huà)出6階所有非同構(gòu)的無(wú)向樹(shù)。階所有非同構(gòu)的無(wú)向樹(shù)。生成樹(shù)生成樹(shù) 設(shè)設(shè)G為無(wú)向圖，若為無(wú)向圖，若G的生成子圖是一棵的生成子圖是一棵樹(shù)，則該樹(shù)稱為樹(shù)，則該樹(shù)稱為G的的生成樹(shù)生成樹(shù)。設(shè)。設(shè)G的生成樹(shù)的生成樹(shù)為為T(mén)，則，則T中的邊稱為樹(shù)枝。在中的邊稱為樹(shù)枝。在G中但不在中但

13、不在生成樹(shù)生成樹(shù)T中的邊稱為中的邊稱為弦弦。T的所有弦的集合的所有弦的集合的導(dǎo)出子圖稱為的導(dǎo)出子圖稱為T(mén)的的余樹(shù)余樹(shù)。注意：注意：余樹(shù)不一定是樹(shù)。余樹(shù)不一定是樹(shù)。 一個(gè)無(wú)向連通圖，如果它本身不是樹(shù)，一個(gè)無(wú)向連通圖，如果它本身不是樹(shù)，它的生成樹(shù)是不唯一的。但所有的連通圖都它的生成樹(shù)是不唯一的。但所有的連通圖都具有生成樹(shù)。具有生成樹(shù)。 例例：在下圖中，：在下圖中，(2)為為(1)的一棵生成樹(shù)的一棵生成樹(shù)T， (3)為為T(mén)的余樹(shù)，但（的余樹(shù)，但（3）不是樹(shù)。）不是樹(shù)。abcdeabcdeabcd(1)(2)(3) 定理：定理：無(wú)向圖無(wú)向圖G G具有生成樹(shù)的充分必要條件是具有生成樹(shù)的充分必要條件是G

14、G為連通圖。為連通圖。 證明證明：若無(wú)向圖：若無(wú)向圖G G具有生成樹(shù)，顯然具有生成樹(shù)，顯然G G為連通圖。為連通圖。以下證明若無(wú)向圖以下證明若無(wú)向圖G G為連通圖，則為連通圖，則G G具有生成樹(shù)。具有生成樹(shù)。 若連通圖若連通圖G G無(wú)回路，則無(wú)回路，則G G本身就是一棵生成樹(shù)；若本身就是一棵生成樹(shù)；若G G至少有一個(gè)回路，刪除此回路的一邊，得到子圖至少有一個(gè)回路，刪除此回路的一邊，得到子圖G G1 1，它，它仍然連通，并與仍然連通，并與G G有相同結(jié)點(diǎn)集。若有相同結(jié)點(diǎn)集。若G G1 1無(wú)回路，則無(wú)回路，則G G1 1就就是一棵生成樹(shù)；若是一棵生成樹(shù)；若G G1 1仍有一個(gè)回路，再刪除仍有一個(gè)回

15、路，再刪除G G1 1回路上的回路上的一邊。重復(fù)上述過(guò)程，直至得到一個(gè)無(wú)回路的連通圖，一邊。重復(fù)上述過(guò)程，直至得到一個(gè)無(wú)回路的連通圖，該圖就是一棵生成樹(shù)。該圖就是一棵生成樹(shù)。 由該定理的證明過(guò)程可以看出，一個(gè)連通圖可以有由該定理的證明過(guò)程可以看出，一個(gè)連通圖可以有多個(gè)生成樹(shù)。因?yàn)樵谌《ㄒ粋€(gè)回路后，就可以從中去掉多個(gè)生成樹(shù)。因?yàn)樵谌《ㄒ粋€(gè)回路后，就可以從中去掉任一條邊，去掉的邊不同，可能得到的生成樹(shù)也不同。任一條邊，去掉的邊不同，可能得到的生成樹(shù)也不同。 推論推論1: 無(wú)向連通圖無(wú)向連通圖G有有n個(gè)結(jié)點(diǎn)和個(gè)結(jié)點(diǎn)和m條邊，則條邊，則mn1。 證明證明：由上述定理的證明知，：由上述定理的證明知，G有

16、生成樹(shù)，有生成樹(shù)，設(shè)為設(shè)為T(mén)。 |E(G)|=m，其中，其中，E(G)是圖是圖G的邊構(gòu)的邊構(gòu)成的集合。成的集合。|E(T)|=n1, 其中，其中，E(T)是樹(shù)是樹(shù)T的邊的邊構(gòu)成的集合。而構(gòu)成的集合。而|E(G)|E(T)|，所以，所以mn1。推論推論2： 在無(wú)向連通圖中，一個(gè)回路和任何一在無(wú)向連通圖中，一個(gè)回路和任何一棵生成樹(shù)的補(bǔ)至少有一條公共邊?？蒙蓸?shù)的補(bǔ)至少有一條公共邊。 證明：證明：若有一個(gè)回路和一棵生成樹(shù)的補(bǔ)若有一個(gè)回路和一棵生成樹(shù)的補(bǔ)無(wú)公共邊，那么，這個(gè)回路包含在該生成樹(shù)無(wú)公共邊，那么，這個(gè)回路包含在該生成樹(shù)中，這與樹(shù)的定義矛盾。中，這與樹(shù)的定義矛盾。 推論推論3 3： 在無(wú)向連通

17、圖中，一個(gè)邊割集和在無(wú)向連通圖中，一個(gè)邊割集和任何一棵生成樹(shù)至少有一條公共邊。任何一棵生成樹(shù)至少有一條公共邊。 證明：證明：若有一個(gè)邊割集和一棵生成樹(shù)若有一個(gè)邊割集和一棵生成樹(shù)無(wú)公共邊，那么，刪除這個(gè)邊割集所得的無(wú)公共邊，那么，刪除這個(gè)邊割集所得的子圖必包含該生成樹(shù)，從而該子圖是連通子圖必包含該生成樹(shù)，從而該子圖是連通的。這與邊割集的定義矛盾。的。這與邊割集的定義矛盾。 設(shè)設(shè)G為無(wú)向連通圖，有為無(wú)向連通圖，有n個(gè)結(jié)點(diǎn)和個(gè)結(jié)點(diǎn)和m條邊。條邊。T為為G的生成樹(shù)，的生成樹(shù)，T有有n個(gè)結(jié)點(diǎn)和個(gè)結(jié)點(diǎn)和n-1條邊。所以要得到條邊。所以要得到G的一棵生成樹(shù)，必須的一棵生成樹(shù)，必須刪除刪除G的的m-(n-1)

18、=mn1條邊。條邊。 最小生成樹(shù)最小生成樹(shù) 設(shè)無(wú)向連通帶權(quán)圖設(shè)無(wú)向連通帶權(quán)圖G=,TG=,T是是G G的一的一棵生成樹(shù)，棵生成樹(shù)，T T的各邊權(quán)之和稱為的各邊權(quán)之和稱為T(mén) T的的權(quán)權(quán)，記作，記作W(T)W(T)。G G的所有生成樹(shù)中權(quán)最小的生成樹(shù)稱為的所有生成樹(shù)中權(quán)最小的生成樹(shù)稱為G G的的最小生成樹(shù)最小生成樹(shù)。 求最小生成樹(shù)的算法很多，我們只介紹求最小生成樹(shù)的算法很多，我們只介紹避圈避圈法（法（克魯斯克爾克魯斯克爾Kruskal算法）。算法）。 設(shè)設(shè)n階無(wú)向連通帶權(quán)圖階無(wú)向連通帶權(quán)圖G=有有m條條邊邊,不妨設(shè)不妨設(shè)G中無(wú)環(huán)中無(wú)環(huán)(否則可先刪去否則可先刪去)，算法為：，算法為： 將將m條邊按權(quán)

19、從小到大順序排列，設(shè)為條邊按權(quán)從小到大順序排列，設(shè)為 e1,e2, ,em。(2) 取取e1在在T中，然后依次檢查中，然后依次檢查e2, ,em ，若，若ej (j=2,3, ,m)與與T中的邊不能構(gòu)成回路，則取中的邊不能構(gòu)成回路，則取ej在在T中，否則放棄中，否則放棄ej，考慮下一條邊，直至，考慮下一條邊，直至jm。(3) 算法停止時(shí)得到的算法停止時(shí)得到的T為為G的最小生成樹(shù)。的最小生成樹(shù)。Kruskal算法算法 一種求最小生成樹(shù)的算法一種求最小生成樹(shù)的算法例：例：下圖下圖 (a)給出了一個(gè)賦權(quán)圖給出了一個(gè)賦權(quán)圖G，用，用kruskal算法求出算法求出G的最小生成樹(shù)。的最小生成樹(shù)。 解：解：

20、先將先將m條邊按權(quán)由小到大排列：條邊按權(quán)由小到大排列： (v4,v5)，(v1,v8)，(v5,v7)，(v6,v7)，(v4,v6)，(v5,v6)， (v2,v7)，(v2,v5)，(v7,v8)，(v2,v3)，(v3,v4)，(v1,v2)。它們的權(quán)分別是：它們的權(quán)分別是：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) 構(gòu)成的生成樹(shù)在下圖構(gòu)成的生成樹(shù)在下圖 (b)，這是，這是G的最小生成樹(shù)。最的最小生成樹(shù)。最小生成樹(shù)小生成樹(shù)T的權(quán)的

21、權(quán)C(T)=3+4+5+6+7.5+10.5+11=47。 例例: :用避圈法求下圖所示的最小生成樹(shù)用避圈法求下圖所示的最小生成樹(shù)abcdef5555136642解解: W(T)=1+2+3+4+5 =15，圖中黃色為最，圖中黃色為最小生成樹(shù)。小生成樹(shù)。bacd762fe81443472356321hg例：例：鋪設(shè)一個(gè)連接各個(gè)城市的光纖通信網(wǎng)絡(luò)。鋪設(shè)一個(gè)連接各個(gè)城市的光纖通信網(wǎng)絡(luò)。圖中藍(lán)色為圖中藍(lán)色為最小生成樹(shù)最小生成樹(shù)。普里姆算法的基本思想：普里姆算法的基本思想： 假設(shè)假設(shè)N=(V,E)是連通圖，是連通圖，TE是是N上最小生成樹(shù)上最小生成樹(shù)中邊的集合。算法從中邊的集合。算法從U=u0(u0V

22、)，TE=開(kāi)始開(kāi)始，重復(fù)執(zhí)行下述操作：在所有，重復(fù)執(zhí)行下述操作：在所有uU, v V-U的的邊邊(u,v)E中找一條代價(jià)最小的邊中找一條代價(jià)最小的邊(u0,v0)并入集并入集合合TE，同時(shí)，同時(shí)v0并入并入U(xiǎn)，直至，直至U=V為止。此時(shí)為止。此時(shí)TE中中必有必有n-1條邊，則條邊，則T=(V,TE)為為N的最小生成樹(shù)的最小生成樹(shù)。 簡(jiǎn)單地說(shuō)簡(jiǎn)單地說(shuō)： 取圖中任意一個(gè)頂點(diǎn) u U作為生成樹(shù)的根，之后往生成樹(shù)上添加新的頂點(diǎn) v V-U。在添加的頂點(diǎn) v和已經(jīng)在生成樹(shù)上的頂點(diǎn)u 之間必定存在一條邊(u,v)，并且該邊的權(quán)值在所有連通頂點(diǎn)集U 和 V-U 之間的邊中取值最小。之后繼續(xù)往生成樹(shù)上添加頂點(diǎn)

23、，直至生成樹(shù)上U含有 n 個(gè)頂點(diǎ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算法分析：算法分析： 普里姆算法的時(shí)間復(fù)雜度為普里姆算法的時(shí)間復(fù)雜度為O O( (n n2 2) )。 該算法與網(wǎng)中的邊的數(shù)目無(wú)關(guān)。該算法與網(wǎng)中的邊的數(shù)目無(wú)關(guān)。 適用于求邊稠密的網(wǎng)的最小生成樹(shù)適用于求邊稠密的網(wǎng)的最小生成樹(shù)。返回 避圈法避圈

24、法是貪婪地增加不構(gòu)成回路的邊，以是貪婪地增加不構(gòu)成回路的邊，以求得最小生成樹(shù)。求得最小生成樹(shù)。 從另一個(gè)角度來(lái)考慮最小生成樹(shù)問(wèn)題，由從另一個(gè)角度來(lái)考慮最小生成樹(shù)問(wèn)題，由G的圈（回路）最優(yōu)條件，我們也可以在原連的圈（回路）最優(yōu)條件，我們也可以在原連通權(quán)圖通權(quán)圖G中逐步刪除構(gòu)成回路中中逐步刪除構(gòu)成回路中權(quán)最大的邊權(quán)最大的邊，最后剩下的無(wú)回路的生成子圖為最小成樹(shù)。我最后剩下的無(wú)回路的生成子圖為最小成樹(shù)。我們把這種方法稱為們把這種方法稱為“破圈法破圈法”。例例 ：在圖在圖(a)中給出了一個(gè)連通圖中給出了一個(gè)連通圖, 求此圖的求此圖的生成樹(shù)。生成樹(shù)。(a)根樹(shù)及其應(yīng)用根樹(shù)及其應(yīng)用 一個(gè)有向圖，略去方向后

25、是樹(shù)，則稱這個(gè)一個(gè)有向圖，略去方向后是樹(shù)，則稱這個(gè)有向圖為有向圖為有向樹(shù)有向樹(shù)。如果一棵有向樹(shù)恰有一個(gè)結(jié)。如果一棵有向樹(shù)恰有一個(gè)結(jié)點(diǎn)入度為點(diǎn)入度為0，其余所有結(jié)點(diǎn)入度為，其余所有結(jié)點(diǎn)入度為1，此有向樹(shù)，此有向樹(shù)稱為稱為根樹(shù)根樹(shù)。在根樹(shù)中，入度為。在根樹(shù)中，入度為0的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為樹(shù)根樹(shù)根，出度為出度為0的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為樹(shù)葉樹(shù)葉，出度不為，出度不為0的結(jié)點(diǎn)稱的結(jié)點(diǎn)稱為為分枝點(diǎn)分枝點(diǎn)或或內(nèi)點(diǎn)內(nèi)點(diǎn)。從此定義可以看出，在根樹(shù)。從此定義可以看出，在根樹(shù)中，除了樹(shù)葉都是分枝點(diǎn)或內(nèi)點(diǎn)外，樹(shù)根也是中，除了樹(shù)葉都是分枝點(diǎn)或內(nèi)點(diǎn)外，樹(shù)根也是分枝點(diǎn)。分枝點(diǎn)。 (1)(2)v0v1v2v3v4v5v6v7v0

26、v1v2v3v4v5v6v7例例: 下圖下圖(1)為一棵根樹(shù)。為一棵根樹(shù)。V0為樹(shù)根為樹(shù)根, v1,v4, v3, v6, v7為樹(shù)為樹(shù)葉葉, v2, v5為內(nèi)點(diǎn)為內(nèi)點(diǎn), v0, v2, v5為均為分支點(diǎn)為均為分支點(diǎn), 由于在根樹(shù)中由于在根樹(shù)中有向邊的方向均一致有向邊的方向均一致, 故可省掉其方向故可省掉其方向, 如圖如圖(2)。v0v1v2v3v4v5v6v7從樹(shù)根到從樹(shù)根到T的任意頂點(diǎn)的任意頂點(diǎn)v的通路（路徑）長(zhǎng)度稱為的通路（路徑）長(zhǎng)度稱為v的的層數(shù)層數(shù)，層數(shù)最大頂點(diǎn)的層數(shù)稱為，層數(shù)最大頂點(diǎn)的層數(shù)稱為樹(shù)高樹(shù)高，平凡樹(shù)也稱為，平凡樹(shù)也稱為根樹(shù)。根樹(shù)。例：例： 下下圖中圖中, v1,v2, v

27、3,在第一層上，在第一層上，v4, v5 在第二層上，在第二層上，v6, v7在第三層上。樹(shù)高為在第三層上。樹(shù)高為3。家族樹(shù)家族樹(shù) 設(shè)設(shè)T為非平凡的根樹(shù)，為非平凡的根樹(shù)，u，v為其兩個(gè)為其兩個(gè)頂點(diǎn)，頂點(diǎn)， a)若若u可達(dá)可達(dá)v，則稱，則稱u是是v的祖的祖先，先，v是是u的后代；的后代； b)若若u鄰接到鄰接到v，則稱，則稱u是是v的父親，的父親，v是是u的兒子；的兒子；c)若若u，v有相同的父親，則稱有相同的父親，則稱u，v是兄弟；是兄弟；d)d)稱稱v v及其后代的導(dǎo)出子圖為及其后代的導(dǎo)出子圖為T(mén) T以以v v為根的根子樹(shù)。為根的根子樹(shù)。uv1v2v3n在根樹(shù)中，若每個(gè)結(jié)點(diǎn)的出度小于或等于在

28、根樹(shù)中，若每個(gè)結(jié)點(diǎn)的出度小于或等于m，則稱該樹(shù)為，則稱該樹(shù)為m叉樹(shù)叉樹(shù)。n在在m叉樹(shù)中，若每個(gè)結(jié)點(diǎn)的出度恰等于叉樹(shù)中，若每個(gè)結(jié)點(diǎn)的出度恰等于0或或m，則稱該樹(shù)為，則稱該樹(shù)為完全完全m叉樹(shù)叉樹(shù)。n在完全在完全m叉樹(shù)中，若所有樹(shù)葉層數(shù)相同，叉樹(shù)中，若所有樹(shù)葉層數(shù)相同，則稱該樹(shù)為則稱該樹(shù)為正則正則m叉樹(shù)叉樹(shù)。 當(dāng)當(dāng)m=2時(shí)，時(shí)，m叉樹(shù)就是二叉樹(shù)，完全叉樹(shù)就是二叉樹(shù)，完全m叉叉樹(shù)就是樹(shù)就是完全二叉樹(shù)完全二叉樹(shù)。（a）是）是2叉樹(shù)，（叉樹(shù)，（b）是正則）是正則2叉樹(shù)叉樹(shù)（c）是完全）是完全2叉樹(shù)。叉樹(shù)。定理定理：在完全：在完全m叉樹(shù)中，其樹(shù)葉數(shù)為叉樹(shù)中，其樹(shù)葉數(shù)為t，分，分枝點(diǎn)數(shù)為枝點(diǎn)數(shù)為i，則，則 (

29、m-1)i=t-1。 證明證明：由定理的條件知，該樹(shù)有：由定理的條件知，該樹(shù)有it個(gè)個(gè)結(jié)點(diǎn)，該樹(shù)邊數(shù)為結(jié)點(diǎn)，該樹(shù)邊數(shù)為it-1。 另一方面，由完另一方面，由完全全m叉樹(shù)定義知，該樹(shù)出度的和為：叉樹(shù)定義知，該樹(shù)出度的和為：mi，這，這也是該樹(shù)的邊數(shù)，于是有也是該樹(shù)的邊數(shù)，于是有mi=it-1。 整理整理后有后有(m-1)i=t-1。 最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)： 設(shè)設(shè)T是一棵二叉樹(shù)，有是一棵二叉樹(shù)，有t片樹(shù)葉片樹(shù)葉v1，v2， ，vt，分，分別帶權(quán)別帶權(quán)W!，W2， ，Wt，則稱，則稱T為賦權(quán)二叉樹(shù)或帶權(quán)為賦權(quán)二叉樹(shù)或帶權(quán)二叉樹(shù)。在賦權(quán)二叉樹(shù)二叉樹(shù)。在賦權(quán)二叉樹(shù)T中，中， 稱為樹(shù)稱為樹(shù)T的權(quán)。記的權(quán)。

30、記為為W(T)。在所有有。在所有有t片樹(shù)葉的二叉樹(shù)中，如果片樹(shù)葉的二叉樹(shù)中，如果t片樹(shù)葉分片樹(shù)葉分別帶權(quán)別帶權(quán)W!，W2， ，Wt，權(quán)，權(quán)W(T)最小的二叉樹(shù)，稱最小的二叉樹(shù)，稱為最優(yōu)二叉樹(shù)。為最優(yōu)二叉樹(shù)。 )(1itiivlW 在下圖所示的三棵樹(shù)中在下圖所示的三棵樹(shù)中,都是帶權(quán)都是帶權(quán)1,3,4,5,6的二元的二元樹(shù)樹(shù),W(T1)=47, W(T2)=54, W(T3)=42,但它們中有無(wú)但它們中有無(wú)最最優(yōu)二叉樹(shù)。優(yōu)二叉樹(shù)。是否有最優(yōu)二叉樹(shù)？最優(yōu)權(quán)重是多少？是否有最優(yōu)二叉樹(shù)？最優(yōu)權(quán)重是多少？T T1 1T T2 2T T3 34 4 5 51 16 63 33 34 45 56 61 11

31、13 36 64 45 5Huffman算法算法 一種求最優(yōu)二叉樹(shù)的算法一種求最優(yōu)二叉樹(shù)的算法 設(shè)設(shè)T T是有是有t t片葉子的二叉樹(shù)片葉子的二叉樹(shù), ,其中其中t t片葉子分別片葉子分別帶有權(quán)帶有權(quán) 1 1, , 2 2, , , t t, ,稱稱T T為加權(quán)二叉樹(shù)為加權(quán)二叉樹(shù), ,稱為二叉樹(shù)稱為二叉樹(shù)T T的權(quán)的權(quán), ,其中其中l(wèi) li i為帶權(quán)為帶權(quán) i i的樹(shù)葉的樹(shù)葉v vi i的層數(shù)。的層數(shù)。 在所有帶權(quán)在所有帶權(quán) 1 1, , 2 2, , , t t的二叉樹(shù)中的二叉樹(shù)中, ,帶權(quán)最帶權(quán)最小的二叉樹(shù)稱為最優(yōu)二叉樹(shù)。小的二叉樹(shù)稱為最優(yōu)二叉樹(shù)。 19521952年年, ,哈夫曼給出了求

32、最優(yōu)二叉樹(shù)的算法哈夫曼給出了求最優(yōu)二叉樹(shù)的算法, ,該該算法的算法的 核心思想為核心思想為: :從帶權(quán)從帶權(quán) 1 1+ + 2 2, , 3 3, , , t t的最的最優(yōu)二叉樹(shù)可得到優(yōu)二叉樹(shù)可得到帶權(quán)帶權(quán) 1 1, , 2 2, , , t t的最優(yōu)二叉樹(shù)的最優(yōu)二叉樹(shù). . 基本步驟如下基本步驟如下: :( )ti iiW Tl哈夫曼算法的步驟哈夫曼算法的步驟 給定實(shí)數(shù)給定實(shí)數(shù) 1, 2, t且且 12 t(1)連接連接 1, 2 為權(quán)的兩片葉子為權(quán)的兩片葉子,得一分枝點(diǎn)得一分枝點(diǎn),其權(quán)為其權(quán)為 1+ 2。(2)在在 1+ 2, 3, t中選出兩個(gè)最小的權(quán)中選出兩個(gè)最小的權(quán),連接它們對(duì)應(yīng)的頂

33、點(diǎn)連接它們對(duì)應(yīng)的頂點(diǎn)(不一定都是樹(shù)葉不一定都是樹(shù)葉)得分得分枝點(diǎn)及所帶的權(quán)。枝點(diǎn)及所帶的權(quán)。(3)重復(fù)重復(fù)(2),直到形成直到形成t-1個(gè)分枝點(diǎn)個(gè)分枝點(diǎn), t片葉子為止。片葉子為止。例例: :求帶權(quán)求帶權(quán)1,3,4,5,61,3,4,5,6的最優(yōu)二元樹(shù)。的最優(yōu)二元樹(shù)。4 44 48 81 13 33 38 84 43 31 11 13 34 45 56 64 44 411115 56 61 14 48 811111919 連接權(quán)為連接權(quán)為w1,w2的兩片樹(shù)葉的兩片樹(shù)葉, 得一個(gè)分支點(diǎn)其權(quán)為得一個(gè)分支點(diǎn)其權(quán)為w1+w2 在在w1+w2 ,w3, ,wt中中選出兩個(gè)最小的權(quán)選出兩個(gè)最小的權(quán), 連接

34、連接它們對(duì)應(yīng)的頂點(diǎn)它們對(duì)應(yīng)的頂點(diǎn)(不一定不一定是樹(shù)葉是樹(shù)葉), 得得 分支點(diǎn)及所分支點(diǎn)及所帶的權(quán)。帶的權(quán)。 重復(fù)重復(fù) , 直到形成直到形成t-1個(gè)分支點(diǎn)個(gè)分支點(diǎn), t片樹(shù)葉為止片樹(shù)葉為止(若得到的權(quán)比后續(xù)的兩若得到的權(quán)比后續(xù)的兩個(gè)權(quán)大個(gè)權(quán)大,則另開(kāi)分支則另開(kāi)分支)最優(yōu)二叉樹(shù)在通信編碼中的應(yīng)用最優(yōu)二叉樹(shù)在通信編碼中的應(yīng)用 設(shè)設(shè) = 1 2 n-1 n為長(zhǎng)為為長(zhǎng)為n的符號(hào)串的符號(hào)串, 稱其子串稱其子串 1 , 1 2 , , 1 2 n-1 分別為該符號(hào)串的長(zhǎng)分別為該符號(hào)串的長(zhǎng)度為度為1,2, n-1的的前綴。前綴。 設(shè)設(shè)B=1 ,2 , ,m 為一個(gè)符號(hào)串集合為一個(gè)符號(hào)串集合, 若對(duì)于任意的若對(duì)

35、于任意的i , j B, i j, i , j , 互不為前互不為前綴綴, 則稱則稱B為為前綴碼。前綴碼。 若符號(hào)串中若符號(hào)串中i(i=1,2, , m)只出現(xiàn)只出現(xiàn)0, 1兩兩個(gè)符號(hào)個(gè)符號(hào), 則稱則稱B為為二元前綴碼二元前綴碼。又如又如： 1,00,011,0101,01001,01000 是前綴是前綴碼。而碼。而 1,00,0101,0100,01001,01000 不不是前綴碼，因?yàn)槭乔熬Y碼，因?yàn)?100是是01001的前綴，也的前綴，也是是01000的前綴。的前綴。例例： 0, 10, 110, 1111 1, 01, 001, 0001 等是前綴碼等是前綴碼而而 1,11,101,0

36、01,0011 不是前綴碼不是前綴碼若使用前綴碼中的若使用前綴碼中的0、1序列表示英文字母，當(dāng)接收者序列表示英文字母，當(dāng)接收者收到收到0、1組成的長(zhǎng)串時(shí)，就可以惟一的、準(zhǔn)確無(wú)誤地組成的長(zhǎng)串時(shí)，就可以惟一的、準(zhǔn)確無(wú)誤地分割成字母對(duì)應(yīng)的分割成字母對(duì)應(yīng)的0、1序列。序列。定理：定理：任意一個(gè)二叉樹(shù)，可以產(chǎn)生惟一的前任意一個(gè)二叉樹(shù)，可以產(chǎn)生惟一的前綴碼。綴碼。 證明：證明：在二叉樹(shù)中，每一個(gè)分枝點(diǎn)引出在二叉樹(shù)中，每一個(gè)分枝點(diǎn)引出的左側(cè)邊標(biāo)記的左側(cè)邊標(biāo)記0，右側(cè)邊標(biāo)記，右側(cè)邊標(biāo)記1。由根結(jié)點(diǎn)到。由根結(jié)點(diǎn)到樹(shù)葉的路經(jīng)上各邊的標(biāo)記組成的樹(shù)葉的路經(jīng)上各邊的標(biāo)記組成的0、1序列作序列作為該片樹(shù)葉的標(biāo)記。顯然，沒(méi)

37、有一片樹(shù)葉的為該片樹(shù)葉的標(biāo)記。顯然，沒(méi)有一片樹(shù)葉的標(biāo)記是另一片樹(shù)葉的標(biāo)記的前綴。所有樹(shù)葉標(biāo)記是另一片樹(shù)葉的標(biāo)記的前綴。所有樹(shù)葉的標(biāo)記構(gòu)成了一個(gè)前綴碼。的標(biāo)記構(gòu)成了一個(gè)前綴碼。由上面做法知，由上面做法知， vi處的符號(hào)串的前綴均在處的符號(hào)串的前綴均在vi所所在的通路上除在的通路上除vi外的頂點(diǎn)處達(dá)到，因而所得外的頂點(diǎn)處達(dá)到，因而所得符號(hào)串集合為二元前綴碼。符號(hào)串集合為二元前綴碼。 010110101000100010101111例：例：右圖所示的二元樹(shù)右圖所示的二元樹(shù)產(chǎn)生的前綴嗎為產(chǎn)生的前綴嗎為11,00,011,0100,0101利用利用Huffman算法求出的最優(yōu)算法求出的最優(yōu)2叉樹(shù)產(chǎn)生的叉

38、樹(shù)產(chǎn)生的前綴碼稱為前綴碼稱為最佳前綴碼最佳前綴碼。例例: 在通信中在通信中, 0,1,2,3,4,5,6,7出現(xiàn)的頻率如下出現(xiàn)的頻率如下 0：30, 1：20, 2： 15 3：10, 4：10, 5： 5 6： 5, 7：5 求傳輸它們的求傳輸它們的最佳前綴碼最佳前綴碼100604030302020151510555010101010101101001000000000100010011001011101解解:將各字符出現(xiàn)的頻率作為其相應(yīng)將各字符出現(xiàn)的頻率作為其相應(yīng)的權(quán)的權(quán) 1=5, 2=5, 3=5, 4=10, 5=10, 6=15, 7=20, 8=30為為8個(gè)權(quán)個(gè)權(quán),利用利用Huff

39、man算法求出的算法求出的最優(yōu)最優(yōu)2叉樹(shù)如圖所示叉樹(shù)如圖所示(碼長(zhǎng)取碼長(zhǎng)取3,如如101傳傳5)圖中方框中的圖中方框中的8個(gè)碼子是個(gè)碼子是最佳前綴碼最佳前綴碼。樹(shù)。樹(shù)T是帶權(quán)是帶權(quán) 1, 2, 8的最優(yōu)二叉樹(shù)。帶權(quán)為的最優(yōu)二叉樹(shù)。帶權(quán)為 i的樹(shù)葉的樹(shù)葉vi對(duì)應(yīng)的碼子傳輸出現(xiàn)頻率為對(duì)應(yīng)的碼子傳輸出現(xiàn)頻率為 i, 的數(shù)字，即的數(shù)字，即11傳傳1, 101傳傳401傳傳0, 0001傳傳5 001傳傳2, 101傳傳4 11傳傳1, 00001傳傳6 100傳傳3, 00000傳傳7。決策樹(shù)決策樹(shù) 若樹(shù)的每個(gè)內(nèi)點(diǎn)都對(duì)應(yīng)著一次決策若樹(shù)的每個(gè)內(nèi)點(diǎn)都對(duì)應(yīng)著一次決策, ,這些頂這些頂點(diǎn)的子樹(shù)都對(duì)應(yīng)著該決策的

40、每種可能結(jié)果點(diǎn)的子樹(shù)都對(duì)應(yīng)著該決策的每種可能結(jié)果, ,這樣的這樣的有序樹(shù)稱為有序樹(shù)稱為決策樹(shù)決策樹(shù)。例例：有：有8 8枚外觀相同的硬幣枚外觀相同的硬幣, ,其中有其中有7 7枚重量相同枚重量相同, ,而而剩余的一枚偽幣較輕剩余的一枚偽幣較輕, ,要求以比較重量的方法用一要求以比較重量的方法用一架天平去找出偽幣。架天平去找出偽幣。解解: :用用1-81-8標(biāo)記硬幣標(biāo)記硬幣, ,每次衡量有每次衡量有3 3種可能種可能: :左旁低下左旁低下, ,保持水平保持水平, ,右旁低下右旁低下, ,下圖給出這一解決過(guò)程的決策下圖給出這一解決過(guò)程的決策圖。圖中圖。圖中表示不會(huì)出現(xiàn)的結(jié)果。表示不會(huì)出現(xiàn)的結(jié)果。決策

41、樹(shù)的結(jié)點(diǎn)左側(cè)標(biāo)記著狀態(tài)決策樹(shù)的結(jié)點(diǎn)左側(cè)標(biāo)記著狀態(tài), ,這里表示包含有偽幣這里表示包含有偽幣的硬幣集合的硬幣集合, ,右側(cè)標(biāo)記測(cè)試內(nèi)容右側(cè)標(biāo)記測(cè)試內(nèi)容。1,2,3,81,2,3對(duì)6,7,8右旁低下左旁低下1,2,31對(duì)332154876說(shuō)明說(shuō)明: :( (1)1)決策樹(shù)的每一內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)部分解決策樹(shù)的每一內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)部分解; ;每個(gè)葉子對(duì)應(yīng)于一個(gè)解。每一內(nèi)部結(jié)點(diǎn)聯(lián)結(jié)于一個(gè)每個(gè)葉子對(duì)應(yīng)于一個(gè)解。每一內(nèi)部結(jié)點(diǎn)聯(lián)結(jié)于一個(gè)獲得新信息的測(cè)試。從每一結(jié)點(diǎn)出發(fā)的每一枝標(biāo)記獲得新信息的測(cè)試。從每一結(jié)點(diǎn)出發(fā)的每一枝標(biāo)記著不同的測(cè)試結(jié)果。一個(gè)解決過(guò)程的執(zhí)行對(duì)應(yīng)于通著不同的測(cè)試結(jié)果。一個(gè)解決過(guò)程的執(zhí)行對(duì)應(yīng)

42、于通過(guò)從根到葉的一條路。一個(gè)決策樹(shù)是所有可能的解過(guò)從根到葉的一條路。一個(gè)決策樹(shù)是所有可能的解決路的集合。決路的集合。(2)(2)可以用決策樹(shù)估計(jì)排序的最壞情況時(shí)間。排序問(wèn)題可可以用決策樹(shù)估計(jì)排序的最壞情況時(shí)間。排序問(wèn)題可描述為描述為: :將將n n個(gè)元素個(gè)元素x x1 1,x,x2 2, ,x,xn n按升序或降序排列。這按升序或降序排列。這里將研究的排序算法基于二叉比較里將研究的排序算法基于二叉比較, ,即一次比較兩個(gè)元即一次比較兩個(gè)元素，每次這樣的比較都縮小了可能的排序集合。因此素，每次這樣的比較都縮小了可能的排序集合。因此, ,基于二叉比較的排序算法可以表示成二叉樹(shù)基于二叉比較的排序算法

43、可以表示成二叉樹(shù), ,其中每個(gè)其中每個(gè)內(nèi)點(diǎn)表示兩個(gè)元素的一次比較內(nèi)點(diǎn)表示兩個(gè)元素的一次比較, ,每個(gè)樹(shù)葉表示每個(gè)樹(shù)葉表示n n個(gè)元素個(gè)元素的的n!n!種排列種的一種。種排列種的一種。二叉樹(shù)的遍歷二叉樹(shù)的遍歷二叉樹(shù)的遍歷二叉樹(shù)的遍歷 訪問(wèn)一棵根樹(shù)的每個(gè)頂點(diǎn)一次且僅一次稱為樹(shù)的遍歷。遍歷一棵二叉樹(shù)的方法常有如下三種：（1）中序遍歷法中序遍歷法：訪問(wèn)順序?yàn)椤白笞訕?shù)、樹(shù)根、右子樹(shù)”；（2）前序遍歷法前序遍歷法：訪問(wèn)順序?yàn)椤皹?shù)根、左子樹(shù)、右子樹(shù)”；（3）后序遍歷法后序遍歷法：訪問(wèn)順序?yàn)椤白笞訕?shù)、右子樹(shù)、樹(shù)根”。 例：例：試用三種周游方式行遍下圖。試用三種周游方式行遍下圖。中序行遍法訪問(wèn)此樹(shù)中序行遍法訪問(wèn)

44、此樹(shù)：(a(b+c)+def ) (g+(h-i)j)前序行遍法訪問(wèn)此樹(shù)：前序行遍法訪問(wèn)此樹(shù)：(+(+(a (+b c )a (+b c )d (d (e f ) +g (e f ) +g (- h i j )(- h i j )后序行遍法訪問(wèn)此樹(shù)：后序行遍法訪問(wèn)此樹(shù)：a b c + de f+ g h i - j + 圖圖G G的一個(gè)頂點(diǎn)的一個(gè)頂點(diǎn)v v的的離徑離徑R(v)R(v)定義為定義為: : 所有滿足所有滿足R(v)=R(G)R(v)=R(G)的頂點(diǎn)的頂點(diǎn)v v都稱為都稱為G G的中心的中心. .顯然一個(gè)圖的直徑為顯然一個(gè)圖的直徑為: : ),(max)()(uvdvRGVu()(

45、)min ( )v V GR GR v()max ( )v V GR v圖圖G的半徑的半徑R(G)定義為：定義為：例例.求下圖求下圖G的每個(gè)結(jié)點(diǎn)的離徑及圖的每個(gè)結(jié)點(diǎn)的離徑及圖G的直徑的直徑,半徑和中心半徑和中心.u1u3u6u2u5u4定理定理 設(shè)設(shè)P=u1u2ulul+1是樹(shù)是樹(shù)T的一條最長(zhǎng)路的一條最長(zhǎng)路,則則(1)T的直徑為的直徑為l;(2)若若l為奇數(shù)為奇數(shù),設(shè)設(shè)l=2k-1,則則T的半徑為的半徑為k,T有兩個(gè)有兩個(gè)相鄰的中心相鄰的中心,即為即為ukuk+1.并且每一條長(zhǎng)為并且每一條長(zhǎng)為l的路的路都通過(guò)這兩個(gè)中心都通過(guò)這兩個(gè)中心.(2)若若l為偶數(shù)為偶數(shù),設(shè)設(shè)l=2k,則則T的半徑為的半

46、徑為k,T中只有一中只有一個(gè)中心個(gè)中心,即為即為uk+1.并且每一條長(zhǎng)為并且每一條長(zhǎng)為l的路都通過(guò)的路都通過(guò)該中心該中心.定理的證明證:(1)由于P=u1u2ulul+1是是T中的一條最長(zhǎng)路中的一條最長(zhǎng)路,故故d(u1,ul+1)=l即為即為T(mén)的直徑的直徑.(2)設(shè)設(shè)u是是T中的任意一個(gè)結(jié)點(diǎn)中的任意一個(gè)結(jié)點(diǎn),則則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. 對(duì)于對(duì)于T中任意一個(gè)結(jié)點(diǎn)中任意一個(gè)結(jié)點(diǎn)u,若若u在在P上上,顯然有顯然有d(u,uk) k.若若u不在不在P上上

47、,由由T的連通性的連通性,P中必存在一中必存在一個(gè)頂點(diǎn)個(gè)頂點(diǎn)ui(2 i 2k-1=l),T中有一條連接中有一條連接u與與ui的路的路Q,使使u1,.,ui-1,ui+1,u2k都不在都不在Q上上. 因?yàn)橐驗(yàn)镻是是T中的最長(zhǎng)路中的最長(zhǎng)路,故有故有:d(u,ui) i-1; d(u,ui) l+1-i 若若i k,因?yàn)橐驗(yàn)閐(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)所以對(duì)所以對(duì)T中的任意結(jié)點(diǎn)中的任意結(jié)點(diǎn)u有有d(u,uk) k,

48、故故R(uk) k,從從而而R(T) k.綜合上述論證易得綜合上述論證易得R(T) =k,且且R(uk)=k,即即uk為為T(mén)的一個(gè)中心的一個(gè)中心.同理可證同理可證uk+1為為T(mén)的一個(gè)中心的一個(gè)中心. 下證長(zhǎng)為下證長(zhǎng)為l的任意一條路的任意一條路P一定過(guò)中心一定過(guò)中心uk與與uk+1.設(shè)設(shè)P的兩個(gè)端點(diǎn)分別是的兩個(gè)端點(diǎn)分別是u和和u,則則u和和u均不在均不在P上上.對(duì)對(duì)P上的任意兩個(gè)內(nèi)部點(diǎn)上的任意兩個(gè)內(nèi)部點(diǎn)ui和和uj,由由T的連通性的連通性,T中一定中一定存在存在u-ui路路Q1和和u-uj路路Q2,使得使得(V(Q1)-ui) V(P)=; (V(Q2)-uj) V(P)=.不妨設(shè)不妨設(shè)i j.

49、因?yàn)橐驗(yàn)門(mén)是樹(shù)是樹(shù),故故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為長(zhǎng)是為長(zhǎng)是l的的u-u路矛路矛盾盾.因此因此i kj,所以結(jié)論正確所以結(jié)論正確. 同理可證同理可證(3).最短路問(wèn)題 一、問(wèn)題的提出一、問(wèn)題的提出 )(G賦權(quán)圖（網(wǎng)絡(luò)）：賦權(quán)圖（網(wǎng)絡(luò)）： G=(V, E) 中，給每條邊中，給每條邊 a= 賦予一個(gè)非負(fù)實(shí)數(shù)權(quán)賦予一個(gè)非負(fù)實(shí)數(shù)權(quán) wij ，得到一個(gè)有向網(wǎng)，得到一個(gè)有向網(wǎng)絡(luò)絡(luò)

50、路徑非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和距離矩陣距離矩陣 對(duì)上述網(wǎng)絡(luò)，定義對(duì)上述網(wǎng)絡(luò)，定義 D=(dij)n n，n=|V| wij 當(dāng)當(dāng) E dij = 其它其它帶權(quán)路徑長(zhǎng)度帶權(quán)路徑長(zhǎng)度 對(duì)上述網(wǎng)絡(luò)，路徑對(duì)上述網(wǎng)絡(luò)，路徑 v1, v2 , ,vk 的帶權(quán)路徑長(zhǎng)度定義為的帶權(quán)路徑長(zhǎng)度定義為1,11ki iidw最短路問(wèn)題在實(shí)際工作中應(yīng)用最短路問(wèn)題在實(shí)際工作中應(yīng)用1、通訊網(wǎng)絡(luò)中最可靠問(wèn)題、通訊網(wǎng)絡(luò)中最可靠問(wèn)題2、最大容量問(wèn)題、最大容量問(wèn)題3、統(tǒng)籌方法中求關(guān)鍵路線、統(tǒng)籌方法中求關(guān)

51、鍵路線4、背包問(wèn)題、背包問(wèn)題5、選址問(wèn)題、選址問(wèn)題6、工件加工順序問(wèn)題、工件加工順序問(wèn)題7、中國(guó)郵遞員問(wèn)題、中國(guó)郵遞員問(wèn)題背包問(wèn)題背包問(wèn)題(Knapsack problem)是一種組合優(yōu)化的NP完全問(wèn)題。問(wèn)題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。問(wèn)題的名稱來(lái)源于如何選擇最合適的物品放置于給定背包中。 例一位旅客要從一位旅客要從A城到城到B城城他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選擇一條途中所花時(shí)間最短的路線；他希望選擇一條途中所花時(shí)間最短的路線；他希望選擇一條途中費(fèi)用最小的

52、路線；他希望選擇一條途中費(fèi)用最小的路線；v5v4v3v2v1v0 100 6030101020 5 50這些問(wèn)題均是帶權(quán)圖上的最短路徑問(wèn)題。這些問(wèn)題均是帶權(quán)圖上的最短路徑問(wèn)題。邊上的權(quán)表示一站邊上的權(quán)表示一站邊上的權(quán)代表距離邊上的權(quán)代表距離邊的權(quán)代表費(fèi)用邊的權(quán)代表費(fèi)用 Dijkstra算法 Floyd算法 Floyd-Warshall算法 Dijkstra算法算法 Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉狄克斯特拉（Dijkstra）于）于1959 年提出的，因此又叫狄克斯特拉算法。年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決

53、的是有向是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問(wèn)題。圖中最短路徑問(wèn)題。 荷蘭計(jì)算機(jī)科學(xué)教授荷蘭計(jì)算機(jī)科學(xué)教授Edsger W.Dijkstra(1930-) 在在1972年獲年獲得美國(guó)計(jì)算機(jī)協(xié)會(huì)授予的圖靈獎(jiǎng)，這是計(jì)算機(jī)科學(xué)中最具聲得美國(guó)計(jì)算機(jī)協(xié)會(huì)授予的圖靈獎(jiǎng)，這是計(jì)算機(jī)科學(xué)中最具聲望的獎(jiǎng)項(xiàng)之一。望的獎(jiǎng)項(xiàng)之一。 Dijkstra算法是求出一個(gè)連通加權(quán)簡(jiǎn)單圖中從結(jié)點(diǎn)算法是求出一個(gè)連通加權(quán)簡(jiǎn)單圖中從結(jié)點(diǎn)a到結(jié)到結(jié)點(diǎn)點(diǎn)z的最短路。邊的最短路。邊(i,j)的權(quán)的權(quán)(i,j)0，且結(jié)點(diǎn)，且結(jié)點(diǎn)x的標(biāo)號(hào)為的標(biāo)號(hào)為L(zhǎng)(x)。結(jié)束時(shí)，結(jié)束時(shí)，L(z)是從是從a到到z的最短長(zhǎng)度。的最短長(zhǎng)

54、度。 舉例來(lái)說(shuō)，如果圖中的頂點(diǎn)表示城市，而邊上的舉例來(lái)說(shuō)，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重權(quán)重表表示城市間開(kāi)車行經(jīng)的距離。示城市間開(kāi)車行經(jīng)的距離。 Dijkstra算法可以用來(lái)找到兩個(gè)算法可以用來(lái)找到兩個(gè)城市之間的最短路徑。城市之間的最短路徑。 Dijkstra算法基本思想:把圖中所有結(jié)點(diǎn)分為兩組，每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)距離值。 第一組：包括已確定最短路徑的結(jié)點(diǎn)，結(jié)點(diǎn)對(duì)應(yīng)的距離值是由v0到此結(jié)點(diǎn)的最短路徑長(zhǎng)度； 第二組：包括尚未確定最短路徑的結(jié)點(diǎn)，結(jié)點(diǎn)對(duì)應(yīng)的距離值是v0經(jīng)由第一組結(jié)點(diǎn)（中間結(jié)點(diǎn)）至此結(jié)點(diǎn)的最短路徑長(zhǎng)度。 按最短路徑長(zhǎng)度遞增的順序把第二組的結(jié)點(diǎn)加到第一組中去，直至v0可達(dá)的所有結(jié)

55、點(diǎn)都包含于第一組。在這個(gè)過(guò)程中，總保持從v0到第一組各結(jié)點(diǎn)的最短路徑長(zhǎng)度都不大于從v0至第二組任何結(jié)點(diǎn)的路徑長(zhǎng)度。設(shè)源點(diǎn)為v0v初始時(shí)v0進(jìn)入第一組，v0的距離值為0；第二組包含其它所有結(jié)點(diǎn)，這些結(jié)點(diǎn)對(duì)應(yīng)的距離值這樣確定（設(shè)vi為第二組中的結(jié)點(diǎn)） v然后每次從第二組的結(jié)點(diǎn)中選一個(gè)其距離值為最小的結(jié)點(diǎn)vm加到第一組中。每往第一組加入一個(gè)結(jié)點(diǎn)vm，就要對(duì)第二組的各結(jié)點(diǎn)的距離值作一次修正（設(shè)vi為第二組的結(jié)點(diǎn)）：v若加進(jìn)vm做中間結(jié)點(diǎn)使得v0至vi的路徑長(zhǎng)度更短（即vi的距離值vm的距離值+Wmi），則要修改vi的距離（vi的距離值vm的距離值+Wmi）。修改后再選距離值最小的一個(gè)結(jié)點(diǎn)加入到第一組中

56、，。 如此進(jìn)行下去，直至第一組囊括圖的所有結(jié)點(diǎn)或再無(wú)可加入第一組的結(jié)點(diǎn)存在。顯然，這種從第二組的結(jié)點(diǎn)中選距離值最小的結(jié)點(diǎn)擴(kuò)展是一種貪心策略。EvvEvvwdistiiii),(),(000procedure Dijkstra(G:所有權(quán)都為正數(shù)的加權(quán)連通簡(jiǎn)單圖)G帶有頂點(diǎn)av0,v1,vnz和權(quán)(vi,vj)，若(vi,vj)不是G的邊，則(vi,vj)for i:1 to nL(vi)L(a):0S: （初始化標(biāo)記，a的標(biāo)記為0，其余結(jié)點(diǎn)標(biāo)記為，S是空集while z S beginu:不屬于S的L(u)最小的一個(gè)頂點(diǎn)S:Su for 所有不屬于S的頂點(diǎn)v if L(u)(u,v)L(v)

57、then L(v):L(u)(u,v) 這樣就給S中添加帶最小標(biāo)記的頂點(diǎn)并且更新不在S中的頂點(diǎn)的標(biāo)記 endL(z)從a到z的最短長(zhǎng)度 下面給出該算法的框圖：下面給出該算法的框圖： 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(c)(c,z)2L(b)3，L(d)1

58、0，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結(jié) 束uz，Sa,c,b,d,e,z從a到z的最短路的長(zhǎng)度為13。DijkstraDijkstra算法只求出圖中一個(gè)特定的頂點(diǎn)到其他各定點(diǎn)的最算法只求出

59、圖中一個(gè)特定的頂點(diǎn)到其他各定點(diǎn)的最短路。但在許多實(shí)際問(wèn)題中，需求出任意兩點(diǎn)之間的最短路，短路。但在許多實(shí)際問(wèn)題中，需求出任意兩點(diǎn)之間的最短路，如全國(guó)各城市之間最短的航線，選址問(wèn)題等。當(dāng)然，要求出如全國(guó)各城市之間最短的航線，選址問(wèn)題等。當(dāng)然，要求出一個(gè)圖的任意兩點(diǎn)間的最短距路，只需將圖中每一個(gè)頂點(diǎn)依一個(gè)圖的任意兩點(diǎn)間的最短距路，只需將圖中每一個(gè)頂點(diǎn)依次視為始點(diǎn)，然后用次視為始點(diǎn)，然后用DijkstraDijkstra算法就可以了。算法就可以了。DijkstraDijkstra算法可以應(yīng)用與物流配送中算法可以應(yīng)用與物流配送中 OSPFOSPF（open shortest path first, o

60、pen shortest path first, 開(kāi)放最短路徑優(yōu)先）算開(kāi)放最短路徑優(yōu)先）算法是法是DijkstraDijkstra算法在網(wǎng)絡(luò)路由中的一個(gè)具體實(shí)現(xiàn)。算法在網(wǎng)絡(luò)路由中的一個(gè)具體實(shí)現(xiàn)。 Floyd算法如果有一個(gè)矩陣D=d(ij)，其中d(ij)0表示i城市到j(luò)城市的距離。若i與j之間無(wú)路可通，那么d(ij)就是無(wú)窮大。又有d(ii)=無(wú)窮大。通過(guò)這個(gè)距離矩陣D，把任意兩個(gè)城市之間的最短路徑找出來(lái)。【分析】 對(duì)于任何一個(gè)城市而言，i 到 j 的最短距離不外乎存在經(jīng)過(guò) i 與 j 之間的k和不經(jīng)過(guò)k兩種可能，所以可以令k=1，2，3，.，n(n是城市的數(shù)目)，檢查d(ij)與d(ik)+