(PPT)第2章性數(shù)據(jù)結(jié)構(gòu)樹和圖

1、下一頁上一頁停止放映 西安交通大學(xué)計教中心西安交通大學(xué)計教中心下一頁上一頁停止放映第2頁/91樹形結(jié)構(gòu)樹形結(jié)構(gòu)是以分支關(guān)系來定義的層次結(jié)構(gòu)。在客觀世界中樹形結(jié)構(gòu)廣泛存在，并應(yīng)用于：人類社會的族譜、家譜、行政區(qū)域劃分管理；各種社會組織機(jī)構(gòu)；在計算機(jī)領(lǐng)域中，用樹表示源程序的語法結(jié)構(gòu)；在os中，文件系統(tǒng)、目錄等組織結(jié)構(gòu)也是用樹來表示的。下一頁上一頁停止放映第3頁/91樹的邏輯結(jié)構(gòu)樹是一種數(shù)據(jù)結(jié)構(gòu)，可用二元組表示為： tree=（d，r）其中：d 是具有相同特性的數(shù)據(jù)元素的集合；r 是數(shù)據(jù)元素間邏輯關(guān)系的集合，且滿足：在d中存在唯一的稱為根的數(shù)據(jù)元素，沒有前趨；d中其余數(shù)據(jù)元素都有且只有一個前趨；d中

2、所有元素，或有若干個互不相同的后繼（子樹），或無后繼（葉結(jié)點）； 則稱tree為樹。下一頁上一頁停止放映第4頁/91樹的遞歸定義: gacfdeb下一頁上一頁停止放映第5頁/91樹結(jié)構(gòu)舉例c1（章） book 1.1(節(jié)) 1.2 c1 c2 c3 c2 2.1 1.1 1.2 2.1 2.2 2.3 2.11 2.12 2.2 2.1.1 2.1.2 2.3c3書目錄 目錄樹 樹結(jié)構(gòu)下一頁上一頁停止放映第6頁/91與樹相關(guān)的術(shù)語 結(jié)點：在樹結(jié)構(gòu)中一般把數(shù)據(jù)元素及其若干指向子樹的分支稱為結(jié)點。 結(jié)點的度：結(jié)點擁有的非空子樹的個數(shù)。 樹的度：樹中所有結(jié)點的度的最大值。 葉子結(jié)點：度為0的結(jié)點。

3、分支結(jié)點：至少有一個非空子樹的結(jié)點。 孩子結(jié)點和父結(jié)點：某結(jié)點所有子樹的根結(jié)點都稱為該結(jié)點的孩子結(jié)點，同時該結(jié)點也稱為其孩子結(jié)點的父結(jié)點。下一頁上一頁停止放映第7頁/91 兄弟結(jié)點：具有相同父結(jié)點的結(jié)點互為兄弟結(jié)點。 結(jié)點的層次：根結(jié)點的層次為1,其子結(jié)點的層次為2。依次類推，子結(jié)點的層次總比父結(jié)點多一層。 樹的深度：樹中結(jié)點所在的最大層次。 有序樹和無序樹：將樹中各結(jié)點的子樹看成自左向右有序的，則稱該樹為有序樹。否則稱為無序樹。 森林：由零棵或有限棵互不相交的樹組成的集合。 下一頁上一頁停止放映第8頁/91二叉樹的定義二叉樹是另一種樹形結(jié)構(gòu)： binary_tree =( d,r) 其中:

4、d 是具有相同性質(zhì)的數(shù)據(jù)元素的集合; r 是在d上某個兩元關(guān)系的集合,且滿足:d中存在唯一稱為根的數(shù)據(jù)元素,沒有前趨;d中其余元素都有且僅有一個前趨;每個結(jié)點至多只有兩個子樹;d中元素,或有兩個互不相交后繼,或無后繼;左、右子樹分別又是一棵二叉樹。下一頁上一頁停止放映第9頁/91二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) （a）（b）（c）（d）（e）o 空結(jié)點空結(jié)點 o 單個結(jié)點單個結(jié)點oo右子樹為空右子樹為空的二叉樹的二叉樹oo左子樹為空左子樹為空的二叉樹的二叉樹左、右子左、右子樹非空的樹非空的二叉樹二叉樹ooo下一頁上一頁停止放映第10頁/91二叉樹與樹的區(qū)別二叉樹與樹的區(qū)別 表達(dá)形式（對

5、3個結(jié)點） 普通樹 二叉樹 （a） （b） （c） （d） （e） oooooo有兩種不同形式有兩種不同形式（a）（b b）ooooooooooooooo有五種不同形式有五種不同形式下一頁上一頁停止放映第11頁/91二叉樹與樹的區(qū)別（二）二叉樹與樹的區(qū)別（二） 觀念二叉樹的子樹有順序關(guān)系，分左子樹和右子樹，而樹則無此區(qū)分；二叉樹的分支度一定為0、1或2，而樹的度可大于2。下一頁上一頁停止放映第12頁/91特殊二叉樹特殊二叉樹滿二叉樹完全二叉樹平衡二叉樹二叉排序樹下一頁上一頁停止放映第13頁/91滿二叉樹滿二叉樹q當(dāng)二叉樹每個分支結(jié)點的度都是當(dāng)二叉樹每個分支結(jié)點的度都是2 2，且所有葉子，且所有

6、葉子結(jié)點都在同一層上，則稱其為滿二叉樹。結(jié)點都在同一層上，則稱其為滿二叉樹。q若若k k為二叉樹為二叉樹t t的深度，且的深度，且t t中共有中共有2 2k-1-1個結(jié)點個結(jié)點（k k 1 1），則稱），則稱t t為滿二叉樹。為滿二叉樹。（a） 滿二叉樹 （b）非滿二叉樹 oooo o oooooooo下一頁上一頁停止放映第14頁/91完全二叉樹完全二叉樹q從滿二叉樹葉子所在的層次中，自右向從滿二叉樹葉子所在的層次中，自右向左連續(xù)刪除若干葉子所得到的二叉樹被左連續(xù)刪除若干葉子所得到的二叉樹被稱為完全二叉樹。稱為完全二叉樹。（a）完全二叉樹 （b） 非完全二叉樹ooooooooooo葉結(jié)點只可能

7、出現(xiàn)在層次最大的兩層上。下一頁上一頁停止放映第15頁/91平衡二叉樹平衡二叉樹二叉樹上任一結(jié)點的左子樹深度減去右子樹深度的差值，稱為該結(jié)點的平衡因子。任意結(jié)點左、右子樹的深度之差的絕對值1 ，這樣的樹稱為平衡二叉樹。ooooooo ooooooooo（a）平衡二叉樹 （b）非平衡二叉樹下一頁上一頁停止放映第16頁/91二叉排序樹定義二叉排序樹定義二叉排序樹或者是空二叉樹；或者是：左子樹上所有結(jié)點的值均小于根結(jié)點的值；右子樹上所有結(jié)點的值均大于等于根結(jié)點的值；左、右子樹本身又是一棵二叉排序樹。 10571114181515141851012137（a）二叉排序樹 （b）非二叉排序樹下一頁上一頁停

