回溯法與樹(shù)的遍歷及圖

回溯法與樹(shù)的遍歷及圖第1頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第6章樹(shù)和二叉樹(shù)

6.1樹(shù)的定義和基本術(shù)語(yǔ)

6.2二叉樹(shù)

6.3遍歷二叉樹(shù)和線索二叉樹(shù)

6.4樹(shù)和森林

6.5樹(shù)與等價(jià)問(wèn)題

6.6赫夫曼樹(shù)及其應(yīng)用

6.7回溯法與樹(shù)的遍歷

6.8樹(shù)的計(jì)數(shù)第2頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷回溯法(backtracking)，是解決問(wèn)題的一種策略，是窮舉法的一種推廣，一種搜索算法。它在包含問(wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。如右圖：一個(gè)陌生人從甲地到乙地的策略甲乙第3頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷例：求含有n個(gè)元素的集合的冪集。若

A={1,2,3},則其冪集

P(A)={

{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{}

}第4頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷可以用分治法來(lái)設(shè)計(jì)這個(gè)求冪集的遞歸過(guò)程。另一個(gè)角度：

冪集的每個(gè)元素是一個(gè)集合，它或是空集、或含集合A中的一個(gè)元素、或含集合A中的兩個(gè)元素、或等于集合A.

也就是說(shuō)，

集合A中的元素x，對(duì)于冪集的每一個(gè)元素S而言，要么x屬于S，要么x不屬于S。

所以，求冪集的元素的過(guò)程可看成是依次對(duì)集合A中的元素進(jìn)行取舍的過(guò)程。第5頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷1，2，31，21，312，3231，2121可以用一棵二叉樹(shù)來(lái)表示過(guò)程中冪集元素的變化狀況，求冪集的元素的過(guò)程即為先序遍歷這棵狀態(tài)樹(shù)的過(guò)程。第6頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷求冪集元素的過(guò)程即為先序遍歷這棵狀態(tài)樹(shù)的過(guò)程，算法如下：

voidPowerSet(inti,intn){

//求含n個(gè)元素的集合A的冪集，進(jìn)入函數(shù)時(shí)

//已對(duì)A中前i-1個(gè)元素作了取舍處理，現(xiàn)從第i個(gè)元素起

//進(jìn)行取舍處理，若i>n則求得冪集的一個(gè)元素，

//并輸出之。

//初始調(diào)用：PowerSet(1,n)

if(i>n)輸出冪集的一個(gè)元素

else{

取第i個(gè)元素，PowSet(i+1,n)

舍第i個(gè)元素，PowSet(i+1,n)

}

}//PowerSet第7頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷算法求精（用線性表表示集合）如下：

voidGetPowerSet(inti,ListA,List&B){

//線性表A表示集合A，線性表B表示集合冪集的一個(gè)元素

//局部變量k為進(jìn)入函數(shù)時(shí)表B的當(dāng)前長(zhǎng)度，

//第一次調(diào)用本函數(shù)時(shí)，B為空表，i=1 if(i>ListLength(A))Output(B);

else{

GetElem(A,i,x);k=ListLength(B);

ListInsert(B,k+1,x);GetPowSet(i+1,A,B);

ListDelete(B,k+1,x);GetPowSet(i+1,A,B);

}

}//GetPowerSet第8頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷八皇后問(wèn)題：

在國(guó)際象棋中，皇后可以向八個(gè)方向伸展去吃，問(wèn)題是如何把八個(gè)皇后同時(shí)放在棋盤(pán)上，互相不被吃。第9頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷試試看：第10頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷一個(gè)答案：第11頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.7回溯法與樹(shù)的遍歷怎么找？

voidTrial(inti,intn){

//設(shè)nxn棋盤(pán)的前i-1行已放置了

//互不攻擊的i-1個(gè)棋子

if(i>n)輸出棋盤(pán)當(dāng)前布局;

elsefor(j=1;j<=n;++j){

在第i行第j列放置一個(gè)棋子;

if(當(dāng)前布局合法)Trial(i+1,n);

移走第i行第j列的棋子;

}

}//Trial第12頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)具有n個(gè)節(jié)點(diǎn)的不同形態(tài)的樹(shù)（二叉樹(shù)）有多少棵？二叉樹(shù)T和T’相似是指：二者都為空樹(shù)或者都不為空樹(shù)，且它們的左右子樹(shù)分別相似。二叉樹(shù)的計(jì)數(shù)問(wèn)題就是討論具有n個(gè)節(jié)點(diǎn)、互不相似的二叉樹(shù)的數(shù)目bn第13頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)一棵具有n(n>1)個(gè)節(jié)點(diǎn)的二叉樹(shù)可以看成是由一個(gè)根節(jié)點(diǎn)、一棵具有i個(gè)節(jié)點(diǎn)的左子樹(shù)和一棵具有n-i-1個(gè)節(jié)點(diǎn)的右子樹(shù)組成，因此：第14頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)經(jīng)演算可知：第15頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)另一個(gè)角度：

前序（后序）＋中序唯一確定一棵二叉樹(shù)e.g:

前序:A、B、D、E、F、C

中序:D、B、E、F、A、C確定過(guò)程:

1、定根A

2、在中序序列中找到A

3、中序序列中的A的左部為A的左子樹(shù)上的所有結(jié)點(diǎn)，A的右部為A的右子樹(shù)中的所有結(jié)點(diǎn)。

4、根據(jù)A的左子樹(shù)的所有結(jié)點(diǎn)的前序序列確定A的左子樹(shù)的根節(jié)點(diǎn)，它是A的左兒子。

5、根據(jù)A的右子樹(shù)的所有結(jié)點(diǎn)的前序序列確定A的右子樹(shù)的根節(jié)點(diǎn)，它是A的右兒子。

6、在左、右子樹(shù)中反復(fù)以上過(guò)程。至所有結(jié)點(diǎn)處理完畢。結(jié)束前序:A、B、D、E、F、C

中序:D、B、E、F、A、C前序:A、B、D、E、F、C

中序:D、B、E、F、A、CEF前序:B、D、E、F

中序:D、B、E、F前序:E、F

中序:E、FA

CA

D、E、FCBABCD

D、B、E、F第16頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)設(shè)二叉樹(shù)的前序的序列為1、2、3、…、n不同的中序序列對(duì)應(yīng)著不同形態(tài)的二叉樹(shù)不同的中序序列的總數(shù)

=不同形態(tài)二叉樹(shù)總數(shù)不同的中序序列在中序遍歷時(shí)和相應(yīng)的進(jìn)出棧序列一一對(duì)應(yīng)。不同的進(jìn)出棧序列的總數(shù)

=不同形態(tài)的二叉樹(shù)的總數(shù)實(shí)例：e.g:當(dāng)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)n=3 前序序列為1、2、3時(shí)1231231231231231、進(jìn)棧2、進(jìn)棧3、進(jìn)棧3、出棧2、出棧1、出棧1、進(jìn)棧2、進(jìn)棧2、出棧3、進(jìn)棧3、出棧1、出棧1、進(jìn)棧2、進(jìn)棧2、出棧1、出棧3、進(jìn)棧3、出棧1、進(jìn)棧1、出棧2、進(jìn)棧3、進(jìn)棧2、出棧3、出棧1、進(jìn)棧1、出棧2、進(jìn)棧2、出棧3、進(jìn)棧3、出棧第17頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)實(shí)例：e.g:當(dāng)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)n=3 前序序列為1、2、3時(shí)1231231231231231、進(jìn)棧2、進(jìn)棧3、進(jìn)棧3、出棧2、出棧1、出棧1、進(jìn)棧2、進(jìn)棧2、出棧3、進(jìn)棧3、出棧1、出棧1、進(jìn)棧2、進(jìn)棧2、出棧1、出棧3、進(jìn)棧3、出棧1、進(jìn)棧1、出棧2、進(jìn)棧3、進(jìn)棧2、出棧3、出棧1、進(jìn)棧1、出棧2、進(jìn)棧2、出棧3、進(jìn)棧3、出棧進(jìn)出棧序列總數(shù)的計(jì)算為2n個(gè)方格中放置3個(gè)1的組合數(shù)－不合理的序列總數(shù)e.g:n=3時(shí)，6格放置3個(gè)1的序列情況：1代表進(jìn)棧，0表示出棧

