數(shù)據(jù)結(jié)構(gòu)（自考） 課件 第5、6章 樹與二叉樹、圖結(jié)構(gòu)

全國高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（專科段）數(shù)據(jù)結(jié)構(gòu)第五章樹與二叉樹學(xué)習(xí)目標(biāo)理解樹及二叉樹的基本概念，掌握二叉樹的基本性質(zhì)掌握樹及二叉樹的存儲(chǔ)方式能夠?qū)崿F(xiàn)樹及二叉樹的基本操作及遍歷算法理解遞歸的概念，能夠?qū)崿F(xiàn)遞歸程序掌握樹、森林與二叉樹之間的相互轉(zhuǎn)換掌握哈夫曼樹及哈夫曼編碼的概念，能夠構(gòu)造哈夫曼樹并設(shè)計(jì)哈夫曼編碼本章主要內(nèi)容樹的基本概念12二叉樹的操作3二叉樹樹和森林4哈夫曼樹及哈夫曼編碼5第一節(jié)樹的基本概念樹是一種層次結(jié)構(gòu)，所以是一種非線性結(jié)構(gòu)日常生活中，經(jīng)常會(huì)遇到具有層次關(guān)系的示例家族中部分成員的輩份關(guān)系樹的定義定義5.1一棵樹（tree）T是由一個(gè)或一個(gè)以上的結(jié)點(diǎn)組成的有限集，其中有一個(gè)特定的結(jié)點(diǎn)R稱為樹T的根結(jié)點(diǎn)。在集合中除根結(jié)點(diǎn)R外，其余的結(jié)點(diǎn)可劃分為k(k≥0)個(gè)不相交的子集T1,T2,…,Tk，其中每個(gè)子集都是樹，并且其相應(yīng)的根結(jié)點(diǎn)R1,R2,…,Rk是R的孩子結(jié)點(diǎn)，R稱為Ri(1≤i≤k)的雙親結(jié)點(diǎn)，Ri(1≤i≤k)互稱為兄弟結(jié)點(diǎn)。子集Ti(1≤i≤k)稱為根R的子樹（subtree）樹的結(jié)點(diǎn)集合至少包含一個(gè)結(jié)點(diǎn)只含有一個(gè)結(jié)點(diǎn)的樹是只有根結(jié)點(diǎn)的樹，也就是單結(jié)點(diǎn)樹對于多結(jié)點(diǎn)的樹，必須有一個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)之間通過邊來連接，邊也稱為分支。含n個(gè)結(jié)點(diǎn)的樹有且僅有n-1條邊，這是樹的重要特性之一根結(jié)點(diǎn)的各子樹之間不會(huì)有重疊樹是一種層次結(jié)構(gòu)，也是遞歸形式的含有A,B,C,D,E,F,G,H,I,J共10個(gè)結(jié)點(diǎn)的樹TA為根結(jié)點(diǎn)，{B,E,F}，{C,G}和{D,H,I,J}構(gòu)成根結(jié)點(diǎn)A的三棵子樹，B,C,D分別是這三棵子樹的根樹中每個(gè)結(jié)點(diǎn)擁有的子樹的個(gè)數(shù)稱為結(jié)點(diǎn)的度結(jié)點(diǎn)的度即為其子結(jié)點(diǎn)的個(gè)數(shù)樹中結(jié)點(diǎn)的度的最大值稱為樹的度度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或終端結(jié)點(diǎn)度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)如果樹中每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間規(guī)定了次序，則樹稱為有序樹具有同一雙親結(jié)點(diǎn)的結(jié)點(diǎn)是兄弟結(jié)點(diǎn)從任一結(jié)點(diǎn)到根結(jié)點(diǎn)之間所經(jīng)過的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)以任一結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的后代將線性結(jié)構(gòu)中的前驅(qū)和后繼概念引申至樹中，將某結(jié)點(diǎn)的雙親結(jié)點(diǎn)看作是它的前驅(qū)，它的孩子結(jié)點(diǎn)看作是它的后繼除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均只有一個(gè)前驅(qū)結(jié)點(diǎn)根的前驅(qū)結(jié)點(diǎn)個(gè)數(shù)為0，除葉結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有若干個(gè)后繼結(jié)點(diǎn)葉結(jié)點(diǎn)的后繼結(jié)點(diǎn)個(gè)數(shù)為0樹中每個(gè)元素的前驅(qū)的個(gè)數(shù)不會(huì)多于1個(gè)，后繼的個(gè)數(shù)可以是任意個(gè)樹是一種層次結(jié)構(gòu)，設(shè)根為0層，根的孩子結(jié)點(diǎn)為1層，依此類推一般地，若某個(gè)結(jié)點(diǎn)位于i（i≥0）層，則它的孩子結(jié)點(diǎn)位于i+1層樹中結(jié)點(diǎn)的最大層數(shù)定義為樹的深度最大層數(shù)加1為樹的高度樹中從某一結(jié)點(diǎn)出發(fā)，到達(dá)另一個(gè)結(jié)點(diǎn)之間所經(jīng)過的邊組成一條路徑路徑中所含的邊數(shù)為路徑長度雖然樹的路徑定義中并沒有限制路徑的方向，但路徑通常是沿一個(gè)方向延伸的，即從某一結(jié)點(diǎn)向根的方向延伸，或是從某一結(jié)點(diǎn)向葉結(jié)點(diǎn)方向延伸通常，以組成路徑的結(jié)點(diǎn)序列來表示該條路徑m（m≥0）棵互不相交的樹構(gòu)成森林對樹中每個(gè)結(jié)點(diǎn)來說，其子樹的集合即為森林第二節(jié)二叉樹定義5.2二叉樹（binarytree）是結(jié)點(diǎn)（node）的一個(gè)有限集合，這個(gè)集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為這個(gè)根的左子樹和右子樹的二叉樹組成。左子樹和右子樹的根分別稱為此二叉樹根結(jié)點(diǎn)的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)二叉樹的左子樹和右子樹都可以存在或者為空，不同的存在狀態(tài)可以組合出5種基本形態(tài)一棵高度為k的二叉樹若有2k-1個(gè)結(jié)點(diǎn)，則二叉樹稱為滿二叉樹從形式上來看，滿二叉樹中除葉結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)，即除最后一層外，每一層的結(jié)點(diǎn)都是“滿”的滿二叉樹中的n個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，從編號(hào)為0的結(jié)點(diǎn)開始，由連續(xù)編號(hào)的任意多個(gè)結(jié)點(diǎn)組成的二叉樹稱為完全二叉樹特殊二叉樹滿二叉樹和完全二叉樹完全二叉樹的特性