8、止放映第17頁/91二叉樹的性質(zhì)一二叉樹的性質(zhì)一 二叉樹的第i層上至多有2i-1個結(jié)點（ i 1）。利用歸納法證明：i=1時，只有一個結(jié)點，對的；假設(shè)對所有的j，1 j i，命題成立， 即在第j層上，至多有2j-1 個結(jié)點。由歸納假設(shè)，第i-1層上至多有2i-2 個結(jié)點。由于二叉樹的每個結(jié)點的度至多為2，故第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即 22i-2 = 2i-1。下一頁上一頁停止放映第18頁/91二叉樹的性質(zhì)二二叉樹的性質(zhì)二深度為深度為h的二叉樹上至多含的二叉樹上至多含2h-1個結(jié)點個結(jié)點(h1)。i=1h （第（第i i層上的最大結(jié)點數(shù)）層上的最大結(jié)點數(shù)） hi=1

9、= = 2 2i-1i-1 = 2 = 2h h-1-1證明：證明：由性質(zhì)一可見，深度為h的二叉樹的最大結(jié)點數(shù)為：下一頁上一頁停止放映第19頁/91包含包含n(n0)個結(jié)點的二叉樹總的分支數(shù)為個結(jié)點的二叉樹總的分支數(shù)為n-1。二叉樹的性質(zhì)三二叉樹的性質(zhì)三證明：證明： 二叉樹中除了根結(jié)點之外每個元素有且只有一二叉樹中除了根結(jié)點之外每個元素有且只有一個父結(jié)點。在所有子結(jié)點與父結(jié)點間有且只有個父結(jié)點。在所有子結(jié)點與父結(jié)點間有且只有一個分支，即除根外每個結(jié)點對應(yīng)一個分支，一個分支，即除根外每個結(jié)點對應(yīng)一個分支，因此二叉樹總的分支數(shù)為因此二叉樹總的分支數(shù)為n-1。oooo o oooooooo下一頁上一

10、頁停止放映第20頁/91 任意二叉樹，若含有任意二叉樹，若含有n0個葉結(jié)點、個葉結(jié)點、n2個度為個度為2的結(jié)點，則必存在關(guān)系式的結(jié)點，則必存在關(guān)系式n0=n2+1 。二叉樹的性質(zhì)四二叉樹的性質(zhì)四證明：設(shè)二叉樹含有證明：設(shè)二叉樹含有n1個度為個度為1的結(jié)點，則二叉的結(jié)點，則二叉樹結(jié)點總數(shù)顯然為：樹結(jié)點總數(shù)顯然為：n0 + n1 + n2（2-2）再看樹的分支數(shù)，n2個度為2的結(jié)點必然有2n2個分支，n1個度為1的結(jié)點必然有n1個分支。又因為除根結(jié)點外，其余每個結(jié)點都有一個分支進(jìn)入。因此二叉樹的分支數(shù)加1就是結(jié)點總數(shù)。即結(jié)點總數(shù)為： 1 + n1 + 2n2（2-3）由（2-2）和（2-3）兩式可

11、知：n0=n2+1下一頁上一頁停止放映第21頁/91 具有具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為 log2(n)+1。二叉樹的性質(zhì)五二叉樹的性質(zhì)五證明：證明： 假設(shè)二叉樹的深度為假設(shè)二叉樹的深度為h， 則必有則必有2h-1-1n2h-1， 于是有于是有2h-1n+12h，也就是，也就是 2h-1n2h， 從而得到從而得到h-1log2(n)n，則該結(jié)點無左孩子。否則，編號，則該結(jié)點無左孩子。否則，編號為為2i的結(jié)點為其左孩子結(jié)點；的結(jié)點為其左孩子結(jié)點； 若若2i+1n，則該結(jié)點無右孩子。否則，編，則該結(jié)點無右孩子。否則，編號為號為2i+1的結(jié)點為其右孩子結(jié)點。的結(jié)點為其右孩

12、子結(jié)點。證明：通過對證明：通過對i進(jìn)行歸納即可得證。進(jìn)行歸納即可得證。二叉樹的性質(zhì)六二叉樹的性質(zhì)六下一頁上一頁停止放映第23頁/91驗證性質(zhì)六驗證性質(zhì)六 143256 1 2 3 4 5 6 1 2 3 4 5 6 第第i i個結(jié)點就存放在第個結(jié)點就存放在第i i個位置上；個位置上；第第i i個結(jié)點（個結(jié)點（i1)i1)的父結(jié)點就存放在第的父結(jié)點就存放在第 i/2i/2個位置個位置; ;第第i i個結(jié)點的左子結(jié)點就存放在第個結(jié)點的左子結(jié)點就存放在第2 2* *i i的位置的位置; ;右子存放在第右子存放在第2 2* *i+1i+1的位置（的位置（若若2i+1n ）。）。下一頁上一頁停止放映第2

13、4頁/91二叉樹的鏈?zhǔn)酱鎯Χ鏄涞逆準(zhǔn)酱鎯?結(jié)點定義：結(jié)點定義：struct bintreenode elemtype data;struct bintreenode *leftchild, *rightchild; ; struct bintreenode *root; / 定義根結(jié)點指針定義根結(jié)點指針 這里leftchild和rightchild分別為某一結(jié)點指向其左孩子和右孩子的指針。對于葉結(jié)點或一個新生成的結(jié)點而言，其左孩子和右孩子指針都為空值。下一頁上一頁停止放映第25頁/91二叉樹的鏈?zhǔn)酱鎯bcde利用這種結(jié)點形式存儲的樹一般稱為二叉鏈表。從根結(jié)點出發(fā)，可以訪問二叉樹的任何結(jié)點。

14、為了能夠訪問二叉樹，必須保留指向根結(jié)點的指針。這和單鏈表必須保留頭指針的道理一樣。 下一頁上一頁停止放映第26頁/91二叉樹的遍歷二叉樹的遍歷 遍歷（traversing）是樹形結(jié)構(gòu)的一種重要運算，即按一定的次序系統(tǒng)地訪問結(jié)構(gòu)中的所有結(jié)點，使每個結(jié)點只被訪問一次。 遍歷的方法很多，常用的有： 前序法（preorder） 中序法（inorder） 后序法（postorder）下一頁上一頁停止放映第27頁/91前序法（前序法（preorder）方法描述：從根結(jié)點a開始訪問，接著訪問左子結(jié)點b，最后訪問右子結(jié)點c。即：根根左子左子右子右子abc遍歷序列a b c下一頁上一頁停止放映第28頁/91中序