111000

110010

110100

101100

101010

000111

100110合理不合理第18頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)這個(gè)數(shù)目為：Thesequencesofnleftandnrightparenthesesthatarenotwellformedcorrespondexactlytoallsequencesofn-1leftparenthesesandn+1rightparentheses(inallpossibleorders).Toprovethiscorrespondence,letusstartwithasequenceofnleftandnrightparenthesesthatisnotwellformed.Letkbethefirstpositioninwhichthesequencegoeswrong,sotheentryatpositionkisarightparenthesis,andthereisonemorerightparenthesisthanleftupthroughthisposition.Hencestrictlytotherightofpositionkthereisonefewerrightparenthesisthanleft.Strictlytotherightofpositionk,then,letusreplaceallleftparenthesesbyrightandallrightparenthesesbyleft.Theresultingsequencewillhaven-1leftparenthesesandn+1rightparenthesesaltogether.Conversely,letusstartwithasequenceofn-1leftparenthesesandn+1rightparentheses,andletkbethefirstpositionwherethenumberofrightparenthesesexceedsthenumberofleft(suchapositionmustexist,sincetherearemorerightthanleftparenthesesaltogether).Againletusexchangeleftforrightandrightforleftparenthesesintheremainderofthesequence(positionsafterk).Wetherebyobtainasequenceofnleftandnrightparenthesesthatisnotwellformed,andwehaveconstructedtheone-to-onecorrespondenceasdesired.第19頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)這個(gè)數(shù)稱為Catalan數(shù)：Cat(n)同時(shí)也是把n+2邊的凸多邊形，連n-1條不相交的對(duì)角線，把這個(gè)凸多邊形分成三角形的不同的方法的數(shù)目。第20頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月

