計算機軟件技術(shù)基礎(chǔ)3-3 數(shù)據(jù)結(jié)構(gòu)及算法(樹與圖)

常用數(shù)據(jù)結(jié)構(gòu)及其運算第三章1§3.1概述§3.2線性表§3.3棧與隊

§3.4樹與二叉樹§3.5圖§3.6查找與排序目錄23.4.1樹的定義及其存儲結(jié)構(gòu)3.4.2二叉樹及其性質(zhì)3.4.3二叉樹的遍歷3.4.4二叉樹的應(yīng)用3.4.5小結(jié)3.4樹與二叉樹3非線性數(shù)據(jù)結(jié)構(gòu)元素結(jié)點之間存在分支和層次關(guān)系。(一對多)應(yīng)用：家譜 社會組織機構(gòu)書的章節(jié)劃分 操作系統(tǒng)中的多級目錄結(jié)構(gòu) 高級語言中源程序的語法結(jié)構(gòu)等。

什么是樹？3.4.1樹的定義及其存儲結(jié)構(gòu)4樹的定義(遞歸定義) 樹是由n(n≥0)個結(jié)點組成的有限集合T：

有且僅有一個結(jié)點稱為根結(jié)點(root)

其余結(jié)點分為m(m≥0)個各互不相交的有限集合 T1、T2、…、Tm，其中每一個集合Ti本身又是一棵樹，稱為根結(jié)點root的子樹。