15、法（中序法（inorder）方法描述：從左子結(jié)點b開始訪問，接著訪問根結(jié)點a，最后訪問右子結(jié)點c。即：根根左子左子右子右子abc遍歷序列b a c下一頁上一頁停止放映第29頁/91后序法（后序法（postorder） 方法描述：從左子結(jié)點b開始訪問，接著訪問右子結(jié)點c，最后訪問根結(jié)點a。 即：根根左子左子右子右子abc遍歷序列b c a下一頁上一頁停止放映第30頁/91二叉樹的遍歷舉例二叉樹的遍歷舉例 oooooooooabcdefghi前序遍歷序列：前序遍歷序列：中序遍歷序列：中序遍歷序列：后序遍歷序列：后序遍歷序列： dgebhifcadgebhifcadbgeachfidbgeachfi

16、abdegcfhiabdegcfhi下一頁上一頁停止放映第31頁/91二叉樹遍歷算法（遞歸、前序法二叉樹遍歷算法（遞歸、前序法）void preorder(bintreenode *t) if (t) visit( t ); /訪問根結(jié)點訪問根結(jié)點 preorder( t-leftchild ); /遍歷左子樹遍歷左子樹 preorder( t-rightchild ); /遍歷右子樹遍歷右子樹 abcdef前序遍歷二叉樹的序列為： a b c d e f下一頁上一頁停止放映第32頁/91二叉樹遍歷算法（遞歸、前序法驗證）二叉樹遍歷算法（遞歸、前序法驗證）打印a 取a.左子(b) 打印b取b.

17、左子(c)打印c取c.左子(空)取c.右子(空) 取b.右子(d)打印d取d.左子(e)打印e取e.左子(空)取e.右子(空)取d.右子(f)打印f取f.左子(空)取f.右子(空) 取a.右子(空)結(jié)束a ab bc cd de ef fatopatopbatopbatopbcatopdatopdeatopdatopfatop下一頁上一頁停止放映第33頁/91（2 2）中序遍歷）中序遍歷 對一顆非空二叉樹進(jìn)行中序遍歷時，首先按對一顆非空二叉樹進(jìn)行中序遍歷時，首先按中序遍歷方式訪問左子樹，然后訪問根結(jié)點，中序遍歷方式訪問左子樹，然后訪問根結(jié)點，最后按中序遍歷方式訪問右子樹。中序遍歷最后按中序遍歷

18、方式訪問右子樹。中序遍歷算法如下：算法如下：void inorder(bintreenode *t) if(t) inorder( t-leftchild ); / 遍歷左子樹遍歷左子樹 visit( t ); / 訪問根節(jié)點訪問根節(jié)點 inorder( t-rightchild ); / 遍歷右子樹遍歷右子樹下一頁上一頁停止放映第34頁/91（3 3）后序遍歷）后序遍歷對一顆非空二叉樹進(jìn)行中序遍歷時，首先按對一顆非空二叉樹進(jìn)行中序遍歷時，首先按后序遍后序遍歷歷方式訪問左子樹，然后方式訪問左子樹，然后按后序遍歷按后序遍歷方式訪問右方式訪問右子樹，最后訪問根結(jié)點。子樹，最后訪問根結(jié)點。后序遍歷后

19、序遍歷算法如下：算法如下： void postorder(bintreenode *t) if(t) postorder( t-leftchild ); / 遍歷左子樹遍歷左子樹postorder( t-rightchild ); / 遍歷右子樹遍歷右子樹visit( t ); / 訪問根節(jié)點訪問根節(jié)點下一頁上一頁停止放映第35頁/91表達(dá)式樹及應(yīng)用表達(dá)式樹及應(yīng)用在計算機(jī)中對表達(dá)式進(jìn)行分析和計算是一項重要的任務(wù)。舉例，用二叉樹表示表達(dá)式： a + b * （ c - d）前序遍歷序列：中序遍歷序列：后序遍歷序列：分析： 每個葉結(jié)點為運算對象； 每個非葉結(jié)點為運算符； 每個子樹對應(yīng)一個子表達(dá)式。

20、表達(dá)式處理一般采用后序法，也稱“逆波蘭”法。表達(dá)式處理規(guī)則： 見運算數(shù)入棧； 見運算符，取兩個棧頂元素運算后再壓棧； 直到處理結(jié)束。efbcda a下一頁上一頁停止放映第36頁/91表達(dá)式樹應(yīng)用舉例表達(dá)式樹應(yīng)用舉例（1） a b c d 入棧dcba（1）（2） c - d b a（3） b*（c-d） aa+b*（c-d）（4）（5）a+b*（c-d）fe（6）e/fa+b*（c-d）（7）a+b*（c-d）- e/f（2）遇-，c d 出棧， 運算后再壓棧；（3）遇*，（c - d）和 b 出棧，運算后再壓棧；（4）遇+，b*（c-d）和a出棧，運算后再壓棧；（5）e f 入棧（6）遇/，

21、f e 出棧， 運算后再壓棧；（7）遇-，a+b*（c-d）和e/f出棧，運算后再壓棧。下一頁上一頁停止放映第37頁/91圖的基本概念圖的基本概念 圖的來源圖的來源：通信網(wǎng)、交通網(wǎng)等，它表現(xiàn)了數(shù)據(jù)對：通信網(wǎng)、交通網(wǎng)等，它表現(xiàn)了數(shù)據(jù)對象間多對多的聯(lián)系。在該結(jié)構(gòu)中，數(shù)據(jù)元素一般象間多對多的聯(lián)系。在該結(jié)構(gòu)中，數(shù)據(jù)元素一般稱為頂點稱為頂點。圖的定義：圖的定義：圖是對結(jié)點的前趨和后繼個數(shù)不加限制的圖是對結(jié)點的前趨和后繼個數(shù)不加限制的數(shù)數(shù)據(jù)結(jié)構(gòu)，它據(jù)結(jié)構(gòu)，它v ve e下一頁上一頁停止放映第38頁/91圖例圖例設(shè)圖g1 = （v，e）v=v1，v2，v3，v4e=（v1，v2），（v1，v3）， （v2，