二叉樹的性質(zhì)性質(zhì)1在二叉樹的i層上最多有2i個(gè)結(jié)點(diǎn)(i≥0)證明：使用數(shù)學(xué)歸納法證明

歸納基礎(chǔ)：

對于非空的二叉樹T，根在0層，本層只有20=1個(gè)結(jié)點(diǎn)，結(jié)論成立

歸納假設(shè)：

設(shè)二叉樹T中i-1層最多有2i-1個(gè)結(jié)點(diǎn)，考慮i層，由于i層的結(jié)點(diǎn)均為i-1層結(jié)點(diǎn)的孩子結(jié)點(diǎn)，而二叉樹中每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，故i層最多有2

2i-1=2i個(gè)結(jié)點(diǎn)

根據(jù)歸納法原理，性質(zhì)1得證

性質(zhì)3對任何非空二叉樹T，設(shè)n0是葉結(jié)點(diǎn)的個(gè)數(shù)，n2是度為2的結(jié)點(diǎn)的個(gè)數(shù)，則有n0=n2+1證明：設(shè)二叉樹T中度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，則T中結(jié)點(diǎn)總數(shù)n為 n=n0+n1+n2 n-1=2

n2+1

n1+0

n0

將上兩式聯(lián)立求解，得到 n0=n2+1

二叉樹的存儲(chǔ)——順序存儲(chǔ)結(jié)構(gòu)對于完全二叉樹，各層自上至下，同層間自左至右，將結(jié)點(diǎn)依次存入數(shù)組從前至后的各個(gè)元素中。按照前面使用過的編號(hào)方法，一般來講，編號(hào)為i的結(jié)點(diǎn)存放在數(shù)組中下標(biāo)為i的位置使用這樣的存儲(chǔ)規(guī)則可以很方便地找到二叉樹中的相關(guān)結(jié)點(diǎn)，即若知道二叉樹某一結(jié)點(diǎn)保存在數(shù)組中下標(biāo)i的位置，則可以很方便地求出它的雙親結(jié)點(diǎn)（若存在）和左、右孩子結(jié)點(diǎn)（若存在）在數(shù)組中的位置對于一般的二叉樹，順序存儲(chǔ)的思想是，針對二叉樹中的每個(gè)位置，不論這個(gè)位置有沒有結(jié)點(diǎn)，都在數(shù)組中預(yù)留保存空間。采用這種存儲(chǔ)方式保存完全二叉樹時(shí)，既不浪費(fèi)空間，又便于有關(guān)操作的實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義一個(gè)結(jié)點(diǎn)結(jié)構(gòu)：它含有兩個(gè)指針域，一個(gè)指針用來指向該結(jié)點(diǎn)左孩子所在的結(jié)點(diǎn)，稱為左孩子指針，簡稱為左指針；另一個(gè)指針用來指向該結(jié)點(diǎn)右孩子所在的結(jié)點(diǎn)，稱為右孩子指針，簡稱為右指針。此外，還定義一個(gè)用來保存結(jié)點(diǎn)中數(shù)據(jù)的數(shù)據(jù)域二叉鏈表表示二叉樹結(jié)點(diǎn)類的定義及二叉樹的定義二叉鏈表中結(jié)點(diǎn)類的定義及二叉樹的定義typedefintELEMType;typedefstructBNode //二叉樹結(jié)點(diǎn){ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左孩子、右孩子的指針}BinTNode;typedefBinTNode*BTree; //二叉樹二叉鏈表中到底有多少空指針域呢設(shè)二叉樹中有n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都含有兩個(gè)指針域，則二叉鏈表中共有2

n個(gè)指針域已知含n個(gè)結(jié)點(diǎn)的樹中僅含有n-1個(gè)分支，即只有n-1個(gè)指針域不為空，則其余的n+1個(gè)指針域均為空可以看出，二叉鏈表中有超過一半的指針域都是空的，這些都是結(jié)構(gòu)性開銷第三節(jié)二叉樹的操作二叉樹的生成按照二叉樹的順序存儲(chǔ)方式，將二叉樹各結(jié)點(diǎn)值保存在一維數(shù)組中，然后建立二叉鏈表如要建立如下的二叉鏈表輸入的數(shù)組是inta[]={0,1,2,3,4,NA,5,NA,NA,NA,NA,NA,NA,6};函數(shù)CreateBinaryTree遞歸處理二叉鏈表的生成調(diào)用它的主程序中先創(chuàng)建一個(gè)根結(jié)點(diǎn)，其中保存數(shù)組首元素的值，該結(jié)點(diǎn)作為參數(shù)傳遞給函數(shù)CreateBinaryTree。這個(gè)結(jié)點(diǎn)的位置是下標(biāo)0，將這個(gè)位置值也作為參數(shù)傳給函數(shù)CreateBinaryTree主程序中BTreeroot;root=(BTree)malloc(sizeof(BinTNode));root->data=a[0];root->left=NULL;root->right=NULL;調(diào)用函數(shù)CreateBinaryTree。參數(shù)0是起始位置CreateBinaryTree(0,n,a,root);生成二叉鏈表如果下標(biāo)i處的結(jié)點(diǎn)有左孩子，則其應(yīng)該保存在下標(biāo)2

i+1處如果有右孩子，則應(yīng)該保存在下標(biāo)2

i+2處故在函數(shù)內(nèi)，判斷數(shù)組中位置2

i+1及位置2

i+2處是否保存了元素值如果確實(shí)有值，則分配空間創(chuàng)建結(jié)點(diǎn)且保存數(shù)組中相應(yīng)位置的元素值，并讓下標(biāo)i處結(jié)點(diǎn)的相應(yīng)指針指向新創(chuàng)建的結(jié)點(diǎn)然后再以2

i+1或2

i+2為參數(shù)值，遞歸調(diào)用函數(shù)，去處理2

i+1或2

i+2位置處結(jié)點(diǎn)的左孩子和右孩子如果數(shù)組中數(shù)據(jù)的存儲(chǔ)是正確的，則能正確建立二叉鏈表。如果位置2

i+1或位置2