n=0時，為空樹。ABDKEFLMJIHGCT1T2T3root3.4.1樹的定義及其存儲結(jié)構(gòu)52.常用術(shù)語 1）結(jié)點：表示樹中的元素。 2）度：結(jié)點擁有的子樹數(shù)。如A的度為3，B 的度為2。樹的度＝樹中最大的結(jié)點度數(shù)。 3）葉子(終端結(jié)點)：度為0的結(jié)點。 4）孩子：結(jié)點的子樹的根(后繼結(jié)點)。每個結(jié)點 均是其前驅(qū)結(jié)點的孩子。 5）雙親：一個結(jié)點的前驅(qū)結(jié)點。ABDKEFLMJIHGCT1T2T3root12343.4.1樹的定義及其存儲結(jié)構(gòu)66）子孫：以某結(jié)點為根的子樹中的任一結(jié)點。7）祖先：從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。8）兄弟：同一雙親的孩子。9）結(jié)點的層次：根為第一層，根的直接后繼結(jié)點為 第二層，以此類推。10）深度：樹中結(jié)點的最大層次數(shù)。ABDKEFLMJIHGCT1T2T3root12343.4.1樹的定義及其存儲結(jié)構(gòu)7 11）森林：是m(m≥0)棵互不相交的樹的集合 12）有序樹：樹中結(jié)點在同層中按從左到右有序排 列、不能互換的稱為有序樹；反之稱為無序樹。例：ABDKEFLMJIHGCT1T2T3root1234ABCT1ACBT2有序樹：T1!=T2無序樹：T1=T23.4.1樹的定義及其存儲結(jié)構(gòu)8例：用有序樹表示算術(shù)表達式 (A+B)×5/(2×(C-D))/**+5AB2-CD3.4.1樹的定義及其存儲結(jié)構(gòu)9結(jié)點的結(jié)構(gòu)類型：1)異構(gòu)型－根據(jù)結(jié)點的度數(shù)設(shè)置相應(yīng)的指針域。

特點：節(jié)省空間、運算不便。2)同構(gòu)型－每個結(jié)點的指針域個數(shù)均為樹的度數(shù)。

特點：運算方便、浪費空間。·A···B·^^E^^^F^^^C^·^D^^^G^^

例(空鏈域問題)：一棵具有n個結(jié)點的k叉樹，采用同構(gòu)型存儲結(jié)構(gòu)，問有多少個空鏈域？解：總鏈域=nk；非空鏈域=n-1；

所以，空鏈域=n(k-1)+1。若樹度為k,k=1為線性表，k=2時空鏈域最低，即二叉樹。3.4.1樹的定義及其存儲結(jié)構(gòu)3.樹的存儲結(jié)構(gòu)(鏈?zhǔn)?103.4.2二叉樹及其性質(zhì)1.二叉樹的定義及其存儲結(jié)構(gòu)

二叉樹是n(n≥0)個結(jié)點的有限集合，它或為空 樹(n=0)， 或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不 相交的二叉樹構(gòu)成。(遞歸定義。)即：度<=2的有序樹 特點：每個結(jié)點至多有2個孩子，結(jié)點度數(shù)最大為2； 結(jié)點子樹有左右之分。

存儲結(jié)構(gòu)：采用二叉鏈表存儲。BADFEC

A^

B

^F^

^E^

D

^C^

Data

Lchild

Rchild結(jié)點結(jié)構(gòu)：111.二叉樹的定義及其存儲結(jié)構(gòu)

二叉樹的五種形態(tài)

AABABABC思考：二叉樹與二叉有序樹的區(qū)別？二叉樹可以是空的，而二次有序樹至少有一個結(jié)點的度為2。3.4.2二叉樹及其性質(zhì)121265743121110983.4.2二叉樹及其性質(zhì)2.二叉樹的基本性質(zhì)（1）二叉樹的第i層上至多有2i-1(i≥1)個結(jié)點。(可用歸納法證明)證明：當(dāng)k=1時，命題顯然成立。假定k=n-1時命題成立，則第n層（k=n）的結(jié)點數(shù)最多是第n-1層的2倍，所以第n層最多有2*2n-2=2n-1個結(jié)點。命題成立。（2）深度為h的二叉樹中至多含有2h-1個結(jié)點(h>=1)。證明：根據(jù)性質(zhì)1容易知道深度為h的二叉樹最多有20+21+…+2h-1個結(jié)點，即最多有2h-1個結(jié)點。13（3）包含n(n>0)個結(jié)點的二叉樹總的分支數(shù)為n-1證明：二叉樹中除了根結(jié)點之外每個元素有且只有一個父結(jié)點。在所有子結(jié)點與父結(jié)點間有且只有一個分支，即除根外每個結(jié)點對應(yīng)一個分支，因此二叉樹總的分支數(shù)為n-1。3.4.2二叉樹及其性質(zhì)（4）任何一棵二叉樹，若含有n0個葉子結(jié)點、n2個度為2的結(jié)點，則必存在關(guān)系式n0=n2+1證明：設(shè)二叉樹含有n1個度為1的結(jié)點，則二叉樹結(jié)點總數(shù)顯然為：

n0+n1+n2 （2-2）再看看樹的分支數(shù)，n2個度為2的結(jié)點必然有2n2個分支，n1個度為1的結(jié)點必然有n1個分支。又因為除根結(jié)點外，其余每個結(jié)點都有一個分支進入。因此二叉樹的分支數(shù)加1就是結(jié)點總數(shù)。即結(jié)點總數(shù)為： 1+n1+2n2 （2-3）

由（2-2）（2-3）兩式可知：n0=n2+114126574315141312111098滿二叉樹：深度為h且含有2h-1個結(jié)點的二叉樹。結(jié)點編號是自上至下、自左至右。

特點：每一層上的結(jié)點都達到了最大值，即不存在度為1的結(jié)點，葉子結(jié)點均在最底一層

完全二叉樹：一棵有n個結(jié)點的二叉樹，按與滿二叉樹相同的編號方式對結(jié)點進行編號，若樹中n個結(jié)點和滿二叉樹1～n編號完全一致。

性質(zhì)：具有n個結(jié)點的完全二叉樹的深度為：[Log2n]+1

證明：假設(shè)二叉樹的深度為h，則必有2h-1-1<n≤2h-1，于是有2h-1<n+1≤2h，也就是2h-1≤n<2h，從而得到h-1≤log2(n)<h，于是h=[log2(n)]+1。1265743121110981265743121110983.4.2二叉樹及其性質(zhì)3.幾種特殊形式的二叉樹15平衡二叉樹：又稱AVL樹，（Adelson-VerskiiandLandis,阿德爾遜-弗斯基-蘭迪斯樹），它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。 平衡因子＝(結(jié)點的)左子樹深度－右子樹深度) 平衡二叉樹上所有結(jié)點的平衡因子只可能是-1、0、1。1254376非平衡二叉樹1256437平衡二叉樹3.4.2二叉樹及其性質(zhì)163.4.2二叉樹及其性質(zhì)（1）將一般樹轉(zhuǎn)換為二叉樹4.森林與二叉樹的轉(zhuǎn)換②對每個結(jié)點，除了與它的第一個孩子保持聯(lián)系外，去除與其它孩子的聯(lián)系；EACBDIHGF

③以樹根為軸心，將整棵樹順時針旋轉(zhuǎn)45°。

①在兄弟結(jié)點之間加一連線；EACBDIHGFEACBDIHGF17（2）將森林轉(zhuǎn)換為二叉樹--把森林中第二棵樹的根結(jié)點看成是第一棵樹轉(zhuǎn)化成的二叉樹的左孩子的兄弟ACBDEFIHGJEFACBDIHGJACBDEFIHGJ3.4.2二叉樹及其性質(zhì)18（1）順序存儲結(jié)構(gòu)--用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素。5.二叉樹的存儲結(jié)構(gòu)162345完全二叉樹123456其順序存儲3.4.2二叉樹及其性質(zhì)19（1）順序存儲結(jié)構(gòu)例：5.二叉樹的存儲結(jié)構(gòu)123456712345????67注意：對于一般二叉樹，尤其是單支二叉樹，采用順序存儲，按完全二叉樹方式編號，雖能反映結(jié)點間的邏輯關(guān)系，但造成存儲空間的浪費。3.4.2二叉樹及其性質(zhì)20（1）鏈?zhǔn)酱鎯Y(jié)構(gòu)結(jié)點結(jié)構(gòu)：5.二叉樹的存儲結(jié)構(gòu)LchilddataRchildAEBGCDFA^B6^C6^D6^E6^F6^^G6^3.4.2二叉樹及其性質(zhì)213.4.3二叉樹的遍歷 ---遍歷是指循某條搜索路線依次訪問某數(shù)據(jù)構(gòu)中的 全部結(jié)點，而且每個結(jié)點只被訪問一次。1.遍歷二叉樹的定義

依次遍歷根結(jié)點（D）、左子樹（L）、右子樹（R） 三部分。

按先左后右，有以下3種形式：

DLR：先序遍歷（前序遍歷）

LDR：中序遍歷

LRD：后序遍歷

說明：其中的序是針對根結(jié)點來說的。22（1）先序遍歷：根->左->右二叉樹為空，則空操作;訪問根結(jié)點;先序遍歷左子樹;先序遍歷右子樹。1.遍歷二叉樹的定義PreOrder(t)

{

if(t!=NULL){

訪問根結(jié)點；

PreOrder(lchild(t));

PreOrder(rchild(t));

}

}遍歷算法3.4.3二叉樹的遍歷23（2）中序遍歷：左->根->右二叉樹為空，則空操作;中序遍歷左子樹;訪問根結(jié)點;中序遍歷右子樹。1.遍歷二叉樹的定義InOrder(t)

{

if(t!=NULL){

InOrder(lchild(t));

訪問根結(jié)點； InOrder(rchild(t));

}

}遍歷算法3.4.3二叉樹的遍歷24（3）后序遍歷：左->右->根二叉樹為空，則空操作;后序遍歷左子樹;后序遍歷右子樹;訪問根結(jié)點。1.遍歷二叉樹的定義PostOrder(t)

{

if(t!=NULL){

PostOrder(lchild(t));

PostOrder(rchild(t));

訪問根結(jié)點；

}

}遍歷算法3.4.3二叉樹的遍歷25例：ABABABCDABGDEFC先序：AB中序：BA后序：BAABABBAABCDACBDCDBAABDCEFGDBAECFGDBEGFCA3.4.3二叉樹的遍歷26例：已知先序序列為：ABFGCHDEIJLK，中序序列為：FGBHCDILJKEA，求此二叉樹及后序序列。ABEFHDCGILKJ則后序序列為：GFHLKJIEDCBA3.4.3二叉樹的遍歷27例：已知中序序列為：DCBGEAHFIJK，后序序列為：DCEGBFHKJIA，求此二叉樹及先序序列。則后序序列為：ABCDGEIHFJKABKCHJIDEFG3.4.3二叉樹的遍歷28如果給出一棵二叉樹的先序遍歷結(jié)果和中序遍歷結(jié)果，或者給出后序遍歷結(jié)果和中序遍歷結(jié)果，我們就可畫出該二叉樹；如果只給此二叉樹出先序遍歷結(jié)果和后序遍歷結(jié)果，就無法畫出該二叉樹。有兩棵二叉樹T1和T2，它們的先序和后序遍歷結(jié)果完全相同。顯然只憑先序和后序遍歷結(jié)果無法確定到底是哪一棵二叉樹。3.4.3二叉樹的遍歷29 求二叉樹中的葉子數(shù)：

CountLeaf(t,count)

{

if(t!=NULL){

if(lchild(t)==NULL&&rchild(t)==NULL)

count++;

CountLeaf(lchild(t));

CountLeaf(rchild(t));

}2.遍歷的應(yīng)用3.4.3二叉樹的遍歷303.3.4二叉樹的應(yīng)用（1）定義：二叉排序樹是一棵二叉樹，滿足下列條件：空樹；左子樹上的結(jié)點值<根結(jié)點的值；右子樹上的結(jié)點值>=根結(jié)點的值；左、右子樹也是二叉排序樹。1031598921134218

在二叉排序樹中，若按中序遍歷就可以得到由小到大的有序序列。上圖中序遍歷得到： {2，3，4，8，9，9，10，13，15，18，21}1.二叉排序樹311.二叉排序樹 （2）二叉排序樹的插入（生成）

在給定的二叉排序樹中插入值為b的結(jié)點

若樹為空，則作為根結(jié)點； 若樹不空，則將b與根結(jié)點值r作比較：

b<r，插入左子樹；

b>=r，插入右子樹；

（注：新插入的結(jié)點一定是新添的葉子結(jié)點）3.3.4二叉樹的應(yīng)用321.二叉排序樹

插入算法： InsertBet(t,b)

{

if(t==NULL){

GETNODE(t)；

t->data=b; t->lchild=NULL; t->rchild=NUILL;

}

elseif(b<t->data) InsertBet(t->lchild,b);

elseInsertBet(t->rchild,b);

} 3.3.4二叉樹的應(yīng)用33二叉排序樹是一種動態(tài)表結(jié)構(gòu)，即二叉排序樹的生成過程是不斷地向二叉排序樹中插入新的結(jié)點。

1018371282310101810183101883101812831018128231018712823序列{10，18，3，8，12，2，7，3}構(gòu)成一棵二叉排序樹的過程。3.3.4二叉樹的應(yīng)用34 （3）二叉排序樹的刪除：刪除結(jié)點P，使刪除后的二 叉樹仍是二叉排序樹：DelNode(t,p,f)1.二叉排序樹P為葉子結(jié)點P只有左或右子樹直接刪除將P的左子樹或右子樹直接成為其雙親結(jié)點的左右子樹循著P的左子樹的根C找其右子樹分支，找到第一個無右子樹的結(jié)點S，將S的左子樹改為其雙親結(jié)點Q的右子樹，用S取代P。YYNN3.3.4二叉樹的應(yīng)用35

DelNode(*t,*p,*f)

{

fag=0;

if(p->lchild==NULL)f=p->rchild;

elseif(p->rchild==NULL)f=p->lchild;

else{

q=p;s=p->lchild;

while(s->rchild!=NULL){q=s;s=s->rchild;}

if(q==p)q->lchild=s->lchild;

elseq->rchild=s->lchild;

p->data=s->data;free(s);fag=1;

}

if(fag==0){if(f==NULL)t=s;

elseif(f->lchild==p)f->lchild=s;

elsef->rchild=s;

free(p);

}

}刪除算法：3.3.4二叉樹的應(yīng)用36FCLPRfPCQSQLSLpqsFCLPRfSCQQLpqSL例：1.二叉排序樹3.3.4二叉樹的應(yīng)用37例：1.二叉排序樹1018412231576刪71018412231561018423156刪1210154236刪181015426刪361524刪103.3.4二叉樹的應(yīng)用382.哈夫曼樹

----又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。 (1)基本術(shù)語

路徑：從樹中一個結(jié)點到另一個結(jié)點之間 的分支構(gòu)成兩個結(jié)點之間的路徑。

路徑長度：路徑上的分支數(shù)目。

樹的路徑長度：從樹根到每一結(jié)點的路徑長 度之和（PL）。3.3.4二叉樹的應(yīng)用39164532

PL=0+1×2+2×2+3=9例：436251

PL=0+1+2×2+3＋4=12推論：對n個結(jié)點的二叉樹，滿足：最小路徑長度的樹稱為完全二叉樹3.3.4二叉樹的應(yīng)用40

樹的帶權(quán)路徑長度：樹中葉子結(jié)點的帶權(quán)路 徑長度之和。

wk---葉子結(jié)點的權(quán)值，

lk---葉子結(jié)點到根結(jié)點的路徑長度。結(jié)點的帶權(quán)路徑長度：從該結(jié)點到樹根之間的路徑長度與該結(jié)點上權(quán)值的乘積。3.3.4二叉樹的應(yīng)用41

(a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4*3=35(哈夫曼樹)abcd7524dacb7542abcd7524例：(a)(b)(c)3.3.4二叉樹的應(yīng)用42哈夫曼樹：WPL最小的二叉樹稱最優(yōu)二叉樹或哈 夫曼（huffman）樹。注意：加權(quán)路徑最小的二叉樹并非完全二叉樹。哈夫曼樹中沒有度為1的結(jié)點，因此一棵有n 個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點。3.3.4二叉樹的應(yīng)用433.3.4二叉樹的應(yīng)用

①由給定的n個權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}，每棵樹只有一個權(quán)值為Wi的根結(jié)點；

②在F中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和；

③將新二叉樹加入F中，并去除原兩棵樹；

④重復(fù)②、③，直到F中只含一棵樹，即huffman樹（2）哈夫曼樹的構(gòu)造abcdab75c2d4b5c2d4ac2d4ab752475671118(a)(b)(c)(d)44（3）哈夫曼樹的應(yīng)用

最佳判定樹 在解決某些判定問題時，利用哈夫曼樹可以得到 最佳判定算法。例：一批數(shù)據(jù)結(jié)構(gòu)，a<＝20為第一類，概率為2/20; 20<a<＝50為第二類，概率為3/20; 50<a<＝100為第三類，概率為4/20; 其余為第四類，概率為11/20;a≤20NY第一類a≤50NY第二類a≤100YN第三類第四類WPL=2/20+2×3/20+(4/20+11/20)×3 =53/20a>100NY第四類a>50NY第三類a>20YN第二類第一類WPL=11/20+2×4/20+(2/20+3/20)×3 =34/20Huffman樹的判定過程是最佳的3.3.4二叉樹的應(yīng)用453.4.5小結(jié)

理解樹的定義、術(shù)語及存儲結(jié)構(gòu) 掌握二叉樹的概念和性質(zhì)

熟悉滿二叉樹、完全二叉樹和平衡二叉樹的特點 會將一般樹（森林）與二叉樹進行相互轉(zhuǎn)換 掌握二叉樹的遍歷算法 理解二叉排序樹的概念并會構(gòu)造，了解插入 和刪除算法 掌握哈夫曼樹 了解最佳判定算法463.5.1圖的定義及基本術(shù)語3.5.2圖的存儲結(jié)構(gòu)3.5.3圖的遍歷3.4.4圖的應(yīng)用3.4.5小結(jié)3.5圖47 圖比樹更復(fù)雜、更一般，樹是一種簡單的圖。 圖的應(yīng)用---范圍非常廣，如語言學(xué)、邏輯學(xué)、數(shù) 學(xué)、物理、化學(xué)、計算機科學(xué)以及各種工程學(xué)科 領(lǐng)域。 在圖中，結(jié)點之間的關(guān)系可以是任意的多對多的關(guān) 系。3.5圖481.圖的定義 1）圖：由頂點集合V和頂點之間關(guān)系集合R組成。 G=(V,R)， 其中V={v1,v2,…,vn}，是頂點的非空有限集合； R＝{<vi,vj>},是頂點的有序?qū)Γ?/p>

或{(vi,vj)},是頂點的無序?qū)Α?2）無向圖：當(dāng)圖中頂點間的關(guān)系為無序?qū)Α? (vi,vj)=(vj,vi)，稱為邊E。

無向圖記作：G=(V,E)，35241無向圖3.5.1圖的定義及基本術(shù)語例如上圖：G1=(V,E)，

V(G1)={1，2，3，4，5}

E(G1)={(1,2),(1,3),(1,4),(2,3),(3,5)}49vivj弧頭弧尾 3）有向圖：圖中頂點間的關(guān)系為有序?qū)? <vi,vj>稱為弧A， 注意：<vi,vj>≠<vj,vi>，

有向圖記作：G=(V,A)，例如右圖： G2=(V,A)，V(G2)={1,2,3,4,5,6}

A(G2)={<1,2>,<2,1>,<2,4>,<2,3>,<3,5>,<5,6>,<6,3>}有向圖3241563.5.1圖的定義及基本術(shù)語503426751192718331410511216無向網(wǎng)3426751706469584430804375180313260有向網(wǎng) 4）網(wǎng)：若圖中每一條邊附有反映該邊特征的數(shù)據(jù)，則 稱為網(wǎng)，與邊相關(guān)的數(shù)據(jù)稱為權(quán)。 邊上帶權(quán)的無向圖稱為無向網(wǎng)。 弧上帶權(quán)的有向圖稱為有向網(wǎng)。3.5.1圖的定義及基本術(shù)語512.圖的基本術(shù)語 1）子圖：兩個圖G和G′，G=(V,E),G’=(V’,E’)

若， 則稱G′為G的子圖。 例：3241G3G3的子圖：321132413.5.1圖的定義及基本術(shù)語522）度、入度和出度： 度：無向圖中，與某個頂點相連的邊的數(shù)目。

入度：有向圖中，以某個頂點為頭的弧的數(shù)目。 出度：以某個頂點為尾的弧的數(shù)目。35241無向圖3241有向圖3.5.1圖的定義及基本術(shù)語例：有N個頂點的有向圖中，每個頂點的度最大可達多少？

2(N－1)533）路徑和回路：

路徑：在無向圖中，從頂點vp到vq的路徑---- 是頂點序列(vp,vi1,vi2,…,vik,vq)，且(vp,vi1)， (vi1,vi2)，…，(vik,vp)均是E中的邊。

有向路徑：在有向圖中，由頂點的弧組成。

路徑長度：路徑上邊或弧的數(shù)目。 網(wǎng)的路徑長度---路徑上權(quán)值的和。

簡單路徑：除第一個和最后一個頂點外，序列中其余 頂點各不相同的路徑。

簡單回路：第一個頂點和最后一個頂點相同的簡單路徑。3.5.1圖的定義及基本術(shù)語543.5.1圖的定義及基本術(shù)語4）連通圖和連通分量：(對于無向圖定義) 在無向圖G中:

連通：若從頂點vi到vj存在路徑，則稱vi和vj是連通的。35421連通圖(a)6776541非連通圖(b)11855555G1G2G3注意：連通圖只有一個連通分量，即本身。 非連通圖有多個連通分量連通圖：頂點集合V中任意兩個頂點vi和vj都連通， 則稱G為連通圖。連通分量：G中的極大連通子圖稱為該圖的連通分量。 如上圖，(a)為連通圖，(b)不是連通圖，但它有3個 連通分量：G1、G2、G3555）強連通圖和強連通分量：(對于有向圖定義) 在有向圖G中:

連通：從頂點vi到vj有路徑，則稱從vi到vj是連通的。

強連通圖：任意兩個頂點vi和vj都連通， 則稱G為強連通圖。 強連通分量：G中的極大強連通子圖稱為該圖的 強連通分量。

3.5.1圖的定義及基本術(shù)語561.鄰接矩陣（表示頂點之間的關(guān)系） 有n個頂點的圖G=(V,E)，可用n×n的矩陣來表示，矩陣元素為：若(vi,vj)或<vi,vj>是E中的邊或弧反之3.5.2圖的存儲結(jié)構(gòu)若G是網(wǎng)，則鄰接矩陣中每個元素定義為：若(vi,vj)或<vi,vj>是E中的邊或弧反之57 無向圖和無向網(wǎng)的鄰接矩陣為對稱矩陣。例：3241有向圖↓0110

0000

0001

100035241無向圖↓01110

10100

11001

10000

001000270019210

270560110

05010000

061000140

1900003318

21110143300

00001800342675119271833141011216網(wǎng)↓53426751706469584430804375180313260有向網(wǎng)↓080006400

000310600

03000000

032440000

70000018058

750043000

00006900582.鄰接表

鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu),在鄰接表中,對圖中每個頂點建立一個單鏈表，并將它們的表頭指針用向量存儲（鄰接向量）。 第i個單鏈表中的結(jié)點依附于頂點vi的邊(有向圖為弧)，故其結(jié)點數(shù)等于vi的度(有向圖為出度)。3.5.2圖的存儲結(jié)構(gòu)59

鏈結(jié)點結(jié)構(gòu)：adjvex：鄰接域,存儲鄰接頂點 的序號；data：數(shù)據(jù)域，存儲和邊或弧的 權(quán)值信息；nextarc：鏈域指示下一條邊或弧 的結(jié)點adjvexnextarcdata表結(jié)點vexdatafirarc頭結(jié)點vexdata：數(shù)據(jù)域,存儲vi 信息；firarc：鏈域，指向表中 第一個結(jié)點。3.5.2圖的存儲結(jié)構(gòu)601034267511927183314112165342675170646958443080437518031326032413524112345672271272526119121518^51935410^310633211621^46614^718^414611^533^1234567280431230^232170175569^564^660^344^6180443^758^12^3424^1^3^123452121^3^33^14^5^61注意：

表頭結(jié)點有序，以向量存儲(鄰接向量)； 無向圖的鄰接矩陣唯一，但其鄰接表不唯一（次序與鄰接表建立時輸入次序有關(guān)）；

對于無向圖，n個頂點，e條邊，有n個表頭結(jié)點，2e個表結(jié)點，空間復(fù)雜度為O(n+e)； n個頂點的無向圖至多n(n-1)/2條邊（完全圖）。3.5.2圖的存儲結(jié)構(gòu)62 從圖的某一頂點出發(fā)，沿某條路徑，依次對其余頂點進行訪問，為了避免重復(fù)訪問，設(shè)一個輔助數(shù)組visited[n]：3.5.3圖的遍歷初值，未訪問已訪問631.深度優(yōu)先搜索(DFS)：樹的前序遍歷推廣 1）基本思想：從圖的某一個頂點v0出發(fā)進行遍歷，首先訪問起始點v0，然后選擇v0的一個尚未訪問過的鄰接點w，從w出發(fā)繼續(xù)深度優(yōu)先搜索，即訪問w之后選擇w的一個尚未訪問過的鄰接點作為出發(fā)點繼續(xù)作深度優(yōu)先搜索，直到被訪問的頂點其鄰接點均被訪問過為止，這時需要回溯到該頂點訪問前的頂點，繼續(xù)訪問其尚未訪問的鄰接點。這樣不斷回溯，直到回溯到起始點v0，使所有和v0有路徑相通的頂點都被訪問到為止。3.5.3圖的遍歷642）算法描述：以鄰接矩陣作為圖的存儲結(jié)構(gòu)

DFS(A,n,v)

{

visit(v); //訪問頂點v

visited[v]=TRUE;//置已訪問標(biāo)志

for(j=0;j<n;j++)

if(A[v][j]==1&&!visited[j])

DFS(A,n,j);

}3.5.3圖的遍歷6531856942735241(a) (b)圖(a)：v1,v2,v3,v5,v4 v3,v1,v2,v4,v5

v2,v1,v3,v5,v4 v4,v1,v2,v3,v5圖(b)：v1,v2,v3,v6,v5,v7,v8,v4,v9

v9,v4,v1,v2,v3,v6,v5,v7,v8

v3,v1,v2,v4,v9,v6,v5,v7,v8例：662.廣度優(yōu)先搜索(BFS)(類似于樹的層次遍歷) 1）基本思想：訪問了起始點v0之后，首先依次訪問v0的各個鄰接點，然后再依次訪問這些頂點中未被訪問過的鄰接點，以此類推，直到所有被訪問到的頂點的鄰接點都被訪問過為止。 2）算法描述：為了搜索需要，應(yīng)設(shè)置一個循環(huán)隊列，存放已被訪問過的頂點。3.5.3圖的遍歷67

BFS(AdjList,n,v)//以鄰接表作為圖的存儲結(jié)構(gòu)

{

訪問頂點v;visited[v]=TRUE;

front=n-1;rear=0;CQ[rear]=v;

while(rear！=front){front=(front+1)%n;v=CQ[front];

p=AdjList[v].firarc;

while(p！=NULL){if(!visited[p->adjvex]){訪問p->adjvex;visited[p->adjvex]=TRUE;

rear=(rear+1)%n;CQ[rear]=p->adjvex;

}/*endif*/