6.8樹(shù)的計(jì)數(shù)由二叉樹(shù)的計(jì)數(shù)可推得樹(shù)的計(jì)數(shù)，由“森林與二叉樹(shù)的轉(zhuǎn)換”中可知一棵樹(shù)可轉(zhuǎn)換成唯一的一棵沒(méi)有右子樹(shù)的二叉樹(shù)，反之亦然。所以具有n個(gè)節(jié)點(diǎn)的不同形態(tài)的樹(shù)的數(shù)目和具有n-1個(gè)節(jié)點(diǎn)的二叉樹(shù)的數(shù)目相同。這里的樹(shù)指的是有序樹(shù)。第21頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第7章圖

7.1圖的定義和術(shù)語(yǔ)

7.2圖的存儲(chǔ)結(jié)構(gòu)

7.3圖的遍歷

7.4圖的連通性問(wèn)題

7.5有向無(wú)環(huán)圖及其應(yīng)用

7.6最短路經(jīng)第22頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月第7章圖離散數(shù)學(xué)中的圖論是專門(mén)研究圖性質(zhì)的一個(gè)數(shù)學(xué)分支，但圖論注重研究圖的純數(shù)學(xué)性質(zhì)，而數(shù)據(jù)結(jié)構(gòu)中對(duì)圖的討論則側(cè)重于在計(jì)算機(jī)中如何表示圖以及如何實(shí)現(xiàn)圖的操作和應(yīng)用等。圖是較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，因此和線性表、樹(shù)不同，雖然在遍歷圖的同時(shí)可以對(duì)頂點(diǎn)或弧進(jìn)行各種操作，但更多圖的應(yīng)用問(wèn)題如求最小生成樹(shù)和最短路徑等在圖論的研究中都早已有了特定算法，在本章中主要是介紹它們?cè)谟?jì)算機(jī)中的具體實(shí)現(xiàn)。第23頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語(yǔ)圖的抽象數(shù)據(jù)類型定義如下：

ADTGraph{

數(shù)據(jù)對(duì)象：

V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。

數(shù)據(jù)關(guān)系：

VR＝{<v,w>|v,w∈V且P(v,w)，<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}第24頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語(yǔ)基本操作P：

{結(jié)構(gòu)初始化}

CreateGraph(&G,V,VR);初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。

{銷毀結(jié)構(gòu)}

DestroyGraph(&G);初始條件：圖G存在。操作結(jié)果：銷毀圖G。

{引用型操作}

LocateVex(G,u);初始條件：圖G存在，u和G中頂點(diǎn)有相同特征。操作結(jié)果：若G中存在和u相同的頂點(diǎn)，則返回該頂點(diǎn)在圖中位置；否則返回其它信息。

GetVex(G,v);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回v的值。

FirstAdjVex(G,v);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回v的第一個(gè)鄰接點(diǎn)。若該頂點(diǎn)在G中沒(méi)有鄰接點(diǎn)，則返回"空"。

NextAdjVex(G,v,w);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。操作結(jié)果：返回v的（相對(duì)于w的）下一個(gè)鄰接點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回"空"。第25頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語(yǔ)……

{加工型操作}

PutVex(&G,v,value);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：對(duì)v賦值value。

InsertVex(&G,v);初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖G中增添新頂點(diǎn)v。

DeleteVex(&G,v);初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的弧。

InsertArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中增添弧<v,w>，若G是無(wú)向的，則還增添對(duì)稱弧<w,v>。

DeleteArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中刪除弧<v,w>，若G是無(wú)向的，則還刪除對(duì)稱弧<w,v>。

DFSTraverse(G,Visit());初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對(duì)圖G進(jìn)行深度優(yōu)先遍歷。遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。

BFSTraverse(G,Visit());初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對(duì)圖G進(jìn)行廣度優(yōu)先遍歷。遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。}ADTGraph第26頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語(yǔ)圖由一個(gè)頂點(diǎn)集和弧集構(gòu)成，通常寫(xiě)作：Graph=(V,VR)。由于空的圖在實(shí)際應(yīng)用中沒(méi)有意義，因此一般不討論空的圖，即V是頂點(diǎn)的有窮非空集合。<v,w>表示從頂點(diǎn)v到頂點(diǎn)w的一條弧，其中頂點(diǎn)v被稱為弧尾，頂點(diǎn)w被稱作弧頭。由于弧是有方向的，故稱有向圖。例如下列定義的有向圖如右圖所示。G1=(V1,VR1)其中：V1={A,B,C,D,E}VR1=