i+2處沒有保存元素值，則遞歸結(jié)束二叉樹的遍歷對非空的二叉樹的遍歷可以相應(yīng)地分解為三項(xiàng)“子任務(wù)”訪問根結(jié)點(diǎn)遍歷左子樹（即依相應(yīng)的規(guī)律訪問左子樹中的全部結(jié)點(diǎn)）遍歷右子樹（即依相應(yīng)的規(guī)律訪問右子樹中的全部結(jié)點(diǎn)）常規(guī)的3種遍歷算法分別是先序遍歷、中序遍歷和后序遍歷。這3種遍歷也分別稱為先根遍歷、中根遍歷和后根遍歷先序遍歷算法若二叉樹為空，則返回；否則依次執(zhí)行以下操作（1）訪問根結(jié)點(diǎn)（2）先序遍歷左子樹（3）先序遍歷右子樹中序遍歷算法若二叉樹為空，則返回；否則依次執(zhí)行以下操作（1）中序遍歷左子樹（2）訪問根結(jié)點(diǎn)（3）中序遍歷右子樹后序遍歷算法若二叉樹為空，則返回；否則依次執(zhí)行以下操作（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根結(jié)點(diǎn)先序遍歷過程中序遍歷過程后序遍歷過程示例寫出其先序、中序及后序遍歷序列先序遍歷序列為A,B,D,G,H,J,K,E中序遍歷序列為G,D,J,H,K,B,E,A后序遍歷序列為G,J,K,H,D,E,B,A先序遍歷算法先序遍歷算法中序遍歷算法中序遍歷算法后序遍歷算法后序遍歷算法給出二叉樹的先序遍歷序列和中序遍歷序列，能唯一確定該二叉樹給出二叉樹的后序遍歷序列和中序遍歷序列，能唯一確定該二叉樹示例設(shè)二叉樹T的先序遍歷序列是A,B,D,G,H,J,K,E，中序遍歷序列是G,D,J,H,K,B,E,A，畫出二叉樹T由先序遍歷序列可知，T的根是A在中序遍歷序列中查找A的位置，位于A前面的是其左子樹的中序遍歷序列，位于A后面的是其右子樹的中序遍歷序列從而將原問題的求解（對整棵樹的還原）分解為兩個(gè)更小問題的求解（對兩棵子樹的還原）示例統(tǒng)計(jì)以二叉鏈表表示的二叉樹T中葉結(jié)點(diǎn)的個(gè)數(shù)T中葉結(jié)點(diǎn)的個(gè)數(shù)等于根左子樹中葉結(jié)點(diǎn)的個(gè)數(shù)加上根右子樹中葉結(jié)點(diǎn)的個(gè)數(shù)。所以如果遞歸調(diào)用已經(jīng)得到了兩棵子樹中葉結(jié)點(diǎn)的個(gè)數(shù)，那么將結(jié)果相加即求解示例編寫程序，返回二叉樹T的高度仍是使用遞歸的思想去編寫程序。如果左子樹的高度和右子樹的高度都已經(jīng)知道，則二叉樹T的高度就可求得，樹的高度是兩棵子樹中較高者的高度再加1層序遍歷所謂按層遍歷，即是從根結(jié)點(diǎn)開始逐層向下遍歷，直到最后一層對于同一層的結(jié)點(diǎn)，由左到右遍歷各結(jié)點(diǎn)同一層中的結(jié)點(diǎn)相繼被訪問，同時(shí)，它們之間的相對次序也決定著它們孩子結(jié)點(diǎn)的相對次序。即同一層中的結(jié)點(diǎn)u和結(jié)點(diǎn)v，若先遍歷u再遍歷v，則u的孩子結(jié)點(diǎn)的遍歷也早于v的孩子結(jié)點(diǎn)的遍歷按層進(jìn)行遍歷先訪問最上面一層即0層中的元素，輸出1然后依次訪問1的子結(jié)點(diǎn)2和3再繼續(xù)訪問2的子結(jié)點(diǎn)和3的子結(jié)點(diǎn)依此類推，得到的層序遍歷結(jié)果是：1,2,3,4,5,6,7層序遍歷算法二叉樹層序遍歷的算法二叉樹的應(yīng)用可以使用二叉樹來表示一個(gè)表達(dá)式，這樣的二叉樹稱為表達(dá)式樹2*y*(a+3*y)-b畫出表達(dá)式樹先根據(jù)運(yùn)算符的優(yōu)先級對表達(dá)式加括號(hào)去掉最外層括號(hào)。中間的運(yùn)算符為根，前后兩部分分別對應(yīng)于左子樹和右子樹對左子樹遞歸執(zhí)行步驟②對右子樹遞歸執(zhí)行步驟②當(dāng)遇到空串時(shí)，遞歸結(jié)束第四節(jié)樹和森林樹的存儲(chǔ)結(jié)構(gòu)父結(jié)點(diǎn)表示法孩子結(jié)點(diǎn)表示法孩子-兄弟表示法父結(jié)點(diǎn)表示法樹中每個(gè)結(jié)點(diǎn)至少含兩個(gè)域，一個(gè)域用來保存結(jié)點(diǎn)本身的值，另一個(gè)域用來保存結(jié)點(diǎn)之父結(jié)點(diǎn)的相關(guān)信息孩子結(jié)點(diǎn)表示法父結(jié)點(diǎn)-孩子結(jié)點(diǎn)表示法孩子-兄弟表示法為樹中的每個(gè)結(jié)點(diǎn)定義一個(gè)存儲(chǔ)結(jié)點(diǎn)，其中有左、右兩個(gè)指針域，左指針域指向這個(gè)結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)，右指針域指向這個(gè)結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)樹、森林與二叉樹的轉(zhuǎn)換樹和二叉樹都可以用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)同一個(gè)二叉鏈表，若按樹的存儲(chǔ)含義來解釋，可以還原為樹。若按二叉樹的存儲(chǔ)含義來解釋，可以還原為二叉樹正是因?yàn)檫@一點(diǎn)，可以在樹與二叉樹之間建立一種對應(yīng)關(guān)系轉(zhuǎn)換規(guī)則規(guī)則1：將森林轉(zhuǎn)換成二叉樹設(shè)F={T1,T2,…,Tm}是森林，則可按如下規(guī)則將森林F轉(zhuǎn)換為一棵二叉樹B=(root,LB,RB)（1）若F為空（m=0），則B為空樹（2）若F非空（m>0），則森林中T1的根作為二叉樹B的根root；T1中各子樹組成的森林F1={T11,T12,…,T1s}轉(zhuǎn)換成的二叉樹作為B的左子樹BL；森林F’={T2,T3,…,Tm}轉(zhuǎn)換成的二叉樹作為B的右子樹BR森林轉(zhuǎn)換為二叉樹轉(zhuǎn)換規(guī)則規(guī)則2：將二叉樹還原為森林設(shè)B=(root,BL,BR)是一棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F={T1,T2,…,Tm}（1）若B為空，則F為空（2）若B非空，則B的根root作為F中第一棵樹T1的根；B的左子樹BL還原得到的森林作為T1的各子樹；B的右子樹BR還原得到的森林作為F中的T2,T3,…,Tm樹和森林的遍歷樹的兩種遍歷策略先序（根）遍歷先訪問樹的根結(jié)點(diǎn)，再依次先序遍歷根結(jié)點(diǎn)的各棵子樹后序（根）遍歷若樹的根結(jié)點(diǎn)有子樹，則首先后序遍歷各棵子樹，然后再訪問根結(jié)點(diǎn)；否則（根結(jié)點(diǎn)無子樹），只訪問根結(jié)點(diǎn)森林的兩種遍歷策略先序遍歷森林森林的先序遍歷過程，是按照樹的排列次序，先序遍歷各棵樹后序遍歷森林森林的后序遍歷過程，是按照樹的排列次序，后序遍歷各棵樹可以看出，森林的遍歷序列中，各棵樹中的結(jié)點(diǎn)不會(huì)混雜在一起森林與對應(yīng)的二叉樹的遍歷序列的關(guān)系二叉樹的先序遍歷序列和中序遍歷序列，與森林的先序遍歷序列和后序遍歷序列分別相同第五節(jié)哈夫曼樹及哈夫曼編碼編碼ASCII編碼、Unicode碼、電報(bào)碼定長編碼算法簡單，效率高在編碼長度確定之后，譯文的長度完成取決于原文的長度變長編碼變長編碼前綴特性：一個(gè)編碼方案中，任何一個(gè)字符的編碼都不是該方案中任何其他字符編碼的前綴，這樣的編碼稱為具有前綴特性正是因?yàn)榫幋a方案具有前綴特性，才能夠保證譯碼過程的正確性和唯一性?？梢允褂枚鏄鋪肀硎疽粋€(gè)編碼方案在二叉樹的分支上標(biāo)注0或1，從根到某結(jié)點(diǎn)的路徑上，各分支標(biāo)注的0或1組成一個(gè)編碼哈夫曼樹二叉樹中，葉結(jié)點(diǎn)的帶權(quán)路徑長度定義為葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度二叉樹的帶權(quán)路徑長度，就是樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和二叉樹的外部帶權(quán)路徑長度記為WPL其中n為葉結(jié)點(diǎn)個(gè)數(shù)，wk為第k個(gè)葉結(jié)點(diǎn)的權(quán)值，lk為第k個(gè)葉結(jié)點(diǎn)的路徑長度各字符出現(xiàn)的頻度分別是6、12、25、30，構(gòu)造4棵二叉樹，分別計(jì)算其WPL值4棵二叉樹的帶權(quán)路徑長度WPL分別為134、195、139和146我們的任務(wù)是構(gòu)造具有最小WPL且滿足前綴特性的編碼樹設(shè)有n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造具有n個(gè)葉結(jié)點(diǎn)的二叉樹，每個(gè)葉結(jié)點(diǎn)帶有一個(gè)權(quán)值wi。在所有這樣的二叉樹中，帶權(quán)路徑長度WPL最小的一棵二叉樹稱為哈夫曼樹構(gòu)造哈夫曼樹的算法根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}(n≥2)，構(gòu)造含n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹Ti(1≤i≤n)只有一個(gè)根結(jié)點(diǎn)，它帶有權(quán)值wi(i=1,2,…,n)在F中選出兩棵根結(jié)點(diǎn)權(quán)值最?。ㄈ绻邢嗟鹊臋?quán)值，則任意選）的二叉樹分別作為左、右子樹，新增加一個(gè)根結(jié)點(diǎn)，從而構(gòu)造一棵新的二叉樹，新二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和。然后從F中刪去選出的這兩棵樹，加入這棵新構(gòu)造的樹重復(fù)步驟②，直到F中只有一棵樹時(shí)為止，這棵樹就是哈夫曼樹示例已知字符集S={a,b,c,d,e}，對應(yīng)的權(quán)值為{17,25,12,6,14}，試構(gòu)造哈夫曼樹，并計(jì)算其WPL初始時(shí)，5個(gè)權(quán)值分別對應(yīng)一棵單結(jié)點(diǎn)的樹，并按權(quán)值從小到大排序選擇權(quán)值最小的兩棵樹進(jìn)行合并，新增加的根結(jié)點(diǎn)表示為圓形結(jié)點(diǎn)。新樹的根結(jié)點(diǎn)的權(quán)值是18，選擇權(quán)值小的樹作為左子樹，權(quán)值大的樹作為右子樹繼續(xù)選擇權(quán)值最小的兩棵樹進(jìn)行合并。新樹的根結(jié)點(diǎn)的權(quán)值是31。將選中的兩棵樹刪除，增加新合并的樹繼續(xù)這個(gè)過程最后得到的結(jié)果WPL=14