22、v1），（v2，v3）， （v2，v4），（v3，v1）， （v3，v2），（v4，v2） oooov1v2v3v4g1下一頁上一頁停止放映第39頁/91有向圖、無向圖有向圖、無向圖有向圖（digraph） 圖g中頂點的偶對若是有向的，稱為有向圖。如圖g2所示。為示區(qū)別， 其偶對用表示。 例 g2=（v，e） v= 1，2，3，4 e=1，2,1，3， 3，4,4，1無向圖（undigraph） 圖g中頂點的偶對若是無向的，稱為無向圖，其偶對用（vx，vy）表示，如圖g1所示。 1324 g2oooov1v2v3v4g1下一頁上一頁停止放映第40頁/91邊、弧邊、弧邊（edge） 頂點間的關(guān)系

23、可描述為頂點的偶對，也稱為頂點的邊。記為：（vx，vy）。邊是無序的，可看成是（vx，vy），也可看成是（vy，vx）?；。╝rc） 若頂點間的邊是有方向性（有序）的，則稱該偶對為弧。記為：vx，vy?；∈怯行虻?，vx，vy表示從vx到vy?；☆^（head）弧的終點（terminal node）稱為弧頭（方向前方）。弧尾（tail）弧的起始點（initial node）稱為弧尾（方向后方）。 弧 vx，vy表示為，弧尾弧尾 弧頭弧頭vx vyvx vy下一頁上一頁停止放映第41頁/91頂點、鄰接點頂點、鄰接點頂點（頂點（vertexvertex）圖中的數(shù)據(jù)元素（結(jié)點）稱為頂點。如圖g1、g2中

24、的1、2，1，2。鄰接點（鄰接點（adjacentadjacent）無向圖中,若邊（x,y） e，則x和y互為鄰接點;有向圖中，若弧x,y e，則y是x的鄰接點，反之，不是。vxvyx、y互為鄰接點互為鄰接點vxvyy是是x的鄰接點的鄰接點下一頁上一頁停止放映第42頁/91頂點的度（頂點的度（degree）無向圖中，頂點的度是以該頂點為一個端點的邊的條數(shù)。例如，g1中v2的度為3，v4的度為1。有向圖中，以某頂點為弧頭的弧的數(shù)目稱為該頂點的入度（indegree）。例如g2中頂點1的入度為1。以某頂點為弧尾的弧的數(shù)目稱為該頂點的出度（outdegree）。例如g2中頂點1的出度為2。該頂點的度

25、=入度+出度。例如，g2中頂點1的度=2+1=3。oooov1v2v3v4g11324 g2下一頁上一頁停止放映第43頁/91路徑、長度路徑、長度路徑（path） 在圖中，從頂點vx到頂點vy的頂點序列（vx，v1，v2，,vn,vy)稱為從vx到vy的路徑。路徑可能是不唯一的。例如，g1中，v1到v3的路徑為：（v1v2v3）或（v1v3）；而g2中，1到4的路徑為。長度（length） 路徑的長度是該路徑上邊或弧的數(shù)目。例如，g1中v1到v3的長度為1或2；而g2中1到4的長度為2。1324 g2oooov1v2v3v4g1下一頁上一頁停止放映第44頁/91連通圖、強(qiáng)連通圖、連通分量連通圖

26、、強(qiáng)連通圖、連通分量 連通圖（連通圖（connected graphconnected graph） 在無向圖中，若每一對頂點間都有路徑，稱此圖是連通圖。如圖g3所示。 連通分量（連通分量（connected componentconnected component） 無向圖中的極大連通子圖稱為連通 分量。強(qiáng)連通圖（強(qiáng)連通圖（strongly connected graphstrongly connected graph） 在有向圖中，若每對頂點vx到vy間都存在vx到vy，及從vy到vx的路徑，則稱此圖是強(qiáng)連通圖。如圖g4所示。12345g321345g4下一頁上一頁停止放映第45頁/91子

27、圖、生成樹子圖、生成樹子圖 有兩個圖g和g1，若v1v，e1 e，即v1中的頂點都屬于v中的頂點，e1中的關(guān)系都屬于e中的關(guān)系，則稱g1是g的子圖。g =（v，e），g1=（v1，e1） （圖的部分頂點和部分邊組成的圖） 生成子圖、生成樹 設(shè)g是一個連通圖，g中任一包含g的所有頂點的子圖稱為生成子圖。如果該子圖是樹，則稱為g的生成樹。g的生成樹不是唯一的。一棵有n個頂點的生成樹，有且僅有n-1條邊（?。?。（子圖包含所有頂點，但不一定包含所有邊）下一頁上一頁停止放映第46頁/91網(wǎng)、權(quán)網(wǎng)、權(quán)權(quán)（權(quán)（weightweight） 若圖的邊或弧帶有與之相關(guān)的數(shù)，稱此數(shù)為該邊或弧的權(quán)。權(quán)通常用來表示從一

28、個頂點到另一個頂點的距離或費用。網(wǎng)（網(wǎng)（networknetwork） 帶權(quán)的圖稱為網(wǎng)。如g5為帶權(quán)的網(wǎng)。v1v2v3v4g52357下一頁上一頁停止放映第47頁/91圖的存儲方式圖的存儲方式 1 1鄰接矩陣鄰接矩陣?yán)脭?shù)組實現(xiàn)的。它利用一維數(shù)組存儲頂點信息，利用二維數(shù)組存儲頂點間邊或弧的信息。此二維數(shù)組又稱鄰接矩陣鄰接矩陣。 鄰接矩陣存儲方式可用于無向圖或有向圖。無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的。下一頁上一頁停止放映第48頁/91 圖的鄰接矩陣存儲可用下面結(jié)構(gòu)體表示：圖的鄰接矩陣存儲可用下面結(jié)構(gòu)體表示：#define max_num 100 /最大頂點個數(shù)typede

29、f struct vertextype vexsmax_num; /頂點信息數(shù)組arctype matrixmax_nummax_num; /鄰接矩陣int vexnum,arcnum; /圖實際頂點數(shù)和弧(邊)數(shù)int kind; /圖種類標(biāo)志,1有向圖,2有向網(wǎng) / 3無向圖,4無向網(wǎng) mgraph;其中:arctype是頂點關(guān)系的數(shù)據(jù)類型。 vertextype是頂點的數(shù)據(jù)類型。 max_num表示最多可存的頂點數(shù)。下一頁上一頁停止放映第49頁/91假設(shè)無向圖假設(shè)無向圖g=(v,e)g=(v,e)是一個有是一個有n n個頂點的圖，則圖個頂點的圖，則圖的鄰接矩陣的鄰接矩陣a a是是n n階