p=p->nextarc;

}/*endwhile(p!=NULL)*/

}/*endwhile(rear!=front)*/

}3.5.3圖的遍歷68

例：圖(a)：v2,v1,v5,v3,v4,v6

v1,v2,v3,v4,v5,v6圖(b)：v1,v2,v3,v4,v6,v9,v5,v7,v8

v9,v4,v1,v2,v3,v6,v5,v7,v8318569427(a) (b)1364523.5.3圖的遍歷69

例：DFS：v1,

v2,v3,v6,v9,v5,v8,v4,v7BFS：v1,v2,v4,v5,v3,v7,v6,v8,v91364527893.5.3圖的遍歷703.復(fù)雜度分析空間復(fù)雜度：O(n)時間復(fù)雜度： 鄰接表：O(e),e為邊數(shù) 鄰接矩陣：O(n2)3.5.3圖的遍歷71

1.單源最短路徑

1）問題的提出

背景：從一個給定的城市出發(fā)，能否到達其它各城市？走哪條路花費最少？

數(shù)據(jù)結(jié)構(gòu)：用有向網(wǎng)表示，頂點表示城市，弧代表路段，弧上的權(quán)值代表兩城市間的距離或運輸所需的代價。我們稱出發(fā)點為源點，其它點為終點。則問題可描述為：從有向網(wǎng)的源點到其它各終點有否路徑？最短路徑是什么？最短路徑的長度是多少？