2+17

2+6

3+12

3+25

2=166哈夫曼算法得到的哈夫曼樹中沒有度為1的結(jié)點(diǎn)，因?yàn)槊看魏喜r(shí)都選擇了兩棵樹分別作為左子樹和右子樹初始時(shí)如果給定的權(quán)值個(gè)數(shù)為n，則哈夫曼樹的構(gòu)建過程需要n-1步。得到的哈夫曼樹中，葉結(jié)點(diǎn)個(gè)數(shù)為n，分支結(jié)點(diǎn)個(gè)數(shù)為n-1，結(jié)點(diǎn)總數(shù)為2n-1哈夫曼編碼在哈夫曼樹中，對于所有的分支結(jié)點(diǎn)，其左分支標(biāo)以0，右分支標(biāo)以1。這樣標(biāo)記以后，將從根到葉結(jié)點(diǎn)的路徑上標(biāo)記的0和1依次收集起來，可以得到葉結(jié)點(diǎn)對應(yīng)字符的具體編碼，這就是哈夫曼編碼哈夫曼樹及編碼編碼的帶權(quán)平均碼長=譯文總位數(shù)/原文字符總數(shù)=166/74

2.24已知譯文是110010101111000011，其原文是什么？從哈夫曼樹根開始，根據(jù)編碼的各位決定選擇的分支，前2位是11，故得到字符b。接下來，00對應(yīng)于字符e。依此類推。最終得到的原文是becabdebThankYou!全國高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（專科段）數(shù)據(jù)結(jié)構(gòu)第六章圖結(jié)構(gòu)學(xué)習(xí)目標(biāo)理解圖的定義和相關(guān)的基本概念掌握圖的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)掌握圖基本操作的實(shí)現(xiàn)掌握并實(shí)現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先搜索算法，理解圖的連通性及連通分量概念理解圖的生成樹概念，掌握求圖最小代價(jià)生成樹的兩個(gè)算法理解有向無環(huán)圖的概念，掌握圖的拓?fù)渑判蛩惴ɡ斫庾疃搪窂礁拍?，掌握迪杰斯特拉算法的求解過程了解各算法的時(shí)間復(fù)雜度本章主要內(nèi)容圖的基本概念12圖基本操作的實(shí)現(xiàn)3圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷4圖的生成樹56單源最短路徑7DAG圖及拓?fù)渑判虻谝还?jié)圖的基本概念圖（graph）由頂點(diǎn)和邊組成一般地，用G=(V,E)來表示，其中V表示頂點(diǎn)（vertex）集，是一個(gè)有窮非空集合；E表示邊（edge）集，E中的每條邊都是V中某一對頂點(diǎn)的連接當(dāng)頂點(diǎn)分別是u和v時(shí)，連接這兩個(gè)頂點(diǎn)的邊可以表示為一個(gè)二元組(u,v)，有時(shí)也將邊稱為頂點(diǎn)的偶對圖中任意兩個(gè)不同頂點(diǎn)之間允許有邊，但不能超過一條基本概念圖G=(V,E)中，頂點(diǎn)總數(shù)記為|V|，邊的總數(shù)記為|E|如果圖中邊的數(shù)目較少（相對于頂點(diǎn)數(shù)來說），則圖稱為稀疏圖邊數(shù)較多的圖稱為密集圖或是稠密圖至于邊數(shù)多到多少是密集圖或少到多少是稀疏圖，并沒有嚴(yán)格的界定當(dāng)圖中邊數(shù)的數(shù)量級不高于頂點(diǎn)數(shù)的數(shù)量級時(shí)，就可以認(rèn)為圖是稀疏圖基本概念當(dāng)圖中的邊限定為從一個(gè)頂點(diǎn)指向另一個(gè)頂點(diǎn)時(shí)，稱為有向邊，或稱為?。╝rc）不限定方向的邊稱為無向邊一條無向邊可以看成是兩條方向相反的有向邊組成有向邊的偶對看作是有序的組成無向邊的偶對是無序的基本概念有向邊(u,v)表示從頂點(diǎn)u指向頂點(diǎn)v的邊，弧的方向是從u指向v，u稱為弧尾（tail），v稱為弧頭（head）對于有向邊，(u,v)與(v,u)不同無向邊(u,v)既可以表示從頂點(diǎn)u指向頂點(diǎn)v，也可以表示從頂點(diǎn)v指向頂點(diǎn)u對于無向邊，(u,v)與(v,u)是等價(jià)的基本概念含有向邊的圖稱為有向圖（directedgraph或簡寫為digraph）如果圖中的邊都是無向邊，則圖稱為無向圖（undirectedgraph或簡寫為undigraph）如果一個(gè)圖中既含有有向邊，又含有無向邊，則可以將其中所有的無向邊表示為一對方向相反的有向邊提到有向圖時(shí)，表明其中所含的邊全部都是有向邊基本概念若無向圖G中含有邊(u,v)，則u和v互為鄰接點(diǎn)（adjacent）邊(u,v)稱為與頂點(diǎn)u和v相關(guān)聯(lián)（incident），也可以說邊(u,v)依附于頂點(diǎn)u和v對于有向圖中的有向邊(u,v)，稱頂點(diǎn)v是頂點(diǎn)u的鄰接點(diǎn)頂點(diǎn)u鄰接到頂點(diǎn)v，或頂點(diǎn)v鄰接自頂點(diǎn)u可以給邊賦予一個(gè)非負(fù)的數(shù)值，這個(gè)非負(fù)數(shù)值稱為邊的權(quán)（weight），相應(yīng)的圖稱為帶權(quán)圖（weightedgraph）或是加權(quán)圖可以讓各頂點(diǎn)帶有標(biāo)號(hào)，這樣的圖稱為標(biāo)號(hào)圖（labedledgraph）本章討論的圖大多是標(biāo)號(hào)圖，標(biāo)號(hào)可以作為頂點(diǎn)的名稱示例圖中兩個(gè)頂點(diǎn)之間的邊不能有重復(fù)無向圖中兩個(gè)頂點(diǎn)之間最多只能有一條邊有向圖中兩個(gè)頂點(diǎn)之間最多有兩條方向相反的弧圖中不包含(i,i)形式的邊，即沒有頂點(diǎn)自身到自身的邊在無向圖中，與頂點(diǎn)v相關(guān)聯(lián)的邊的數(shù)目稱為頂點(diǎn)的度（degree）在有向圖中，頂點(diǎn)的度分為出度和入度以某頂點(diǎn)為弧頭的弧稱為該頂點(diǎn)的入邊，入邊的數(shù)目稱為該頂點(diǎn)的入度以某頂點(diǎn)為弧尾的弧稱為該頂點(diǎn)的出邊，出邊的數(shù)目稱為該頂點(diǎn)的出度一個(gè)頂點(diǎn)的出度和入度之和稱為該頂點(diǎn)的度有n個(gè)頂點(diǎn)的無向圖中，其邊數(shù)最多可達(dá)n(n-1)/2有向圖中由于邊具有方向性，所以可能的最大邊數(shù)比無向圖多了一倍，含n個(gè)頂點(diǎn)的有向圖中最大邊數(shù)為n(n-1)