30、方陣，其內(nèi)容如下：階方陣，其內(nèi)容如下：其中其中w(i,j)w(i,j)是與邊或弧相關(guān)的權(quán)。是與邊或弧相關(guān)的權(quán)。 其它或當(dāng) e)v,(v ev,vji,( if1, ji下一頁上一頁停止放映第50頁/910132528130123410234 (a) (a)無向圖無向圖 (b)(b)有向圖有向圖 (c)(c)網(wǎng)絡(luò)網(wǎng)絡(luò) 0010100011100110110111110a013240010010010000000010101000a38125a01324012340123401230132(a)(a)無向圖鄰接矩陣無向圖鄰接矩陣 (b)(b)有向圖鄰接矩陣有向圖鄰接矩陣 (c)(c)網(wǎng)絡(luò)鄰接矩陣網(wǎng)

31、絡(luò)鄰接矩陣 鄰接矩陣舉例鄰接矩陣舉例 下一頁上一頁停止放映第51頁/912 2鄰接表鄰接表鄰接表存儲形式是一種鏈表與數(shù)組結(jié)合的存儲形式。在鄰接表中有兩種結(jié)點，一種是頭結(jié)點，另一種是表結(jié)點。（1）頭結(jié)點存儲一個頂點的詳細(xì)信息，為了便于管理，所有頭結(jié)點都存放在一個數(shù)組中。（2）對于某個頂點而言，需要將所有與它鄰接的頂點存儲為表結(jié)點形式，并將它們鏈接成單鏈表，這個單鏈表就稱為該頂點的鄰接表。（3）還要在每個頂點的頭結(jié)點中存儲指向其鄰接表首元結(jié)點的指針。 下一頁上一頁停止放映第52頁/91鄰接表的結(jié)點結(jié)構(gòu)鄰接表的結(jié)點結(jié)構(gòu)(c)(c)網(wǎng)絡(luò)的表結(jié)點：網(wǎng)絡(luò)的表結(jié)點：infonextadjvexnextadj

32、vexfirstvexdata(a)(a)頭結(jié)點頭結(jié)點(b)(b)無權(quán)圖的表結(jié)點：無權(quán)圖的表結(jié)點：頂點頂點vi的鄰接點的鄰接點與邊或弧有關(guān)的權(quán)值與邊或弧有關(guān)的權(quán)值存放存放vi信息信息指向指向vi單鏈表的第一個結(jié)點單鏈表的第一個結(jié)點指向指向vi的下一個鄰接點的指針的下一個鄰接點的指針頂點頂點vi的鄰接點的鄰接點指向指向vi的下一個的下一個鄰接點的指針鄰接點的指針下一頁上一頁停止放映第53頁/91鄰接表的舉例鄰接表的舉例無向圖中無向圖中v vi i的度是第的度是第i i個單鏈表的長度。個單鏈表的長度。下一頁上一頁停止放映第54頁/91逆鄰接表逆鄰接表為求頂點為求頂點v vi i的入度，對每個頂點的

33、入度，對每個頂點v vi i，建立一個鏈，建立一個鏈接接 以以v vi i為弧頭的鄰接點鏈表，稱該表為逆鄰接表。為弧頭的鄰接點鏈表，稱該表為逆鄰接表。 顯然逆鄰接表的單鏈表中結(jié)點的個數(shù)就是頂點顯然逆鄰接表的單鏈表中結(jié)點的個數(shù)就是頂點v vi i的的 入度。入度。鄰接表中第鄰接表中第i i個單鏈表的長度是頂點個單鏈表的長度是頂點v vi i的出度。的出度。逆鄰接表中第逆鄰接表中第i i個單鏈表的長度是頂點個單鏈表的長度是頂點v vi i的入度的入度下一頁上一頁停止放映第55頁/91圖的鄰接表描述圖的鄰接表描述 #define max_num 100 /頂點最大允許數(shù)量 struct adjnod

34、e /表結(jié)點類型定義 int adjvex; /該鄰接點在數(shù)組中的位置 infotype info; /該弧相關(guān)信息 struct adjnode *next; /指向下一鄰接點的指針; typedef struct vnode /頭結(jié)點類型定義 vertextype data; /頂點信息 adjnode *first; /指向鄰接表第一個結(jié)點 adjlistmax_num;下一頁上一頁停止放映第56頁/91typedef struct adjlist headarray; /頭結(jié)點數(shù)組int vexnum, arcnum; /圖的當(dāng)前頂點數(shù)和弧數(shù)int kind; /圖的種類標(biāo)志 algr

35、aph; 其中： adjnode為表結(jié)點； infotype為與邊相關(guān)信息的數(shù)據(jù)類型（包括權(quán)等）； vnode為頭結(jié)點； vertextype是頂點的數(shù)據(jù)類型； max_num表示最多可以存放的頂點個數(shù)。下一頁上一頁停止放映第57頁/91圖的遍歷圖的遍歷圖的遍歷（traversing graph） 從圖中指定頂點出發(fā)訪問圖中每一個頂點，且使每個頂點只被訪問一次，該過程為圖的遍歷。圖的遍歷要比樹結(jié)構(gòu)復(fù)雜的多。出發(fā)點不同，任一頂點的鄰接點就不相同，路徑也就不同。因為圖中元素是“多對多”的關(guān)系，為避免發(fā)生重復(fù)，設(shè)立一個輔助數(shù)組visited，每訪問一個頂點，便將其狀態(tài)visitedi置為“真”。下一

36、頁上一頁停止放映第58頁/91圖的遍歷方法圖的遍歷方法常用的圖的遍歷方法有兩種：深度優(yōu)先遍歷法廣度優(yōu)先遍歷法下一頁上一頁停止放映第59頁/91深度優(yōu)先遍歷法深度優(yōu)先遍歷法算法思想：step1 從圖中某個頂點v0出發(fā)，并訪問此頂點；step2 從v0出發(fā)，訪問與v0鄰接的頂點v1后，再從v1出發(fā)，訪問與v1鄰接且未被訪問過的頂點v2。重復(fù)上述過程，直到不存在未訪問過的鄰接點為止。step3 如果是連通圖，從任一頂點v0出發(fā)，就可以遍歷所有相鄰接的頂點；如果是非連通圖，則再選擇一個未被訪問過的頂點作為出發(fā)點，重復(fù)step1、step2，直到全部被訪問過的鄰接點都被訪問為止。下一頁上一頁停止放映第6

37、0頁/91深度優(yōu)先遍歷法舉例深度優(yōu)先遍歷法舉例遍歷過程遍歷過程 訪問頂點訪問頂點 所過邊所過邊起始頂點起始頂點v1 vv1 v1 1 v1v1的第的第1 1個鄰接點個鄰接點v3 vv3 v3 3 （v v1 1，v v3 3）v3v3的第的第1 1個鄰接點個鄰接點v1v1已訪問，已訪問， 取下一個鄰接點取下一個鄰接點v5 vv5 v5 5 （v v3 3，v v5 5）v5v5的第的第1 1個鄰接點個鄰接點v3v3已訪問，已訪問， 取下一個鄰接點取下一個鄰接點v2 vv2 v2 2 （v v5 5，v v2 2）v2v2的兩個鄰接點均被訪問，的兩個鄰接點均被訪問， 回退到回退到v5v5，v5v

38、5的鄰接點均被訪問，的鄰接點均被訪問， 回退到回退到v3v3，v3v3的鄰接點均被訪問的鄰接點均被訪問 ， 回退到回退到v1v1，v1v1的另一個鄰接點的另一個鄰接點v4v4 未被訪問未被訪問 v v4 4 （v v1 1，v v4 4）v4v4的第一個鄰接點的第一個鄰接點v1v1已被訪問，已被訪問， 另一個鄰接點另一個鄰接點v6v6未被訪問未被訪問 v v6 6 （v v4 4，v v6 6）v6v6的鄰接點被訪問，回退到的鄰接點被訪問，回退到v4v4v4v4的鄰接點均被訪問的鄰接點均被訪問回退到回退到v1v1，返回到出發(fā)點，遍歷結(jié)束。，返回到出發(fā)點，遍歷結(jié)束。v1v3v5v4v6g6v2示

39、例示例下一頁上一頁停止放映第61頁/91遍歷產(chǎn)生的結(jié)果遍歷產(chǎn)生的結(jié)果深度優(yōu)先遍歷g6所走過的序列： v1 v3 v5 v2 v4 v6v1v3v5v2v4v6所走過的邊： （v1，v3）,（v3，v5）,（v5，v2）,（v1，v4）,（v4，v6）遍歷生成樹下一頁上一頁停止放映第62頁/91下一頁上一頁停止放映第63頁/91bool visitedmax; /頂點訪問標(biāo)志數(shù)組 void dfstraverse(algragh g) for(int i=0;ig.vexnum;i+) visitedi =false; for(int i=0;ig.vexnum;i+) if( ! visite

40、di ) dfs(g,i) ;void dfs(algraph g, int v) /從v頂點出發(fā)遞歸深度優(yōu)先遍歷圖g adjnode *p; visitedv = true; coutvnext ) if(!visitedp-adjvex) dfs(g,p-adjvex); 下一頁上一頁停止放映第64頁/91深度優(yōu)先遍歷算法程序深度優(yōu)先遍歷算法程序( (非遞歸非遞歸) )void traver_dfs(algragh g,int v) int stackn,visitedn, top=-1 ; adjnode *p; for (int i=0;in;i+) visitedi= false;

41、coutvadjvex) p=p-next; else coutadjvex.dataadjvex= true ; top+; stacktop=p-adjvex; p=gp-adjvex.first; if( top !=-1) v=stacktop; top- -; p=gv.first; p=p-next; 下一頁上一頁停止放映第65頁/91廣度優(yōu)先遍歷算法廣度優(yōu)先遍歷算法廣度優(yōu)先遍歷法首先訪問第1個頂點所有鄰接點，再訪問下一個頂點所有未被訪問的鄰接點。算法思想：step1 從圖中某個頂點v0出發(fā)，并訪問此頂點；step2 從v0出發(fā)，訪問v0的各個未曾訪問的鄰接點w1，w2，,wk;然