3.5.4圖的應(yīng)用72

路徑的三種情況：

①沒有路徑；

②只有一條路徑，即為最短路徑；

③有多條路經(jīng)，存在最短的。12534620101515350203530501045設(shè)頂點v2為源點，則：v2到v6：沒有路徑v2到v1：只有一條，長度35v2到v4：有三條，最短為303.5.4圖的應(yīng)用73

定義：

給定有向圖網(wǎng)G=(V,A)和源點v0,求從v0到G中其余各頂點的最短路徑。125346741412982524510186例：以v6為源點，則各最短路徑為：v6->v1:21(v6->v2->v3->v1)v6->v2:5v6->v3:12(v6->v2->v3)v6->v4:25(v6->v4)v6->v5:無路徑3.5.4圖的應(yīng)用743.5.4圖的應(yīng)用2）算法思想：先找出從源點v0到各終點vk的直達路徑<v0,vk>，從這些路徑中找出一條長度最短的路徑<v0,u>，然后對其余各條路徑進行適當(dāng)調(diào)整：若在圖中存在弧<u,vk>，且<u,vk>和<v0,u>兩條弧上權(quán)之和小于弧<v0,vk>的權(quán)，則以路徑<v0,u,vk>代替<v0,vk>。在調(diào)整后的各條路徑中，再找長度最短的路徑，以此類推。3）過程： ①初始化 設(shè)AS[n][n]為有向網(wǎng)的帶權(quán)鄰接矩陣，AS[i][j]表示弧<vi,vj>上的權(quán)值，若<vi,vj>不存在，則AS[i][j]為∞06∞8∞∞1807∞∞109∞015∞∞∞∞120∞∞∞∞4∞0∞245∞25∞01234561