包含了所有可能邊的圖稱為完全圖（completegraph）假設(shè)無向圖G=(V,E)中含有n個(gè)頂點(diǎn)，e條邊，每個(gè)頂點(diǎn)的度為di(0≤i≤n-1)，則下列關(guān)系式成立：若兩個(gè)圖G=(V,E)和G'=(V',E')，滿足條件：V’V，E’E且E'中邊依附的頂點(diǎn)均屬于V'，則稱G'為G的子圖（subgraph）一個(gè)圖G的子圖是指由圖G中選出其頂點(diǎn)集的一個(gè)子集Vs以及僅與Vs中頂點(diǎn)相關(guān)聯(lián)的一些邊所構(gòu)成的圖示例對于圖G，圖G1、G2、G3和G4都是它的子圖；特別地，圖G1與圖G完全一樣，它也是圖G的子圖，即圖本身也是它自身的子圖；同時(shí)，圖G2也是圖G4的子圖。而圖G5不是圖G的子圖在圖G=(V,E)中，如果(vi0,vi1),(vi1,vi2),…,(vim-2,vim-1)都是E中的邊，則頂點(diǎn)序列(vi0,vi1,…,vim-1)稱為從頂點(diǎn)vi0到頂點(diǎn)vim-1的路徑（path）若圖G是有向圖，則路徑也要求是有向的，且有向邊必須是方向一致的，即有向路徑(vi0,vi1,…,vim-1)是由E中的弧(vi0,vi1),(vi1,vi2),…,(vim-2,vim-1)組成的路徑(vi0,vi1,…,vim-1)中包含的邊或弧的數(shù)目m稱為路徑長度如果路徑上各頂點(diǎn)均不同，則稱此路徑為簡單路徑（simplepath）第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路（cycle），也稱為環(huán)如果一個(gè)回路中除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)均不相同，則稱為簡單回路（simplecycle）或簡單環(huán)不帶回路的圖稱為無環(huán)圖。不帶回路的有向圖稱為有向無環(huán)圖從頂點(diǎn)0到頂點(diǎn)3到頂點(diǎn)4再到頂點(diǎn)1構(gòu)成一條有向簡單路徑(0,3,4,1)，路徑長度為3從頂點(diǎn)2到頂點(diǎn)3到頂點(diǎn)4再回到頂點(diǎn)2構(gòu)成一個(gè)簡單有向回路(2,3,4,2)從頂點(diǎn)2到頂點(diǎn)0再到頂點(diǎn)3，雖然其中均有邊相連，但由于邊的方向不一致，所以不能構(gòu)成有向路徑對于無向圖G，如果頂點(diǎn)u和頂點(diǎn)v之間有路徑，則稱這兩個(gè)頂點(diǎn)是連通的如果無向圖G中任意一個(gè)頂點(diǎn)到其他任意頂點(diǎn)都至少存在一條路徑，也就是說，圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱圖G為連通圖（connectedgraph）無向圖中的極大連通子圖稱為連通分量（connectedcomponent）有向圖G中，如果每對頂點(diǎn)u與v之間均有從u到v的有向路徑，則稱G為強(qiáng)連通圖（stronglyconnectedgraph）有向圖的最大強(qiáng)連通子圖稱為強(qiáng)連通分量如果對于每對頂點(diǎn)u和v，存在頂點(diǎn)序列vi0,vi1,…,vim-1，這里u=vi0，v=vim-1，并且(vij,vij+1)∈E或(vij+1,vij)∈E(0≤j≤m-2)，則稱圖G為弱連通圖（weaklyconnectedgraph）示例圖的基本操作VType表示頂點(diǎn)類型MEdge表示邊的類型圖的基本操作定義頂點(diǎn)使用單字符表示，保存在頂點(diǎn)表verticesList[MaxVtxNum]中，使用兩個(gè)輔助方法，在頂點(diǎn)字符與頂點(diǎn)表下標(biāo)之間進(jìn)行轉(zhuǎn)換intVerToNum(MGraphg,VTypeu) //返回頂點(diǎn)u在頂點(diǎn)表verticesList中的下標(biāo)值VType