42、后,依此從w1,w2,wk出發(fā)訪問各自未被訪問的鄰接點。step3 重復(fù)step2，直到全部頂點都被訪問為止。下一頁上一頁停止放映第66頁/91廣度優(yōu)先遍歷法舉例廣度優(yōu)先遍歷法舉例遍歷過程 訪問頂點 所過邊起始頂點v1 v1 訪問v1的未被訪問過的 所有鄰接點 v3,v2,v4 （v1,v3） (v1,v2) (v1,v4)訪問v3的未被訪問過 的所有的鄰接點 v5 （v3,v5）訪問v2的未被訪問過 的所有的鄰接點 無訪問v4的未被訪問過 的所有的鄰接點 v6 (v4,v6)所有頂點已被訪問,結(jié)束。v1v3v5v4v6g6v2示例示例下一頁上一頁停止放映第67頁/91遍歷產(chǎn)生的結(jié)果遍歷產(chǎn)生的

43、結(jié)果廣度優(yōu)先遍歷g6所走過的序列： v1 v3 v2 v4 v5 v6v1v3v5v2v4v6所走過的邊： （v1，v3），（v1，v2），（v1，v4）， （v3，v5），（v4，v6）遍歷生成樹下一頁上一頁停止放映第68頁/91程序舉例程序舉例圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。v1v3v5v4v6g6v2深度優(yōu)先遍歷序列：深度優(yōu)先遍歷序列：v1 v3 v5 v2 v4 v6廣度優(yōu)先遍歷序列：廣度優(yōu)先遍歷序列：v1 v3 v2 v4 v5 v61324 g2深度優(yōu)先遍歷序列：深度優(yōu)先遍歷序列： 1 3 4 2廣度優(yōu)先遍歷序列：廣度優(yōu)先遍歷序列： 1 3 2 4示例示例下一頁上一頁停止放映第69

44、頁/91樹和圖的應(yīng)用樹和圖的應(yīng)用 哈夫曼樹和哈夫曼編碼 最小生成樹下一頁上一頁停止放映第70頁/91哈夫曼樹和哈夫曼編碼哈夫曼樹和哈夫曼編碼 設(shè)計二進(jìn)制編碼方案時要考慮不同字符的使用頻率，使用頻率高的字符編碼應(yīng)當(dāng)盡量短一些。但是僅僅考慮使用頻率也是不夠的。例如：某個文件由a、b、c、d 4個字符組成，其中a用得最多，c次之。方案1: a1 c 0 b 10 d 11 那么象1100這樣的二進(jìn)制數(shù)據(jù)具有二義性，既代表aacc，又可代表abc，還可代表dcc。為了不使二進(jìn)制編碼具有二義性，每個字符編碼都不能與其他字符編碼的前面若干位重合。下一頁上一頁停止放映第71頁/91bd ca 0011ab0

45、1d c0011 (a)有二義性的編碼系統(tǒng)對應(yīng)的二叉樹 (b)無二義性的編碼系統(tǒng)對應(yīng)的二叉樹任何一個無二義性的二進(jìn)制字符編碼系統(tǒng)必然與這樣一顆二叉樹對應(yīng)：該二叉樹的葉子結(jié)點對應(yīng)著所有需要轉(zhuǎn)換的字符，并且按照左分支代表0、右分支代表1的規(guī)則，從根到該葉子的分支對應(yīng)的0、1序列就構(gòu)成葉子對應(yīng)字符的二進(jìn)制編碼。 可以利用二叉樹分析字符編碼問題。假設(shè)二叉樹可以利用二叉樹分析字符編碼問題。假設(shè)二叉樹中的左分支代表中的左分支代表0 0，右分支代表，右分支代表1 1，則不論字符是，則不論字符是采用何種采用何種0 0、1 1組合形式構(gòu)成的編碼，它必然對應(yīng)組合形式構(gòu)成的編碼，它必然對應(yīng)某個二叉樹中一個結(jié)點某個二