2345612534674141298252451018675

S:最短路徑的終點集合(初值為{v0}) DIST[n]:各終點當(dāng)前找到的最短路徑的長度 (初始值為DIST[i]=AS[v0][i])②選擇u，使得：3.5.4圖的應(yīng)用76③對于所有不在S中的終點w，若：④重復(fù)操作②、③共n-1次，可求得從v0到各終點的 最短路徑。幾個量的說明：

S[n]：記錄了從源點出發(fā)的最短路徑的終點集合。

DIST[n]：記錄各終點當(dāng)前找到的最短路徑的長度。

PATH[n]：PATH[i]表示從源點到頂點vi之間的最短路徑的前驅(qū)頂點，初始值為源點v0,若不存在，則為空。3.5.4圖的應(yīng)用773.5.4圖的應(yīng)用例：245∞25∞0

DIST[1:6]123456

S

{6}

{6,2}

{6,2,3}

{6,2,3,1}

{6,2,3,1,4}6666

PATH[1:6]123456262663626636266362662351225∞02151225∞

02151225∞

02151225∞

006∞8∞∞1807∞∞109∞015∞∞∞∞120∞∞∞∞4∞0∞

245∞25∞01234561

23456125346741412982524510186則輸出PATH和Distant:6->1:6->2->3->121;6->2:6->25;6->3:6->2->312;6->4:6->425;6->5:無路徑; 6->6:6->60;782.拓撲排序(AOV網(wǎng)，頂點表示活動的有向網(wǎng))1）問題的描述：

