回溯法與樹的遍歷及圖

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

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

6.2二叉樹

6.3遍歷二叉樹和線索二叉樹

6.4樹和森林

6.5樹與等價(jià)問題

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

6.7回溯法與樹的遍歷

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

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

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

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

P(A)={

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

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

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

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

也就是說，

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

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

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

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

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頁，課件共43頁，創(chuàng)作于2023年2月

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

voidGetPowerSet(inti,ListA,List&B){

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

//局部變量k為進(jìn)入函數(shù)時(shí)表B的當(dā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頁，課件共43頁，創(chuàng)作于2023年2月

6.7回溯法與樹的遍歷八皇后問題：

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

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

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

6.7回溯法與樹的遍歷怎么找？

voidTrial(inti,intn){

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

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

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

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

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

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

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

}

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

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

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

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

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

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

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

中序:D、B、E、F、A、C確定過程:

1、定根A

2、在中序序列中找到A

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

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

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

6、在左、右子樹中反復(fù)以上過程。至所有結(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頁，課件共43頁，創(chuàng)作于2023年2月

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

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

=不同形態(tài)的二叉樹的總數(shù)實(shí)例：e.g:當(dāng)二叉樹的結(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頁，課件共43頁，創(chuàng)作于2023年2月

6.8樹的計(jì)數(shù)實(shí)例：e.g:當(dāng)二叉樹的結(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頁，課件共43頁，創(chuàng)作于2023年2月

6.8樹的計(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頁，課件共43頁，創(chuàng)作于2023年2月

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

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

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

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

7.3圖的遍歷

7.4圖的連通性問題

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

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

{加工型操作}

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是無向的，則還增添對(duì)稱弧<w,v>。

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

DFSTraverse(G,Visit());初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對(duì)圖G進(jìn)行深度優(yōu)先遍歷。遍歷過程中對(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)先遍歷。遍歷過程中對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，則操作失敗。}ADTGraph第26頁，課件共43頁，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語圖由一個(gè)頂點(diǎn)集和弧集構(gòu)成，通常寫作：Graph=(V,VR)。由于空的圖在實(shí)際應(yīng)用中沒有意義，因此一般不討論空的圖，即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)成的圖稱作無向圖。例如下列定義的無向圖如右所示。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頁，課件共43頁，創(chuàng)作于2023年2月7.1圖的定義和術(shù)語數(shù)學(xué)上的定義：圖（graph）G是一個(gè)序偶<V,E>，

其中

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

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

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

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

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

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

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

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

typedefstructArcCell{

//弧的定義

VRTypeadj;

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

//對(duì)無權(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頁，課件共43頁，創(chuàng)作于2023年2月7.2.1數(shù)組表示法無向圖的數(shù)組表示存儲(chǔ)結(jié)構(gòu)有向圖的數(shù)組表示存儲(chǔ)結(jié)構(gòu)第34頁，課件共43頁，創(chuàng)作于2023年2月7.2.2鄰接表類似于樹的孩子鏈表，將和同一頂點(diǎn)"相鄰接"的所有鄰接點(diǎn)鏈接在一個(gè)單鏈表中，單鏈表的頭指針則和頂點(diǎn)信息一起存儲(chǔ)在一個(gè)一維數(shù)組中。第35頁，課件共43頁，創(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)值，無權(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頁，課件共43頁，創(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)用問題中主要是對(duì)以某個(gè)頂點(diǎn)為弧頭的弧進(jìn)行操作，則可以為該有向圖建立一個(gè)"逆鄰接表"。第37頁，課件共43頁，創(chuàng)作于2023年2月7.2.3十字鏈表十字鏈表是有向圖的另一種存儲(chǔ)結(jié)構(gòu)，目的是將在有向圖的鄰接表和逆鄰接表中兩次出現(xiàn)的同一條弧用一個(gè)結(jié)點(diǎn)表示，由于在鄰接表和逆鄰接表中的頂點(diǎn)數(shù)據(jù)是相同的，則在十字鏈表中只需要出現(xiàn)一次，但需保留分別指向第一條"出弧"和第一條"入弧"的指針。第38頁，課件共43頁，創(chuàng)作于2023年2月7.2.3十字鏈表7.2.1中的有向圖的十字鏈表如下所示第39頁，課件共43頁，創(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;

//與