46、叉樹中一個結(jié)點。下一頁上一頁停止放映第72頁/911 1）假設(shè)每個字符使用頻率是相等的，那么不同字符）假設(shè)每個字符使用頻率是相等的，那么不同字符的編碼長度之和就可衡量編碼系統(tǒng)的優(yōu)劣。的編碼長度之和就可衡量編碼系統(tǒng)的優(yōu)劣。2 2）如果每個字符使用頻率不相等，那么將不同字符）如果每個字符使用頻率不相等，那么將不同字符的編碼長度乘上其使用權(quán)值再加起來，也可衡量編的編碼長度乘上其使用權(quán)值再加起來，也可衡量編碼系統(tǒng)的優(yōu)劣。即用根到每個葉子的路徑長度乘以碼系統(tǒng)的優(yōu)劣。即用根到每個葉子的路徑長度乘以葉子對應(yīng)字符的使用權(quán)值再加起來作為衡量標(biāo)準(zhǔn)，葉子對應(yīng)字符的使用權(quán)值再加起來作為衡量標(biāo)準(zhǔn)，顯然這種加權(quán)和除以字符

47、總數(shù)就是每個字符的加權(quán)顯然這種加權(quán)和除以字符總數(shù)就是每個字符的加權(quán)平均編碼長度。平均編碼長度。 下一頁上一頁停止放映第73頁/91 二叉樹帶權(quán)路徑長度二叉樹帶權(quán)路徑長度：設(shè)二叉樹有：設(shè)二叉樹有n n個帶有權(quán)個帶有權(quán)值的葉子結(jié)點，每個葉子到根的路徑長度乘以值的葉子結(jié)點，每個葉子到根的路徑長度乘以其權(quán)值之和稱為二叉樹帶權(quán)路徑長度。一般記其權(quán)值之和稱為二叉樹帶權(quán)路徑長度。一般記作：作：其中，其中，wi為第為第i個葉子的權(quán)重，個葉子的權(quán)重，li為第為第i個葉子到個葉子到根的路徑長度。根的路徑長度。 哈夫曼樹：哈夫曼樹：以一些帶有固定權(quán)值的結(jié)點作為葉以一些帶有固定權(quán)值的結(jié)點作為葉子所構(gòu)造的，具有子所構(gòu)造

48、的，具有最小最小帶權(quán)路徑長度的二叉樹帶權(quán)路徑長度的二叉樹稱為哈夫曼樹稱為哈夫曼樹。 huffman樹也稱為最優(yōu)樹，是一類帶權(quán)路徑最短的二叉樹。niiilwwpl1下一頁上一頁停止放映第74頁/91huffmanhuffman樹舉例樹舉例以下有三棵樹：（a）（b）（c）abcdabcdacbd777555222444wpla =7x2+5x2+2x2+4x2 = 36wplb =7x3+5x3+2x1+4x2 = 46 wplc = 7x1+5x2+2x3+4x3 = 35 事實證明按哈夫曼樹構(gòu)造二叉樹，可得到很好的特性，應(yīng)用于實際問題，可提高處理效率。下一頁上一頁停止放映第75頁/91應(yīng)用舉例

49、應(yīng)用舉例由統(tǒng)計規(guī)律可知，考試成績的分布符合正態(tài)分布：-1 1 0 分?jǐn)?shù) 059 60 69 70 79 80 89 90 100比例數(shù) 0.05 0.15 0.40 0.3 0.10 根據(jù)正態(tài)分布規(guī)律，在根據(jù)正態(tài)分布規(guī)律，在60609090之間的分?jǐn)?shù)占之間的分?jǐn)?shù)占85%85%，而不及格和優(yōu)秀是少數(shù)。而不及格和優(yōu)秀是少數(shù)。下一頁上一頁停止放映第76頁/91將百分制轉(zhuǎn)換成五分制將百分制轉(zhuǎn)換成五分制 判定樹比較：a60?a70?a80?a90?不及格 及格 中等 良好 優(yōu)秀yyyynnnna80?a70?a90?a60?不及格 優(yōu)秀 良好 中等 中等 及格不及格yyynnnnyy(a)(b)若輸入若

50、輸入1 1萬個數(shù)據(jù)，按萬個數(shù)據(jù)，按a a的判定過程進(jìn)行操作，約的判定過程進(jìn)行操作，約需比較需比較3.23.2萬次，而按萬次，而按b b比較比較, ,則僅需則僅需2.22.2萬次。萬次。下一頁上一頁停止放映第77頁/91構(gòu)造構(gòu)造huffmanhuffman樹樹構(gòu)造huffman樹算法步驟：step1 將n個帶權(quán)值wi（in）的結(jié)點構(gòu)成n棵二叉樹的集合t=t1，t2，tn，每棵二叉樹只有一個根結(jié)點。step2 在t中選取兩個權(quán)值最小的結(jié)點作為左右子樹，構(gòu)成一個新的二叉樹，其根結(jié)點的權(quán)值取左右子樹權(quán)值之和；step3 在t中刪除這兩棵樹，將新構(gòu)成的樹加入到t中；step4 重復(fù)2）、3）步的操作，直

51、到t中只含一棵樹為止，該樹就是huffman樹。下一頁上一頁停止放映第78頁/91假定有一段報文由假定有一段報文由a a、b b、c c、d d四個字符構(gòu)成，它們四個字符構(gòu)成，它們的使用頻率比為的使用頻率比為6 64 42 21 1，則用，則用a a、b b、c c、d d作為作為葉子結(jié)點構(gòu)造哈夫曼樹的過程如圖所示。葉子結(jié)點構(gòu)造哈夫曼樹的過程如圖所示。 若二叉樹中的左分支代表0，右分支代表1,則a、b、c、d的哈夫曼編碼分別為0、10、110、111。 下一頁上一頁停止放映第79頁/91構(gòu)造構(gòu)造huffmanhuffman樹舉例樹舉例以權(quán)值分別為7，5，2，4的結(jié)點a、b、c、d構(gòu)造huffm