用有向圖描述工程的進行過程，子工程稱為活動，在圖中用頂點表示，兩頂點間的弧表示活動間的優(yōu)先關(guān)系，這種有向圖稱為作業(yè)活動網(wǎng)或AOV網(wǎng)。 頂點i到頂點j有路徑，稱i是j的前驅(qū)，j是i的后繼；若從i到j(luò)只有一條弧，則稱i是j的直接前驅(qū)，j是i的直接后繼。3.5.4圖的應(yīng)用79引例：一個軟件專業(yè)學(xué)生學(xué)習(xí)課程C1：程序設(shè)計 先修無C2：離散數(shù)學(xué) C1C3：數(shù)據(jù)結(jié)構(gòu) C1C2C4：匯編語言 C1C5：語言設(shè)計與分析C3C4C1C2C4C5C33.5.4圖的應(yīng)用80拓撲有序序列及拓撲排序

死鎖---在AOV網(wǎng)中不允許存在有向回路，否則某項活動的開工將以自己工作的完成作為先決條件，這種現(xiàn)象稱為死鎖。 拓撲有序序列---若有向圖中沒有回路出現(xiàn)，則可構(gòu)造得到包含有向圖中全部頂點的序列，這種序列稱為拓撲有序序列。 拓撲排序---對AOV網(wǎng)構(gòu)造拓撲有序序列的操作稱為拓撲排序。3.5.4圖的應(yīng)用813.5.4圖的應(yīng)用2）拓撲排序方法： ①在有向圖中選取一個沒有前驅(qū)的頂點(入度為0) 輸出； ②在圖中刪除該頂點和以它為尾的所有弧。 ③Repeat①,②,直到全部頂點輸出。(答案不唯一)12543輸出v62543輸出v1253輸出v425輸出v3拓撲有序序列為：v6v1v4v3v2v5125643初態(tài)5輸出v2輸出v582例：12465314523可能的拓撲：