NumToVer(MGraphg,inti) //返回頂點(diǎn)表verticesList中下標(biāo)i對應(yīng)的頂點(diǎn)第二節(jié)圖的存儲(chǔ)結(jié)構(gòu)圖也有兩類基本的存儲(chǔ)方式，即順序存儲(chǔ)結(jié)構(gòu)及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)以鄰接矩陣（adjacencymatrix）為代表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以鄰接表（adjacencylist）為代表鄰接矩陣設(shè)圖G=(V,E)，|V|=n，圖的鄰接矩陣是一個(gè)n

n矩陣，矩陣元素表示圖中各頂點(diǎn)之間的鄰接關(guān)系，鄰接矩陣也稱為相鄰矩陣設(shè)各頂點(diǎn)為v0,v1,…,vn-1，如果從vi到vj存在一條邊，則鄰接矩陣中位于i行j列的元素值為1，否則值為0這樣的一個(gè)矩陣可以表示圖中所有頂點(diǎn)之間的鄰接關(guān)系鄰接矩陣的存儲(chǔ)空間與頂點(diǎn)個(gè)數(shù)有關(guān)，為O(|V|2)鄰接矩陣是一個(gè)二維數(shù)組對于帶權(quán)圖鄰接矩陣是對稱矩陣有向圖的鄰接矩陣不能保證對稱性用鄰接矩陣表示圖時(shí)，可以很容易地判定圖中任意兩頂點(diǎn)之間是否存在邊（或弧）若矩陣元素A[i][j]為1或wij，就表示從vi到vj有一條邊（或?。?，否則從vi到vj沒有邊（或?。┐嬖诮柚卩徑泳仃嚕苋菀椎玫綀D中各頂點(diǎn)的度對于無向圖G，鄰接矩陣i行或i列中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的度對于有向圖G，鄰接矩陣i行中非零（也不等于∞）元素的個(gè)數(shù)為頂點(diǎn)vi的出度而i列中非零（也不等于∞）元素的個(gè)數(shù)為頂點(diǎn)vi的入度i行非零（也不等于∞）元素的個(gè)數(shù)加上i列非零（也不等于∞）元素的個(gè)數(shù)為頂點(diǎn)vi的度設(shè)用鄰接矩陣表示有n個(gè)頂點(diǎn)的圖G，計(jì)算G中有多少條邊時(shí)，需要檢查矩陣中的所有元素，因此時(shí)間復(fù)雜度為O(n2)存儲(chǔ)空間僅與圖G中的頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)，即為O(n2)設(shè)圖G=(V,E)，則G的鄰接表由一個(gè)一維數(shù)組和n=|V|個(gè)鏈表組成一維數(shù)組包含n個(gè)元素，每個(gè)元素包含表示頂點(diǎn)信息的域和一個(gè)指針域與頂點(diǎn)vi(0≤i≤n-1)相鄰接的所有頂點(diǎn)組成一個(gè)單鏈表，其表頭指針保存在一維數(shù)組下標(biāo)為i的元素的指針域中鄰接表鄰接表表結(jié)點(diǎn)的結(jié)構(gòu)對于帶權(quán)圖，可以擴(kuò)展鄰接表的結(jié)構(gòu)，在單鏈表的每個(gè)表結(jié)點(diǎn)中增加一個(gè)域，用來存儲(chǔ)兩個(gè)頂點(diǎn)間這條邊的權(quán)表結(jié)點(diǎn)結(jié)構(gòu)用鄰接表表示有n個(gè)頂點(diǎn)和e條邊的無向圖時(shí)，需要一個(gè)由n個(gè)元素組成的順序表（表頭結(jié)點(diǎn)表）和由總共2e個(gè)結(jié)點(diǎn)組成的n個(gè)單鏈表表示有n個(gè)頂點(diǎn)e條弧的有向圖時(shí)，需要一個(gè)由n個(gè)元素組成的順序表和由總共e個(gè)結(jié)點(diǎn)組成的n個(gè)單鏈表鄰接表的空間復(fù)雜度為O(n+e)當(dāng)圖中頂點(diǎn)個(gè)數(shù)經(jīng)常變化時(shí)，為便于頂點(diǎn)的插入和刪除，也可以將圖的全部頂點(diǎn)保存在一個(gè)單鏈表中，而不是一維數(shù)組中。單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)如下所示指向下一頂點(diǎn)的指針指向鄰接點(diǎn)表的指針頂點(diǎn)信息第三節(jié)圖基本操作的實(shí)現(xiàn)采用鄰接矩陣存儲(chǔ)的圖的定義頂點(diǎn)表的相應(yīng)查詢查詢邊的權(quán)值創(chuàng)建圖創(chuàng)建無向圖創(chuàng)建有向帶權(quán)圖驗(yàn)證圖構(gòu)建函數(shù)的正確性找到某頂點(diǎn)的第一個(gè)鄰接點(diǎn)查找下一個(gè)鄰接點(diǎn)獲取頂點(diǎn)個(gè)數(shù)及邊數(shù)intgetNumVertices(MGraphg){ returng.numVertices;}intgetNumEdges(MGraphg){ returng.numEdges;}第四節(jié)圖的遍歷定義6.1給定一個(gè)連通圖G=(V,E)，從圖中的某個(gè)頂點(diǎn)出發(fā)，經(jīng)過一定的路線訪問圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)被訪問且只訪問一次，這一過程稱為圖的遍歷深度優(yōu)先搜索（depthfirstsearch,DFS）遍歷廣度優(yōu)先搜索（breadthfirstsearch,BFS）遍歷深度優(yōu)先搜索選擇圖中任意指定頂點(diǎn)為起始頂點(diǎn)，將其設(shè)為當(dāng)前頂；訪問當(dāng)前頂點(diǎn)v，輸出關(guān)于v的相關(guān)信息將v的訪問標(biāo)志置為VISITED如果v的鄰接點(diǎn)中存在未被訪問的頂點(diǎn)w，則將w設(shè)為當(dāng)前頂點(diǎn)，轉(zhuǎn)②繼續(xù)；否則轉(zhuǎn)⑤回退到最近被訪問過的且仍有未被訪問鄰接點(diǎn)的頂點(diǎn)u，轉(zhuǎn)④繼續(xù)；不能回退時(shí)，轉(zhuǎn)⑥如果所有頂點(diǎn)均已訪問，則遍歷結(jié)束，否則，選擇未被訪問的另一個(gè)頂點(diǎn)作為起始頂點(diǎn)，繼續(xù)上述過程v0,v1,v3,v7,v4,v5,v2,v6DFS算法當(dāng)圖是連通圖時(shí)，使用DFS算法從某個(gè)頂點(diǎn)出發(fā)，可以訪問到圖中的所有頂點(diǎn)。如果圖不連通，則一次調(diào)用DFS不能訪問圖中的全部頂點(diǎn)，只能訪問初始頂點(diǎn)所在的連通分量中的所有頂點(diǎn)廣度優(yōu)先搜索選擇圖中指定的頂點(diǎn)v為起始頂點(diǎn)，將其入隊(duì)列，且其訪問標(biāo)志置為VISITED隊(duì)列為空時(shí)，轉(zhuǎn)⑤；隊(duì)列不為空時(shí)，出隊(duì)列，設(shè)出隊(duì)列的頂點(diǎn)為w輸出關(guān)于w的相關(guān)信息找到與頂點(diǎn)w相鄰接的且訪問標(biāo)志不是VISITED的頂點(diǎn)序列w1,w2,…,wk，依次入隊(duì)列，轉(zhuǎn)②如果所有頂點(diǎn)均已訪問，則遍歷結(jié)束，否則，選擇未被訪問的一個(gè)頂點(diǎn)作為起始頂點(diǎn)，繼續(xù)上述過程廣度優(yōu)先搜索過程中，使用了一個(gè)隊(duì)列作為輔助存儲(chǔ)結(jié)構(gòu)，頂點(diǎn)是一批批加入隊(duì)列的如果圖是不連通的，則這個(gè)過程也不能訪問圖中的全部頂點(diǎn)，而只能遍歷圖中某個(gè)連通分量中的所有頂點(diǎn)BFS算法第五節(jié)圖的生成樹設(shè)G=(V,E)是一個(gè)連通的無向圖，包含圖中全部頂點(diǎn)的極小連通子圖稱為圖的生成樹極小連通子圖是指含有圖中所有頂點(diǎn)并使圖仍保持連通性的最小子圖從圖中任一頂點(diǎn)出發(fā)，按照深度優(yōu)先搜索策略或是廣度優(yōu)先搜索策略，可以訪問到圖中的全部頂點(diǎn)。在遍歷的過程中，所經(jīng)過的邊集設(shè)為T(G)，沒有經(jīng)過的邊集設(shè)為B(G)。T(G)即構(gòu)成G的一棵生成樹生成樹中所含的邊數(shù)必定是n-1進(jìn)行深度優(yōu)先搜索時(shí)得到的生成樹稱為深度優(yōu)先生成樹進(jìn)行廣度優(yōu)先搜索時(shí)得到的生成樹稱為廣度優(yōu)先生成樹進(jìn)行遍歷時(shí)可能會(huì)得到不同的頂點(diǎn)序列，實(shí)際上，圖的生成樹也可能是不唯一的同一個(gè)圖的深度優(yōu)先生成樹，也可能不是唯一的廣度優(yōu)先生成樹，也可能不是唯一的示例兩棵深度優(yōu)先生成樹圖的最小代價(jià)生成樹帶權(quán)圖的每條邊上都有一個(gè)非負(fù)的權(quán)值，稱邊權(quán)值之和最小的生成樹為最小代價(jià)生成樹（minimum_costspanningtree，MST）。簡稱為最小生成樹給定一個(gè)無向連通圖G，則MST是一個(gè)包括G的所有頂點(diǎn)及其邊子集的圖，邊的子集滿足下列條件這個(gè)子集中所有邊的權(quán)之和為所有滿足條件的子集中最小的子集中的邊能夠保證圖是連通的最小生成樹性質(zhì)它含有圖G中的所有n個(gè)頂點(diǎn)它沒有回路。因?yàn)閺臉?gòu)成回路的各邊中去掉一條邊，仍能保證其連通性，而所得的權(quán)值總和可以進(jìn)一步地減少它含有的邊數(shù)為n-1去掉最小生成樹中的一條邊，換上不在最小生成樹中的另外一條邊，在仍要求連通的前提下，所得的權(quán)值總和都不會(huì)小于原最小生成樹的權(quán)值總和普里姆算法設(shè)連通的帶權(quán)圖G=(V,E)，V是頂點(diǎn)集合，E是邊的集合設(shè)T是圖G的最小生成樹的邊集合，U是最小生成樹的頂點(diǎn)集合，設(shè)由頂點(diǎn)v1開始，初始時(shí)T=Ф，U={v1}在所有u∈U，v∈V-U的邊(u,v)∈E中選擇一條權(quán)最小的邊(ui,vj)，將vj并入U(xiǎn)中，將邊(ui,vj)并入T中重復(fù)②，直到U=V時(shí)結(jié)束示例普里姆算法是貪心算法的一個(gè)實(shí)例，每次選出一條連接U中頂點(diǎn)及V-U中頂點(diǎn)的具有最小權(quán)值的邊，逐步生成最小生成樹普里姆算法共進(jìn)行n-1輪的選邊操作，每輪選邊時(shí)，最多從n-1條邊中選中權(quán)最小的邊。故對于含|V|個(gè)頂點(diǎn)的圖，算法的時(shí)間復(fù)雜度為O(|V|2)當(dāng)圖是一個(gè)邊稠密的圖時(shí)，適合使用普里姆算法求圖的最小生成樹克魯斯卡爾算法設(shè)E1的初值：E1=Φ，T中只含有圖中的所有頂點(diǎn)，頂點(diǎn)個(gè)數(shù)為n=|V|當(dāng)E1中邊數(shù)小于n-1時(shí)，重復(fù)執(zhí)行下面的步驟在圖G的邊集E中選擇權(quán)值最小的邊(u,v)，并從E中刪除它如果u和v分別屬于T中不同的連通分量，則將邊(u,v)加入到E1中去，否則丟掉該邊，選擇E中的下一條權(quán)值最小的邊邊權(quán)值(6,8)2(7,8)2(5,8)3(1,3)4(3,4)5(4,7)5(1,4)6(1,2)6(3,7)6(2,5)7(2,6)7(5,6)10(4,5)14克魯斯卡爾算法中，從|E|條邊中選出權(quán)值最小的邊(u,v)，并檢測u和v是不是在同一連通分量上，時(shí)間花費(fèi)為O(|E|log|E|)。所以，克魯斯卡爾算法適宜求稀疏圖的最小生成樹第六節(jié)有向無環(huán)圖及拓?fù)渑判驁D中不存在回路的有向圖稱為有向無環(huán)圖（directedacyclinegraph），簡稱為DAG圖比如，表達(dá)式樹可表示為DAG圖拓?fù)渑判蛴邢驘o環(huán)圖G=(V,E)的拓?fù)湫蛄惺荊中頂點(diǎn)的一個(gè)線性序列，并且滿足以下關(guān)系：對于圖G中的所有頂點(diǎn)v和w，如果(v,w)∈E，則在線性序列中v排在w之前求有向無環(huán)圖拓?fù)湫蛄械倪^程稱為拓?fù)渑判蛟谟邢驁D中，以頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（activityonvertexnetwork），簡稱為AOV網(wǎng)在AOV網(wǎng)中，若從頂點(diǎn)vi到vj有一條有向路徑，則稱vi是vj的前驅(qū)，vj是vi的后繼若(vi,vj)是AOV網(wǎng)中的一條弧，則稱vi是vj的直接前驅(qū)，vj是vi的直接后繼如果vi是vj的前驅(qū)或直接前驅(qū)，則vi活動(dòng)必須在vj活動(dòng)開始之前結(jié)束，即vj活動(dòng)必須在vi活動(dòng)結(jié)束之后才能開始在AOV網(wǎng)中不允許出現(xiàn)回路，因此AOV網(wǎng)必是有向無環(huán)圖拓?fù)渑判蚩梢詫OV網(wǎng)中的各個(gè)活動(dòng)排序，它把AOV網(wǎng)中各頂點(diǎn)按照它們之間的先后關(guān)系排成一個(gè)線性序列在AOV網(wǎng)中，如果從頂點(diǎn)vi到頂點(diǎn)vj存在有向路徑，則在拓?fù)湫蛄兄?，vi必定排在vj的前面；如果從頂點(diǎn)vi到頂點(diǎn)vj沒有有向路徑，則在拓?fù)湫蛄兄?，vi與vj的先后次序可以任意五門課程排成的拓?fù)湫蛄袨?C1,C2,C3,C4,C5還可以排列成 C1,C2,C5,C3,C4課程代號(hào)課程名稱先導(dǎo)課C1高等數(shù)學(xué)無C2程序設(shè)計(jì)基礎(chǔ)無C