52、an樹。t= a b c d cdt3246bt3t26511bt26511cd241118at27t1618a7t1bt3t251118a7t1b511cd264（d）t= t1 （c）t= a t2 （b）t= a b t3 （a）t= a b c d 代入代入t2代入代入t3代入代入t1示例示例下一頁上一頁停止放映第80頁/91huffmanhuffman編碼編碼編碼：用二進(jìn)制數(shù)的不同組合來表示字符的方法。前綴編碼：一種非等長度的編碼(任一個字符的編碼都不是另一個字符編碼的前綴)。 a0b01cd011編碼：編碼：a a（0 0） b b（0101） c c（011011） d d（11

53、1111）方法約定：1）左分支為02）右分支為13）由葉到根路徑上字符組成的二進(jìn)制串就是該葉結(jié)點的編碼。 huffman編碼：一種非等長度的編碼。以給定權(quán)值的結(jié)點構(gòu)造huffman樹，按二進(jìn)制前綴編碼的方式構(gòu)成的編碼為huffman編碼。下一頁上一頁停止放映第81頁/91huffmanhuffman編碼舉例編碼舉例在某系統(tǒng)的通信聯(lián)絡(luò)中可能出現(xiàn)8種字符，其頻率分別為0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，設(shè)權(quán)值分別為5，29，7，8，14，23，3，11，n=8，其huffman樹為：000000011111115378142911234258100huf

54、fman編碼為：編碼為：a 5 0110b 29 01c 7 0111d 8 1111e 14 011f 23 00g 3 1110h 11 010下一頁上一頁停止放映第82頁/91 【例2-5】假定編碼系統(tǒng)中有五個字符假定編碼系統(tǒng)中有五個字符x x、s s、d d、e e、a a，它們的使用頻率比為，它們的使用頻率比為2 29 95 57 78 8，以這些，以這些頻率值作葉子的權(quán)構(gòu)造哈夫曼樹，并輸出哈夫曼頻率值作葉子的權(quán)構(gòu)造哈夫曼樹，并輸出哈夫曼編碼。編碼。 257oooo89ooooo00111001下一頁上一頁停止放映第83頁/91最小生成樹最小生成樹 該問題是構(gòu)造連通圖的最小代價生成樹

55、問題。一棵生成樹的代價就是樹上各邊（?。┑拇鷥r之和?？紤]一個通信網(wǎng)的建設(shè)問題?？紤]一個通信網(wǎng)的建設(shè)問題。若要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，則只需n-1條線路。但在n個城市間，最多可能架設(shè)n*（n-1）/2條線路，選擇哪n-1條線路，使費用最少。普里姆（prim）算法克魯斯卡爾（kruskal）算法下一頁上一頁停止放映第84頁/91實例實例下一頁上一頁停止放映第85頁/91（1 1）普里姆算法）普里姆算法 假定假定g= v, e g= v, e 為連通網(wǎng)絡(luò)，其中為連通網(wǎng)絡(luò)，其中v v為頂點集為頂點集合，合，e e為帶權(quán)邊集合。設(shè)置生成樹頂點集合為帶權(quán)邊集合。設(shè)置生成樹頂點集合u u，最初它只包含某

56、一個頂點。設(shè)置生成樹邊集合最初它只包含某一個頂點。設(shè)置生成樹邊集合t t，最初為空集。而后考察這樣的邊，它的一個頂最初為空集。而后考察這樣的邊，它的一個頂點點uuuu，另一個頂點，另一個頂點vv-uvv-u，每次從所有這樣，每次從所有這樣的邊中選擇權(quán)值最小的邊的邊中選擇權(quán)值最小的邊(u, v)(u, v)加入集合加入集合t t，并，并把頂點把頂點v v加入到集合加入到集合u u中。如此不斷重復(fù)，直到中。如此不斷重復(fù)，直到所有頂點都加入到集合所有頂點都加入到集合u u中為止。中為止。下一頁上一頁停止放映第86頁/91下一頁上一頁停止放映第87頁/91普里姆（普里姆（primprim）算法舉例）算

57、法舉例12345687214357681110912u=1，v-u=2，3，4，5，6，7，812212421473（1）（2）（3）(1) u=1,2,v-u=3,4,5,6,7,8(2) u=1,2,4,v-u=3,5,6,7,8(3) u=1,2,4,7,v-u=3,5,6,8例子下一頁上一頁停止放映第88頁/91普里姆（普里姆（primprim）算法舉例）算法舉例( (續(xù)續(xù)) ) 47535（4）76（5）6(4) u=1,2,4,7,5 , v-u=3,6,8(5) u=1,2,4,7,5,6, v-u=3,8(6) u=1,2,4,7,5,6,3, v-u=8(7) u=1,2,4

58、,7,5,6,3,8), v-u= 43（7）83654722136589155（6）476363558下一頁上一頁停止放映第89頁/91下一頁上一頁停止放映第90頁/91（2 2）克魯斯卡爾算法）克魯斯卡爾算法 假定假定g= v, e 為連通網(wǎng)絡(luò)，其中為連通網(wǎng)絡(luò)，其中v為為頂點集合，頂點集合，e為帶權(quán)邊集合。先構(gòu)造一個為帶權(quán)邊集合。先構(gòu)造一個包含所有頂點，沒有邊的非連通圖包含所有頂點，沒有邊的非連通圖t= v, ，圖中每個頂點自成一個連通分量。，圖中每個頂點自成一個連通分量。當(dāng)在當(dāng)在e中選到一條具有最小權(quán)值的邊時中選到一條具有最小權(quán)值的邊時,若該邊的兩個頂點落在若該邊的兩個頂點落在t的不同的

59、連通分的不同的連通分量上，則將此邊加入到量上，則將此邊加入到t中；否則將此邊中；否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去，直到所有頂點在同一個連此重復(fù)下去，直到所有頂點在同一個連通分量上為止。通分量上為止。 下一頁上一頁停止放映第91頁/91克魯斯卡爾（克魯斯卡爾（kruskalkruskal）算法舉例）算法舉例 1234561524663556251346123(4)131 1462(3)123456 (1)13(2)1 1下一頁上一頁停止放映第92頁/91克魯斯卡爾（克魯斯卡爾（kruskalkruskal）算法舉例）算法舉例( (續(xù)）續(xù)）

60、123456 (5)1234123456152466355613256412435（6）例子下一頁上一頁停止放映第93頁/91結(jié)束語結(jié)束語歡迎參加到中心網(wǎng)站軟件開發(fā)技術(shù)基礎(chǔ)課程的學(xué)習(xí)討論中來。中心網(wǎng)址： http:/課件下載地址: 60/moodle15我的e-mail地址: lzq答疑安排： 每星期五下午：3:006:00 地點： 計教中心505房間 下一頁上一頁停止放映5%ay*sjhixwsgiskv!-7focqiykyob0%d6gn)rpz%)mzq*nz%t!ljb0kl)imd*v6mea8+y0mw8lglxjbl-yspgupx8zm1f