6->1->4->3->2->5 1->3->2->6->4->5可能的拓撲：

1->2->3->4->5 1->4->2->3->5 1->2->4->3->53.5.4圖的應(yīng)用833）拓撲排序的鄰接表和鏈棧：鄰接表：

4^202^123^0指針入度頂點325^5^45^125643AOV網(wǎng)鏈棧：所有入度為零的頂點構(gòu)成一鏈棧 3.5.4圖的應(yīng)用84操作：①建立一個入度為0的頂點的棧； ②選取一個入度為0的頂點輸出； ③弧頭頂點的入度減1； ④Repeat①～③，直到全部頂點輸出3.5.4圖的應(yīng)用85051234例：5^1

1

3^4^5^V0V1V2V3V4V50202123^^020212初態(tài)010112000111000011000001000000012345下標(biāo)v2出棧v0出棧v1出棧v3出棧v4出棧拓撲排序序列為：

2、0、1、3、4、5改用隊列，則輸出的拓撲序列0,2,1,3,4,5v0/v0v2//v1//v3//v4//v0、v2入棧v5//v2出棧v0出棧v1出棧V3入棧V3出棧V4入棧V4出棧V5入棧V5出棧棧的變化：v1入棧863.關(guān)鍵路徑(以邊表示活動的網(wǎng)：AOE)1）問題描述