{<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,<D,A>,<E,C>}若<v,w>∈R必有<w,v>∈R，則稱(v,w)為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊。由頂點(diǎn)集和邊集構(gòu)成的圖稱作無(wú)向圖。例如下列定義的無(wú)向圖如右所示。G2=(V2,VR2)其中：V2={A,B,C,D,E,F}VR2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}第27頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語(yǔ)數(shù)學(xué)上的定義：圖（graph）G是一個(gè)序偶<V,E>，

其中

V是一個(gè)非空有限集合，

稱為圖G的點(diǎn)集，

E稱為圖G的弧集。第28頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語(yǔ)幾個(gè)有關(guān)圖的常用術(shù)語(yǔ)頂點(diǎn)的度

對(duì)無(wú)向圖而言，鄰接點(diǎn)的個(gè)數(shù)定義為頂點(diǎn)的度。

對(duì)有向圖而言，頂點(diǎn)的度為其出度和入度之和，其中出度定義為以該頂點(diǎn)為弧尾的弧的個(gè)數(shù)，入度定義為以該頂點(diǎn)為弧頭的弧的個(gè)數(shù)。子圖

假設(shè)有兩個(gè)圖G=(V,E)和G‘=(V’,E‘)，如果V’isasubsetofV且E’isasubsetofE，則稱G‘為G的子圖(subgraph)。路徑和回路

若有向圖G中k+1個(gè)頂點(diǎn)之間都有弧存在（即<v0,v1>,<v1,v2>,…<vk-1,vk>都是圖G中的弧），則這個(gè)頂點(diǎn)的序列{v0,v1,…,vk}為從頂點(diǎn)v0到頂點(diǎn)vk的一條有向路徑，路徑中弧的數(shù)目定義為路徑長(zhǎng)度，若序列中的頂點(diǎn)都不相同，則為簡(jiǎn)單路徑。對(duì)無(wú)向圖，相鄰頂點(diǎn)之間存在邊的k+1個(gè)頂點(diǎn)序列構(gòu)成一條長(zhǎng)度為k的無(wú)向路徑。如果v0和vk是同一個(gè)頂點(diǎn)，則是一條由某個(gè)頂點(diǎn)出發(fā)又回到自身的路徑，稱這種路徑為回路或環(huán)。第29頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語(yǔ)幾個(gè)有關(guān)圖的常用術(shù)語(yǔ)連通圖和連通分量、強(qiáng)連通圖和強(qiáng)連通分量

若無(wú)向圖中任意兩個(gè)頂點(diǎn)之間都存在一條無(wú)向路徑，則稱該無(wú)向圖為連通圖，否則稱為非連通圖。若有向圖中任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱該有向圖為強(qiáng)連通圖。

非連通圖中各個(gè)極大連通子圖稱作該圖的連通分量。非強(qiáng)連通的有向圖中的極大強(qiáng)連通子圖稱作有向圖的強(qiáng)連通分量。生成樹(shù)和生成森林

一個(gè)含n個(gè)頂點(diǎn)的連通圖的生成樹(shù)是該圖中的一個(gè)極小連通子圖，它包含圖中n個(gè)頂點(diǎn)和足以構(gòu)成一棵樹(shù)的n-1條邊。對(duì)于非連通圖，對(duì)其每個(gè)連通分量可以構(gòu)造一棵生成樹(shù)，合成起來(lái)就是一個(gè)生成森林。無(wú)向網(wǎng)和有向網(wǎng)

在實(shí)際應(yīng)用中，圖的弧或邊往往與具有一定意義的數(shù)相關(guān)，稱這些數(shù)為"權(quán)"，分別稱帶權(quán)的有向圖和無(wú)向圖為有向網(wǎng)和無(wú)向網(wǎng)。第30頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2圖的存儲(chǔ)結(jié)構(gòu)7.2.1數(shù)組表示法（鄰接矩陣）7.2.2鄰接表7.2.3十字鏈表7.2.4鄰接多重表第31頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.1數(shù)組表示法假設(shè)圖中頂點(diǎn)數(shù)為n，則鄰接矩陣A=(ai,j)定義為