AOE網(wǎng)：一個帶權(quán)的有向無環(huán)圖。

頂點vi：表示事件

弧ai：表示活動 權(quán)：表示活動的持續(xù)時間。

源點：一個入度為零的點(工程起點，只有一個)

匯點：一個出度為零的點(工程結(jié)束，只有一個)

研究的問題 ①完成整個工程需要多少時間？ ②哪些活動是影響工程進度的關(guān)鍵？3.5.4圖的應(yīng)用87關(guān)鍵路徑：完成工程的最短時間是從源點到匯點的最長路徑長度，這條最長的路徑稱作關(guān)鍵路徑。事件vj最早發(fā)生時間ve(j)：從ve(1)=0開始向前遞推活動ai由弧<i,j>表示，其持續(xù)時間記為dut(<i,j>),T是所有以j為頭的弧的集合vjviai3.5.4圖的應(yīng)用88事件vj最遲發(fā)生時間vl(j)：從vl(n)=ve(n)

開始向后遞推其中S是所有以j為尾的弧的集合vkvj注意：以上兩個遞推公式的計算必須在拓撲有序和逆拓撲有序的前提下進行，即：ve(j)必須在vj的所有前驅(qū)的最早發(fā)生時間求得之后才能確定，而vl(j)必須在vj的所有后繼的最遲發(fā)生時間之后才能確定。3.5.4圖的應(yīng)用89活動最早開始時間e(i)：

e(i)=ve(j)vjai活動