ai,j=1若vi和vj有弧或邊存在

ai,j=0否則網(wǎng)的鄰接矩陣的定義為，當(dāng)vi到vj有弧相鄰接時(shí)，ai,j的值應(yīng)為該弧上的權(quán)值，否則為∞。將圖的頂點(diǎn)信息存儲(chǔ)在一個(gè)一維數(shù)組中，并將它的鄰接矩陣存儲(chǔ)在一個(gè)二維數(shù)組中即構(gòu)成圖的數(shù)組表示。第32頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.1數(shù)組表示法圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示

constINFINITY=INT_MAX;

//最大值∞

constMAX_VERTEX_NUM=20;

//最大頂點(diǎn)個(gè)數(shù)

typedefenum{DG,DN,AG,AN}GraphKind;

//類型標(biāo)志{有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)}

typedefstructArcCell{

//弧的定義

VRTypeadj;

//VRType是頂點(diǎn)關(guān)系類型。

//對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。

InfoType*info;

//該弧相關(guān)信息的指針

}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct{

//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)信息

AdjMatrixarcs;

//表示頂點(diǎn)之間關(guān)系的二維數(shù)組

intvexnum,arcnum;

//圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)

GraphKindkind;

//圖的種類標(biāo)志

}MGraph;第33頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.1數(shù)組表示法無(wú)向圖的數(shù)組表示存儲(chǔ)結(jié)構(gòu)有向圖的數(shù)組表示存儲(chǔ)結(jié)構(gòu)第34頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.2鄰接表類似于樹(shù)的孩子鏈表，將和同一頂點(diǎn)"相鄰接"的所有鄰接點(diǎn)鏈接在一個(gè)單鏈表中，單鏈表的頭指針則和頂點(diǎn)信息一起存儲(chǔ)在一個(gè)一維數(shù)組中。第35頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.2鄰接表圖的鄰接表存儲(chǔ)表示

constMAX_VERTEX_NUM=20;

typedefstructArcNode__{

//弧結(jié)點(diǎn)的結(jié)構(gòu)

intadjvex;

//該弧所指向的頂點(diǎn)的位置

structArcNode__*nextarc;

//指向下一條弧的指針

VRTypeweight;

//與弧相關(guān)的權(quán)值，無(wú)權(quán)則為0

InfoType*info;

//指向該弧相關(guān)信息的指針

}ArcNode;

typedefstructVNode{

//頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)

VertexTypedata;

//頂點(diǎn)信息

ArcNode*firstarc;

//指向第一條依附該頂點(diǎn)的弧

}AdjList[MAX_VERTEX_NUM];

typedefstruct{

//圖的鄰接表結(jié)構(gòu)定義

AdjListvertices;

//頂點(diǎn)數(shù)組

intvexnum,arcnum;

//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)

GraphKindkind;

//圖的種類標(biāo)志

}ALGraph;第36頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.2鄰接表有向圖的鄰接表中鏈接在每個(gè)頂點(diǎn)結(jié)點(diǎn)中的都是以該頂點(diǎn)為弧尾的弧，每個(gè)單鏈表中的弧結(jié)點(diǎn)的個(gè)數(shù)恰為弧尾頂點(diǎn)的出度，每一條弧在鄰接表中只出現(xiàn)一次。雖然在鄰接表中也能找到所有以某個(gè)頂點(diǎn)為弧頭的弧，但必須查詢整個(gè)鄰接表。若在應(yīng)用問(wèn)題中主要是對(duì)以某個(gè)頂點(diǎn)為弧頭的弧進(jìn)行操作，則可以為該有向圖建立一個(gè)"逆鄰接表"。第37頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.3十字鏈表十字鏈表是有向圖的另一種存儲(chǔ)結(jié)構(gòu)，目的是將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)點(diǎn)表示，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。第38頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.3十字鏈表7.2.1中的有向圖的十字鏈表如下所示第39頁(yè)，課件共43頁(yè)，創(chuàng)作于2023年2月7.2.3十字鏈表有向圖的十字鏈表存儲(chǔ)表示

constMAX_VERTEX_NUM=20;

typedefstructArcBox{

//弧結(jié)點(diǎn)結(jié)構(gòu)定義

inttailvex,headvex;

//該弧的尾和頭頂點(diǎn)的位置

structArcBox*hlink,*tlink;//分別為弧頭相同和弧尾相同的弧的鏈域

VRTypeweight;

//與