數(shù)據(jù)結(jié)構(gòu)圖結(jié)構(gòu)動(dòng)態(tài)演示文稿

數(shù)據(jù)結(jié)構(gòu)圖結(jié)構(gòu)動(dòng)態(tài)演示文稿當(dāng)前1頁(yè)，總共140頁(yè)。數(shù)據(jù)結(jié)構(gòu)圖結(jié)構(gòu)動(dòng)態(tài)當(dāng)前2頁(yè)，總共140頁(yè)。

圖（Graph）是一種較線性表和樹(shù)更為復(fù)雜的非線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是線性關(guān)系，除開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)直接前趨和直接后繼。在樹(shù)形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系實(shí)質(zhì)上是層次關(guān)系，同層上的每個(gè)結(jié)點(diǎn)可以和下一層的零個(gè)或多個(gè)結(jié)點(diǎn)（即孩子）相關(guān)，但只能和上一層的一個(gè)結(jié)點(diǎn)（即雙親）相關(guān)（根結(jié)點(diǎn)除外）。然而在圖形結(jié)構(gòu)中，對(duì)結(jié)點(diǎn)（圖中常稱為頂點(diǎn)）的前趨和后繼個(gè)數(shù)都是不加限制的，即結(jié)點(diǎn)之間的關(guān)系是任意的。圖中任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)。圖的應(yīng)用極為廣泛，特別是近年來(lái)的迅速發(fā)展，已滲透到諸如語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。

當(dāng)前3頁(yè)，總共140頁(yè)。

7.1圖的定義

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

7.3圖的遍歷

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

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

7.6最短路徑

第七章圖當(dāng)前4頁(yè)，總共140頁(yè)。

圖定義

圖G由兩個(gè)集合V和E組成，記為G=(V,E)

其中，V是頂點(diǎn)的有窮非空集合，

E是V中頂點(diǎn)偶對(duì)的有窮集，這些頂點(diǎn)偶對(duì)稱為邊。通常V(G)和E(G)分別稱為圖的頂點(diǎn)集合和邊集合。注：E(G)可以為空集。7.1圖的定義和術(shù)語(yǔ)當(dāng)前5頁(yè)，總共140頁(yè)。7.1圖的定義和術(shù)語(yǔ)圖的數(shù)據(jù)結(jié)構(gòu)的形式化定義（p156）

G=(V,E)

其中V={x|xdataobject}

E={VR}VR={<x,y>|p(x,y)(x,yV)}VR是兩頂點(diǎn)間的關(guān)系的集合，即邊的集合。當(dāng)前6頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)有向圖:

對(duì)一個(gè)圖G，若邊集E(G)為有向邊的集合，則稱該圖為有向圖。①②③④G1G1=（V，E）V={v1,v2,v3,v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}其中<x,y>表示從x到y(tǒng)的一條?。╝rc），A為弧集合，x為弧尾（tail），y為弧頭（head)x弧尾y弧頭當(dāng)前7頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)無(wú)向圖:

對(duì)一個(gè)圖G，若邊集E(G)為無(wú)向邊的集合，則稱該圖為無(wú)向圖。

①②G2③④⑤

G2=（V，E）V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v3),(v2,v3),(v3,v4),(v2,v5),(v3,v5)}其中，(x,y)表示x與y之間的一條連線，稱為邊（edge）當(dāng)前8頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)設(shè)n為頂點(diǎn)數(shù)，e為邊或弧的條數(shù)

對(duì)無(wú)向圖有：0≤e≤

n(n-1)/2

有向圖有：0≤e≤n(n-1)證明：對(duì)有向圖，每個(gè)頂點(diǎn)至多有n-1條邊與其它的n-1個(gè)頂點(diǎn)相連，則n個(gè)頂點(diǎn)至多有n(n-1)條邊。但對(duì)無(wú)向圖，每條邊連接2個(gè)頂點(diǎn)，故最多為n(n-1)/2

當(dāng)前9頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)端點(diǎn)和鄰接點(diǎn)

在一個(gè)無(wú)向圖中，若存在一條邊<vi,vj>,則稱vi，vj為該邊的兩個(gè)端點(diǎn)，并稱它們互為鄰結(jié)點(diǎn)。

21453G2當(dāng)前10頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)起點(diǎn)和終點(diǎn)

在一個(gè)有向圖中，若存在一條邊<vi,vj>,則稱該邊是頂點(diǎn)vi的一條出邊，是vj的一條入邊，稱vi是起始端點(diǎn)（或起點(diǎn)），稱vj是終止端點(diǎn)（或終點(diǎn)）,并稱它們互為鄰結(jié)點(diǎn).2134G1當(dāng)前11頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)度

圖中每個(gè)頂點(diǎn)的度是以該頂點(diǎn)為一端點(diǎn)的邊的數(shù)目。記為D(V)。入度和出度

對(duì)于有向圖，入度為以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目，出度為以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目。例D(v1)=3

無(wú)向圖的度數(shù)為依附于頂點(diǎn)v的邊數(shù)；有向圖的度數(shù)等于以頂點(diǎn)v為弧頭的弧數(shù)與以頂點(diǎn)v為弧尾的弧數(shù)之和21453G22134G1例D(v1)=2

當(dāng)前12頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)子圖

設(shè)有兩個(gè)圖G=（V，E）

G’=（V’，E’）中，若V’是V的子集，E’是E的子集，則稱G’是G子圖。①①④①③④⑤

①②③④⑤

①②G2③④⑤

當(dāng)前13頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)簡(jiǎn)單圖

對(duì)不含多重邊和自環(huán)的圖。2145321453簡(jiǎn)單圖非簡(jiǎn)單圖當(dāng)前14頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)完全圖

邊達(dá)到最大的圖無(wú)向完全圖：具有n(n-1)/2條邊的簡(jiǎn)單圖稱為無(wú)向完全圖有向完全圖：具有n(n-1)條邊的有向圖。稀疏圖：

邊或弧很少的圖。稠密圖：

邊或弧很多的圖。

權(quán)：與圖的邊或弧相關(guān)的數(shù)。

網(wǎng)：邊或弧上帶有權(quán)值的圖。當(dāng)前15頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)路徑

非空有限點(diǎn)、弧交替序列，

W=v0,a1,v1,…,ak,vk

使得i=1,2,…k,

弧ai的頭vi,尾為vi-1

。

路徑長(zhǎng)度：路徑上邊或弧的數(shù)目當(dāng)前16頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)簡(jiǎn)單路徑：除首尾兩點(diǎn)外，其他各點(diǎn)都不相同的路徑稱為簡(jiǎn)單路徑。簡(jiǎn)單路徑當(dāng)前17頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)回路:無(wú)重復(fù)邊的閉路徑。環(huán)：閉的簡(jiǎn)單路徑，稱為環(huán)。回路但不是環(huán)環(huán)當(dāng)前18頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)連通圖：任何兩點(diǎn)都有路徑的圖。

無(wú)向圖：若圖中任意兩個(gè)頂點(diǎn)vi,vj都是連通

的，則稱該圖是連通圖(vi<>vj)

有向圖：若圖中任意兩個(gè)頂點(diǎn)vi,vj，都存在

從vi到vj和從vj到vi的路徑，則稱

該有向圖為強(qiáng)連通圖

(vi<>vj)當(dāng)前19頁(yè)，總共140頁(yè)。圖的術(shù)語(yǔ)連通分量：

無(wú)向圖：無(wú)向圖中極大連通子圖，稱為

連通分量

有向圖：有向圖中極大強(qiáng)連通子圖，稱為

強(qiáng)連通分量當(dāng)前20頁(yè)，總共140頁(yè)。生成樹(shù)圖的術(shù)語(yǔ)生成樹(shù)

一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的n-1條邊。

①②④⑤

①②④⑤

①②④⑤

①②④⑤

有向樹(shù)

如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹(shù)。

當(dāng)前21頁(yè)，總共140頁(yè)。生成樹(shù)、生成森林生成樹(shù)一個(gè)連通圖的生成樹(shù)是它的極小連通子圖，在n個(gè)頂點(diǎn)的情形下，有n-1條邊。生成樹(shù)是對(duì)連通圖而言的是連通圖的極小連通子圖包含圖中的所有頂點(diǎn)有且僅有n-1條邊

非連通圖的生成樹(shù)則組成一個(gè)生成森林。若圖中有n個(gè)頂點(diǎn)，m個(gè)連通分量，則生成森林中有n-m條邊。

一個(gè)有向圖的生成森林由若干棵有向樹(shù)組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹(shù)的弧。當(dāng)前22頁(yè)，總共140頁(yè)。圖有兩種存儲(chǔ)結(jié)構(gòu)

鄰接矩陣鄰接表7.2圖的存儲(chǔ)結(jié)構(gòu)當(dāng)前23頁(yè)，總共140頁(yè)。7.2.1鄰接矩陣鄰接矩陣(AdjacencyMatrix)是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G＝(V，E)是具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣。7.2圖的存儲(chǔ)結(jié)構(gòu)

無(wú)向圖的鄰接矩陣是以主對(duì)角線對(duì)稱的，有向圖的鄰接矩陣可能是不對(duì)稱的。在有向圖中：第i

行1的個(gè)數(shù)就是頂點(diǎn)i

的出度，第j列1的個(gè)數(shù)就是頂點(diǎn)j

的入度。在無(wú)向圖中,第i

行(列)1的個(gè)數(shù)就是頂點(diǎn)i

的度。當(dāng)前24頁(yè)，總共140頁(yè)。一、鄰接矩陣（用二維數(shù)組表示）例如：G1的鄰接矩陣?yán)纾篏2的鄰接矩陣無(wú)向圖的鄰接矩陣為對(duì)稱矩陣G212345G11234當(dāng)前25頁(yè)，總共140頁(yè)。

對(duì)于無(wú)向圖，（vi，vj）和（vj，vi）表示同一條邊，因此，在鄰接矩陣中Aij=Aji。無(wú)向圖的鄰接矩陣是（關(guān)于主對(duì)角線）對(duì)稱矩陣，可用主對(duì)角線以上（或以下）的部分表示。對(duì)有向圖，弧<vi，vj>和<vj，vi>表示方向不同的兩條弧，Aij和Aji表示不同的弧，所以有向圖的鄰接矩陣一般不具有對(duì)稱性。

鄰接矩陣表示法適合于以頂點(diǎn)為主的運(yùn)算。

當(dāng)前26頁(yè)，總共140頁(yè)。

對(duì)于有向圖，頂點(diǎn)vi的出度OD(vi)等于鄰接矩陣第i行元素之和；頂點(diǎn)vi的入度ID(vi)等于鄰接矩陣第i列元素之和，即：

對(duì)于無(wú)向圖，頂點(diǎn)vi的度等于鄰接矩陣第i行的元素之和，即：

OD(vi)=

ID(vi)=

TD（vi）=當(dāng)前27頁(yè)，總共140頁(yè)。若G是網(wǎng)（有權(quán)圖），鄰接矩陣定義為V2V1V3V435214如圖：

Wij若<vi,vj>

或<vj,vi>

∈E(G)A[i，j]=

0或若其它V1V2V3V4V1V2V3V4當(dāng)前28頁(yè)，總共140頁(yè)。

頂點(diǎn)表:一個(gè)記錄各個(gè)頂點(diǎn)信息的一維數(shù)組，

鄰接矩陣：一個(gè)表示各個(gè)頂點(diǎn)之間的關(guān)系（邊或?。┑亩S數(shù)組。

使用鄰接矩陣存儲(chǔ)結(jié)構(gòu)，可用一維數(shù)組表示圖的頂點(diǎn)集合，用二維數(shù)組表示圖的頂點(diǎn)之間關(guān)系（邊或弧）的集合，數(shù)據(jù)類型定義如下：

#defineMAX_VERTEX_NUM20//最大頂點(diǎn)數(shù)typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣類型typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)表

AdjMatrixarcs;//鄰接矩陣

intvexnum，arcnum;//圖的頂點(diǎn)數(shù)和弧數(shù)}MGraph;

由于一般圖的邊或弧較少，其鄰接矩陣的非零元素較少，屬稀疏矩陣，因此會(huì)造成一定存儲(chǔ)空間的浪費(fèi)。

當(dāng)前29頁(yè)，總共140頁(yè)。

鄰接表

圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1)為每個(gè)頂點(diǎn)建立一個(gè)單鏈表，2)第i個(gè)單鏈表中包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。

鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。類似于樹(shù)的孩子鏈表表示法。在鄰接表中為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，用單鏈表中的一個(gè)結(jié)點(diǎn)表示依附于該頂點(diǎn)的一條邊（或表示以該頂點(diǎn)為弧尾的一條?。?，稱為邊（或?。┙Y(jié)點(diǎn)。

當(dāng)前30頁(yè)，總共140頁(yè)。25341543533412212123451.無(wú)向圖鄰接表G212345adjvexnextarcvexdatafirstarc當(dāng)前31頁(yè)，總共140頁(yè)。2.有向圖鄰接表234143121234如圖G1的鄰接表為：G11234當(dāng)前32頁(yè)，總共140頁(yè)。

在鄰接表的邊鏈表中，各個(gè)邊結(jié)點(diǎn)的鏈入順序任意，視邊結(jié)點(diǎn)輸入次序而定。設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則用鄰接表表示無(wú)向圖時(shí)，需要n個(gè)頂點(diǎn)結(jié)點(diǎn)，2e個(gè)邊結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需n個(gè)頂點(diǎn)結(jié)點(diǎn)，e個(gè)邊結(jié)點(diǎn)。建立鄰接表的時(shí)間復(fù)雜度為O(n*e)。若頂點(diǎn)信息即為頂點(diǎn)的下標(biāo)，則時(shí)間復(fù)雜度為O(n+e)。當(dāng)前33頁(yè)，總共140頁(yè)。存儲(chǔ)表示typedefstructArcNode{ intadjvex;//該弧所指向的頂點(diǎn)的位置

structArcNode*nextarc;//指向下一條弧的指針

int*

info;//該弧相關(guān)信息的指針}ArcNode;//邊結(jié)點(diǎn)類型typedefstructVNode{ VertexTypedata;//頂點(diǎn)信息

ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[MAX_VERTEX_NUM];//鄰接表typedefstruct{ AdjListvertices;intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)

intkind;

//圖的種類標(biāo)志}ALGraph;當(dāng)前34頁(yè)，總共140頁(yè)。25341543533412212123451.無(wú)向圖鄰接表二、鄰接表G212345adjvexnextarcvexdatafirstarc當(dāng)前35頁(yè)，總共140頁(yè)。1.無(wú)向圖鄰接表對(duì)圖中每個(gè)頂點(diǎn)Vi建立一個(gè)單鏈表，鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊，每個(gè)鏈表結(jié)點(diǎn)為兩個(gè)域.其中：鄰接點(diǎn)域（adjvex）記載與頂點(diǎn)Vi鄰接的頂點(diǎn)信息；鏈域（nextarc）指向下一個(gè)與頂點(diǎn)Vi鄰接的鏈表p結(jié)點(diǎn)每個(gè)鏈表設(shè)一個(gè)頭結(jié)點(diǎn)，

頭結(jié)點(diǎn)結(jié)構(gòu)為：其中：vexdata存放頂點(diǎn)信息（姓名、編號(hào)等）；

firstarc指向鏈表的第一個(gè)結(jié)點(diǎn)。二、鄰接表adjvexnextarcvexdatafirstarc當(dāng)前36頁(yè)，總共140頁(yè)。二、鄰接表（adjacencylist）如圖G2的鄰接表為：2534154353341221212345G212345當(dāng)前37頁(yè)，總共140頁(yè)。BACDFE例20A141B0452C353D254E015F123當(dāng)前38頁(yè)，總共140頁(yè)。2.有向圖鄰接表234143121234特點(diǎn)：1.n個(gè)頂點(diǎn)，e條弧的有向圖，需n個(gè)表頭結(jié)點(diǎn)，e個(gè)表結(jié)點(diǎn)

2.第i條鏈表上的結(jié)點(diǎn)數(shù)，為Vi的出度（求頂點(diǎn)的出度易，求入度難）如圖G1的鄰接表為：G11234當(dāng)前39頁(yè)，總共140頁(yè)。142301201234

ABCDE2.有向圖的鄰接表ABECF可見(jiàn)，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。當(dāng)前40頁(yè)，總共140頁(yè)。3.有向圖逆鄰接表123411431234此時(shí)，第i條鏈表上的結(jié)點(diǎn)數(shù)，為Vi的入度如圖G1的逆鄰接表為：①②③④G1當(dāng)前41頁(yè)，總共140頁(yè)。ABECD有向圖的逆鄰接表ABCDE30342001234在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。在有向圖的鄰接表中，第i

個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)Vi的出度。在有向圖的逆鄰接表中，第i

個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)Vi

的入度。當(dāng)前42頁(yè)，總共140頁(yè)。4.帶權(quán)有向圖的鄰接表鏈表中每個(gè)結(jié)點(diǎn)為三個(gè)域.

鄰接點(diǎn)權(quán)帶權(quán)圖的邊結(jié)點(diǎn)中info保存該邊上的權(quán)值。當(dāng)前43頁(yè)，總共140頁(yè)。ABECD4.帶權(quán)有向圖的鄰接表ABCDE0123411037^04

4223^28^102254837125^頂點(diǎn)Vi的邊鏈表的頭結(jié)點(diǎn)存放在下標(biāo)為i的頂點(diǎn)數(shù)組中。當(dāng)前44頁(yè)，總共140頁(yè)。

十字鏈表

十字鏈表(OrthogonalList)是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

可看作是將有向圖的鄰接表和逆鄰接表結(jié)合的一種鏈表。

在十字鏈表中，為每個(gè)頂點(diǎn)vi設(shè)置一個(gè)結(jié)點(diǎn)，它包含數(shù)據(jù)域data和兩個(gè)鏈域firstout、firstin，稱為頂點(diǎn)結(jié)點(diǎn)。數(shù)據(jù)域data用于存放頂點(diǎn)vi的有關(guān)信息；鏈域firstin指向以頂點(diǎn)vi為弧頭的第一個(gè)弧結(jié)點(diǎn)；鏈域firstout指向以頂點(diǎn)vi為弧尾的第一個(gè)弧結(jié)點(diǎn)。

弧結(jié)點(diǎn)包括四個(gè)域：尾域tailvex、頭域headvex，鏈域hlink和tlink。

hlink指向弧頭相同的下一條弧，tlink指向弧尾相同的下一條??；data頂點(diǎn)信息，firstin以該頂點(diǎn)為頭的第一個(gè)弧結(jié)點(diǎn)，firstout以該結(jié)點(diǎn)為尾的第一個(gè)弧結(jié)點(diǎn)。

起點(diǎn)vi終點(diǎn)vjhlinktlink弧結(jié)構(gòu)頂點(diǎn)結(jié)構(gòu)

datafirstinfirstout當(dāng)前45頁(yè)，總共140頁(yè)。圖7-8十字鏈表

圖7-8為圖7-6(a)有向圖的十字鏈表。見(jiàn)右圖

采用十字鏈表表示有向圖，很容易找到以頂點(diǎn)vi為弧尾的弧和以頂點(diǎn)vi為弧頭的弧，因此頂點(diǎn)的出度、入度都很容易求得。

當(dāng)前46頁(yè)，總共140頁(yè)。十字鏈表的數(shù)據(jù)類型定義如下：

#defineMAXV<最大頂點(diǎn)個(gè)數(shù)>typedefstructArcbox//弧結(jié)點(diǎn){inttailvex,headvex;//弧尾和弧頭頂點(diǎn)位置

structArcNode*hlink,*tlink;//弧頭相同和弧尾相同的弧的鏈域}ArcBox;typedefstructVexNode//頂點(diǎn)結(jié)點(diǎn){VertexTypedata;//頂點(diǎn)信息

ArcNode*firstin,*firstout;//分別指向該頂點(diǎn)的第一條入弧和出弧}VexNode;當(dāng)前47頁(yè)，總共140頁(yè)。7.2.4鄰接多重表

鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接多重表中設(shè)置一個(gè)邊結(jié)點(diǎn)表示圖中的一條邊。邊結(jié)點(diǎn)包含五個(gè)域，結(jié)構(gòu)如下所示：

其中:mark域

標(biāo)志域，用于對(duì)該邊進(jìn)行標(biāo)記；

ivex域

存放該邊依附的一個(gè)頂點(diǎn)vi的位置信息；

ilink域

該鏈域指向依附于頂點(diǎn)vi的另一條邊的邊結(jié)點(diǎn)；

jvex域

存放該邊依附的另一個(gè)頂點(diǎn)vj的位置信息；

jlink域

該鏈域指向依附于頂點(diǎn)vj的另一條邊的邊結(jié)點(diǎn)。鄰接多重表為每個(gè)頂點(diǎn)設(shè)置一個(gè)結(jié)點(diǎn)，其結(jié)構(gòu)如下：

當(dāng)前48頁(yè)，總共140頁(yè)。圖7-9鄰接多重表

圖7-9為圖7-5(a)無(wú)向圖的鄰接多重表。

由鄰接多重表可以看出，表示邊（vi，vj）的邊結(jié)點(diǎn)通過(guò)鏈域ilink和jlink鏈入了頂點(diǎn)vi和頂點(diǎn)vj的兩個(gè)鏈表中，實(shí)現(xiàn)了用一個(gè)邊結(jié)點(diǎn)表示一個(gè)邊的目的，克服了在鄰接表中用兩個(gè)邊結(jié)點(diǎn)表示一個(gè)邊的缺點(diǎn)。因此鄰接多重表是無(wú)向圖的一種很有效的存儲(chǔ)結(jié)構(gòu)。

當(dāng)前49頁(yè)，總共140頁(yè)。鄰接多重表的結(jié)點(diǎn)數(shù)據(jù)類型定義如下：

#defineMAXV<最大頂點(diǎn)個(gè)數(shù)>typedefstruct//邊結(jié)點(diǎn)類型{intmark;//訪問(wèn)標(biāo)識(shí)

intivex,jvex;//該邊的兩個(gè)頂點(diǎn)位置信息

structEnode*ilink,*jlink;//分別指向依附這兩個(gè)頂點(diǎn)的下一條邊}Enode;typedefstruct//頂點(diǎn)結(jié)點(diǎn)類型{VertexTypedata;//頂點(diǎn)數(shù)據(jù)域

ENode*firstedge;//指向第一條依附該頂點(diǎn)的邊}Vnode;

當(dāng)前50頁(yè)，總共140頁(yè)。7.3圖的遍歷

和樹(shù)的遍歷相似，若從圖中某頂點(diǎn)出發(fā)訪遍圖中每個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)僅訪問(wèn)一次，此過(guò)程稱為圖的遍歷。(TraversingGraph)。

圖的遍歷遠(yuǎn)比樹(shù)的遍歷復(fù)雜。因?yàn)閺臉?shù)根到達(dá)樹(shù)的某個(gè)結(jié)點(diǎn)只有一條路徑，而圖的兩個(gè)頂點(diǎn)之間可能有多條路徑。

因此，在圖的遍歷過(guò)程中，可能會(huì)出現(xiàn)下面的現(xiàn)象，即在順著一條路徑訪問(wèn)了某個(gè)頂點(diǎn)后，可能會(huì)沿著另一條路徑又回到該頂點(diǎn)。

為避免一個(gè)頂點(diǎn)被多次訪問(wèn)，我們?cè)O(shè)置一個(gè)標(biāo)志數(shù)組

intvisited[MAX_VERTEX_NUM];它的元素初值為0。一旦vi被訪問(wèn)了，便置相應(yīng)數(shù)組元素為1.

圖的遍歷方法有：這兩種方法對(duì)無(wú)向圖和有向圖都適用。

深度優(yōu)先搜索遍歷（簡(jiǎn)稱DFS）廣度優(yōu)先搜索遍歷（簡(jiǎn)稱BFS）當(dāng)前51頁(yè)，總共140頁(yè)。

深度優(yōu)先搜索（DFS）1．深度優(yōu)先搜索遍歷過(guò)程：

DFS在訪問(wèn)圖中某一起始頂點(diǎn)v后，由

v出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn)w1；再?gòu)膚1出發(fā)，訪問(wèn)與w1鄰接但還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)w2；然后再?gòu)膚2出發(fā)，進(jìn)行類似的訪問(wèn)，…如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)u為止。

接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接頂點(diǎn)。如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問(wèn)；如果沒(méi)有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。當(dāng)前52頁(yè)，總共140頁(yè)。

深度優(yōu)先搜索的示例

圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。為了避免重復(fù)訪問(wèn)，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問(wèn)過(guò)的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過(guò)程中，一旦某一個(gè)頂點(diǎn)i

被訪問(wèn)，就立即讓visited[i]為1，防止它被多次訪問(wèn)。當(dāng)前53頁(yè)，總共140頁(yè)。

對(duì)上圖，深度優(yōu)先搜索遍歷的順序（之一）為：

v1

→v2→v4→v8→v5→v6→v3→v7。

圖7-10深度優(yōu)先搜索

當(dāng)前54頁(yè)，總共140頁(yè)。深度優(yōu)先搜索算法：intvisited[MAX_VERTEX_NUM];voidDFS(ALGraphG,intv){ArcNode*p;printf("%c",G.vertices[v].data);visited[v]=1;p=G.vertices[v].firstarc;while(p)

{if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;

}}//從第v個(gè)頂點(diǎn)出發(fā)DFS

當(dāng)前55頁(yè)，總共140頁(yè)。整個(gè)圖的DFS遍歷voidDFSTraverse(ALGraphG){for(intv=0;v<G.vexnum;++v)visited[v]=0;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}對(duì)于連通圖，從一個(gè)頂點(diǎn)出發(fā)，調(diào)用DFS函數(shù)即可將所有頂點(diǎn)都遍歷到。當(dāng)前56頁(yè)，總共140頁(yè)。

廣度優(yōu)先搜索（BFS）1．廣度優(yōu)先搜索思想

廣度優(yōu)先搜索遍歷類似于樹(shù)的按層次遍歷。對(duì)于無(wú)向連通圖，廣度優(yōu)先搜索是從圖的某個(gè)頂點(diǎn)v0出發(fā)，在訪問(wèn)v0之后，依次搜索訪問(wèn)v0的各個(gè)未被訪問(wèn)過(guò)的鄰接點(diǎn)w1，w2，…。然后順序搜索訪問(wèn)w1的各未被訪問(wèn)過(guò)的鄰接點(diǎn)，w2的各未被訪問(wèn)過(guò)的鄰接點(diǎn)，…。即從v0開(kāi)始，由近至遠(yuǎn)，按層次依次訪問(wèn)與v0有路徑相通且路徑長(zhǎng)度分別為1，2，…的頂點(diǎn)，直至連通圖中所有頂點(diǎn)都被訪問(wèn)一次。廣度優(yōu)先搜索的順序不是唯一的，例如圖7-10(a)連通圖的廣度優(yōu)先搜索遍歷順序可為v1，v2，v3，v4，v5，v6，v7，v8

也可為v1，v3，v2，v7，v6，v5，v4，v8。

當(dāng)前57頁(yè)，總共140頁(yè)。

廣度優(yōu)先搜索在搜索訪問(wèn)一層時(shí)，需要記住已被訪問(wèn)的頂點(diǎn)，以便在訪問(wèn)下層頂點(diǎn)時(shí)，從已被訪問(wèn)的頂點(diǎn)出發(fā)搜索訪問(wèn)其鄰接點(diǎn)。所以在廣度優(yōu)先搜索中需要設(shè)置一個(gè)隊(duì)列Queue，使已被訪問(wèn)的頂點(diǎn)順序由隊(duì)尾進(jìn)入隊(duì)列。在搜索訪問(wèn)下層頂點(diǎn)時(shí)，先從隊(duì)首取出一個(gè)已被訪問(wèn)的上層頂點(diǎn)，再?gòu)脑擁旤c(diǎn)出發(fā)搜索訪問(wèn)它的各個(gè)鄰接點(diǎn)。

廣度優(yōu)先搜索過(guò)程 廣度優(yōu)先生成樹(shù)廣度優(yōu)先搜索的示例當(dāng)前58頁(yè)，總共140頁(yè)。廣度優(yōu)先搜索過(guò)程可描述為：（1）f=0;r=0;//隊(duì)列初始化，空隊(duì)列；f-隊(duì)首指針，r-隊(duì)尾指針（2）訪問(wèn)v0;（3）visited[v0]=1;（4）insert(Queue,f,r,v0);//v0進(jìn)入隊(duì)尾（5）whilef>0do(i)delete(Queue,f,r,x);//隊(duì)首元素出隊(duì)并賦于x(ii)對(duì)所有x的鄰接點(diǎn)wifvisited[w]=0then（a）訪問(wèn)w;（b）visited[w]=1;

（c）insert(Queue,f,r,w);//w進(jìn)隊(duì)列

當(dāng)前59頁(yè)，總共140頁(yè)。

voidBFSseach(GraphG,intVisited[],intn){for(v=0;v<n;++v)visited[v]=0;//初始化訪問(wèn)標(biāo)志

InitQueue(Q);//置空的輔助隊(duì)列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){//v尚未訪問(wèn)

visited[v]=1;Visit(v);//訪問(wèn)uEnQueue(Q,v);

//v入隊(duì)列

while(!QueueEmpty(Q)){u=DeQueue(Q,u);//隊(duì)頭元素出隊(duì)并置為ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))

if(!visited[w])

{

visited[w]=1;Visit(w);EnQueue(Q,w);

//訪問(wèn)的頂點(diǎn)w入隊(duì)列

}//if}//while}//BFSTraverse當(dāng)前60頁(yè)，總共140頁(yè)。課堂練習(xí)練習(xí)1、寫(xiě)出右圖的鄰接矩陣表示。vexsA0B1C2D3E4F5ABCDEFarcs011000100111000001000000000100000010ACBDEF當(dāng)前61頁(yè)，總共140頁(yè)。課堂練習(xí)練習(xí)2、寫(xiě)出右圖的鄰接表表示。ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧當(dāng)前62頁(yè)，總共140頁(yè)。課堂練習(xí)練習(xí)3、根據(jù)右圖的如下存儲(chǔ)表示，寫(xiě)出以頂點(diǎn)A為出發(fā)點(diǎn)進(jìn)行DFS的頂點(diǎn)訪問(wèn)序列。ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧A，B，D，E，F(xiàn)，C當(dāng)前63頁(yè)，總共140頁(yè)。課堂練習(xí)ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧A，B，C，D，E，F(xiàn)練習(xí)4、根據(jù)右圖的如下存儲(chǔ)表示，寫(xiě)出以頂點(diǎn)A為出發(fā)點(diǎn)進(jìn)行BFS的頂點(diǎn)訪問(wèn)序列。當(dāng)前64頁(yè)，總共140頁(yè)。使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)。按照生成樹(shù)的定義，n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹(shù)有n個(gè)頂點(diǎn)、n-1條邊。構(gòu)造最小生成樹(shù)的準(zhǔn)則必須使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達(dá)到最小。7.4

最小生成樹(shù)

當(dāng)前65頁(yè)，總共140頁(yè)。普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡(luò)N={V,E}中的某一頂點(diǎn)u0出發(fā),選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊

(u0,v),將其頂點(diǎn)加入到生成樹(shù)頂點(diǎn)集合U中。 以后每一步從一個(gè)頂點(diǎn)在U中,而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合U中。如此繼續(xù)下去,直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹(shù)頂點(diǎn)集合U中為止。采用鄰接矩陣作為圖的存儲(chǔ)表示。當(dāng)前66頁(yè)，總共140頁(yè)。252510504613228102514242216185046132504613210原圖(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212當(dāng)前67頁(yè)，總共140頁(yè)。普里姆(Prim)算法在構(gòu)造過(guò)程中，還設(shè)置了兩個(gè)輔助數(shù)組：

lowcost[]存放生成樹(shù)頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹(shù)外各頂點(diǎn)的各邊上的當(dāng)前最小權(quán)值；

nearvex[]記錄生成樹(shù)頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近(即權(quán)值最小)。5046132281025142422161812當(dāng)前68頁(yè)，總共140頁(yè)。普里姆(Prim)算法若選擇從頂點(diǎn)0出發(fā)，即u0=0，則兩個(gè)輔助數(shù)組的初始狀態(tài)為：02810

-1000000

lowcostnearvex01234565046132281025142422161812當(dāng)前69頁(yè)，總共140頁(yè)。然后反復(fù)做以下工作在lowcost[]中選擇nearvex[i]-1&&lowcost[i]最小的邊,用

v標(biāo)記它。則選中的權(quán)值最小的邊為(nearvex[v],v),相應(yīng)的權(quán)值為

lowcost[v]。將nearvex[v]改為-1,表示它已加入生成樹(shù)頂點(diǎn)集合,將邊(nearvex[v],v,lowcost[v])加入生成樹(shù)的邊集合。取lowcost[i]=min{lowcost[i],Edge[v][i]}，即用生成樹(shù)頂點(diǎn)集合外各頂點(diǎn)i到剛加入該集合的新頂點(diǎn)v的距離

Edge[v][i]與原來(lái)它們到生成樹(shù)頂點(diǎn)集合中頂點(diǎn)的最短距離lowcost[i]做比較,取距離近的作為這些集合外頂點(diǎn)到生成樹(shù)頂點(diǎn)集合內(nèi)頂點(diǎn)的最短距離。如果生成樹(shù)頂點(diǎn)集合外頂點(diǎn)i到剛加入該集合的新頂點(diǎn)v的距離比原來(lái)它到生成樹(shù)頂點(diǎn)集合中頂點(diǎn)的最短距離還要近，則修改nearvex[i]:nearvex[i]=v。表示生成樹(shù)外頂點(diǎn)i到生成樹(shù)內(nèi)頂點(diǎn)v當(dāng)前距離最近。當(dāng)前70頁(yè)，總共140頁(yè)。02810

-1000000

lowcostnearvex0123456選v=5選邊(0,5)當(dāng)前71頁(yè)，總共140頁(yè)。頂點(diǎn)v=5加入生成樹(shù)頂點(diǎn)集合：02825

10

-10005

-10

lowcostnearvex0123456選v=4選邊(5,4)50461322810251424221618原圖邊(0,5,10)

加入生成樹(shù)1204613210255當(dāng)前72頁(yè)，總共140頁(yè)。0123456頂點(diǎn)v=4加入生成樹(shù)頂點(diǎn)集合：02822

2510

24

-100

4

-1-1

4

lowcostnearvex選v=3選邊(4,3)50461322810251424221618原圖邊(5,4,25)

加入生成樹(shù)125046132102522當(dāng)前73頁(yè)，總共140頁(yè)。頂點(diǎn)v=3加入生成樹(shù)頂點(diǎn)集合：02812

222510

18

-103

-1-1-1

3

lowcostnearvex0123456選v=2選邊(3,2)50461322810251424221618原圖邊(4,3,22)

加入生成樹(shù)12504613210252212當(dāng)前74頁(yè)，總共140頁(yè)。lowcostnearvex0123456頂點(diǎn)v=2加入生成樹(shù)頂點(diǎn)集合：0

16

1222251018

-1

2

-1-1-1-13

選v=1選邊(2,1)50461322810251424221618原圖邊(3,2,12)

加入生成樹(shù)125041321025221612當(dāng)前75頁(yè)，總共140頁(yè)。頂點(diǎn)v=1加入生成樹(shù)頂點(diǎn)集合：01612222510

14

-1-1

-1

-1-1-1

1

lowcostnearvex0123456選v=6選邊(1,6)50461322810251424221618原圖邊(2,1,16)

加入生成樹(shù)125046132102514221612當(dāng)前76頁(yè)，總共140頁(yè)。lowcostnearvex0123456頂點(diǎn)v=6加入生成樹(shù)頂點(diǎn)集合：0161222251014

-1-1

-1

-1-1-1-1

50461322810251424221618原圖邊(1,6,14)

加入生成樹(shù)125046132102514221612最后生成樹(shù)中邊集合里存入得各條邊為：

(0,5,10),(5,4,25),(4,3,22), (3,2,12),(2,1,16),(1,6,14)當(dāng)前77頁(yè)，總共140頁(yè)。采用鄰接表作為存儲(chǔ)結(jié)構(gòu)：設(shè)置一個(gè)輔助數(shù)組closedge[]：

lowcost域存放生成樹(shù)頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹(shù)外各頂點(diǎn)的各邊上的當(dāng)前最小權(quán)值；即存放在V-U中各個(gè)頂點(diǎn)到集合U中的當(dāng)前最小權(quán)值；

adjvex域記錄生成樹(shù)頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近(即權(quán)值最小)。即記錄該邊所依附的在U中的頂點(diǎn)。當(dāng)前78頁(yè)，總共140頁(yè)。利用普里姆算法建立最小生成樹(shù):---了解（P175）typedefintVRType;struct{ VertexTypeadjvex; VRTypelowcost;}closedge[MAX_VERTEX_NUM];voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){ intk,j,i,minCost; k=LocateVex(G,u); for(j=0;j<G.vexnum;++j) if(j!=k){ closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j];}當(dāng)前79頁(yè)，總共140頁(yè)。closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=minimum(closedge);minCost=INFINITY;for(j=0;j<G.vexnum;++j){if(closedge[j].lowcost<minCost&&closedge[j].lowcost!=0){minCost=closedge[j].lowcost; k=j;}}printf("(%c,%c)\n",closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j)if(G.arcs[k][j]<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j];}}}當(dāng)前80頁(yè)，總共140頁(yè)。

普里姆算法中的第二個(gè)for循環(huán)語(yǔ)句頻度為n-1，其中包含的兩個(gè)內(nèi)循環(huán)頻度也都為n-1，因此普里姆算法的時(shí)間復(fù)雜度為O(n2)。普里姆算法的時(shí)間復(fù)雜度與邊數(shù)e無(wú)關(guān)，該算法更適合于求邊數(shù)較多的帶權(quán)無(wú)向連通圖的最小生成樹(shù)。

當(dāng)前81頁(yè)，總共140頁(yè)?？唆斔箍?/p>

(Kruskal)算法克魯斯卡爾算法的基本思想：設(shè)一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn),沒(méi)有邊的非連通圖T={V,},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。當(dāng)在

E中選到一條具有最小權(quán)值的邊時(shí),若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點(diǎn)在同一個(gè)連通分量上為止。當(dāng)前82頁(yè)，總共140頁(yè)。應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程10504613228102514242216181250461325046132原圖(a)(b)當(dāng)前83頁(yè)，總共140頁(yè)。1012504613228102514242216181250461325046132101412原圖(c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123當(dāng)前84頁(yè)，總共140頁(yè)。為實(shí)現(xiàn)克魯斯卡爾算法需要設(shè)置一維輔助數(shù)組E，按權(quán)值從小到大的順序存放圖的邊，數(shù)組的下標(biāo)取值從0到e-1（e為圖G邊的數(shù)目）。了解----假設(shè)數(shù)組E存放圖G中的所有邊，且邊已按權(quán)值從小到大的順序排列。n為圖G的頂點(diǎn)個(gè)數(shù)，e為圖G的邊數(shù)?？唆斔箍査惴ㄈ缦拢?defineMAXE<最大邊數(shù)>#defineMAXV<最大頂點(diǎn)數(shù)>typedefstruct{intvex1;//邊的起始頂點(diǎn)intvex2;//邊的終止頂點(diǎn)intweight;//邊的權(quán)值}Edge;

當(dāng)前85頁(yè)，總共140頁(yè)。

Voidkruskal(EdgeE[],intn,inte){inti,j,m1,m2,sn1,sn2,k;intvset[MAXV];for(i=0;i<n;i++)//初始化輔助數(shù)組

vset[i]=i;k=1;//表示當(dāng)前構(gòu)造最小生成樹(shù)的第k條邊，初值為1

j=0;//E中邊的下標(biāo)，初值為0

while(k<e)//生成的邊數(shù)小于e時(shí)繼續(xù)循環(huán){ml=E[j].vex1;m2=E[j].vex2;//取一條邊的兩個(gè)鄰接點(diǎn)

sn1=vset[m1];sn2=vset[m2];//分別得到兩個(gè)頂點(diǎn)所屬的集合編號(hào)

if(sn1!=sn2)//兩頂點(diǎn)分屬于不同的集合，該邊是最小生成樹(shù)的一條邊當(dāng)前86頁(yè)，總共140頁(yè)。{printf(“(m1，m2)：％d＼n”,E[j].weight);k++;//生成邊數(shù)增lfor(i=0;i<n;i++)//兩個(gè)集合統(tǒng)一編號(hào)

if(vset[i]=i)//集合編號(hào)為sn2的改為sn1vset[i]=sn1;}j++;//掃描下一條邊}}

如果給定帶權(quán)無(wú)向連通圖G有e條邊，且邊已經(jīng)按權(quán)值遞增的次序存放在數(shù)組E中，則用克魯斯卡爾算法構(gòu)造最小生成樹(shù)的時(shí)間復(fù)雜度為O(e)。克魯斯卡爾算法的時(shí)間復(fù)雜度與邊數(shù)e有關(guān)，該算法適合于求邊數(shù)較少的帶權(quán)無(wú)向連通圖的最小生成樹(shù)。

當(dāng)前87頁(yè)，總共140頁(yè)。7.５有向無(wú)環(huán)圖及其應(yīng)用１、有向無(wú)環(huán)圖的定義有向無(wú)環(huán)圖是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過(guò)程的有效工具。因?yàn)閹缀跛械墓こ叹梢苑譃槿舾蓚€(gè)稱為活動(dòng)的子工程，而這些子工程之間，通常受著一定條件的約束，如其中某些子工程的開(kāi)始必須在另一些子工程完成之后。因此對(duì)整個(gè)工程和系統(tǒng)而言，最為關(guān)心的兩個(gè)問(wèn)題：

一是工程能否順利進(jìn)行；

二是估算整個(gè)工程完成所必須的最短時(shí)間。對(duì)應(yīng)于有向圖，即是探討拓?fù)渑判蚝完P(guān)鍵路徑問(wèn)題。當(dāng)前88頁(yè)，總共140頁(yè)。一個(gè)無(wú)環(huán)的有向圖稱作有向無(wú)環(huán)圖(DirectidAcyclineGragp)稱為DAG圖。有向無(wú)環(huán)圖是描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過(guò)程的有效工具當(dāng)前89頁(yè)，總共140頁(yè)。課程代號(hào)課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無(wú)C1C1,C2C1C3,C4C11C3.C5C3,C6無(wú)C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語(yǔ)言語(yǔ)言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無(wú)矛盾、順利地完成學(xué)業(yè)？？？頂點(diǎn)

——表示課程有向弧

——若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生選修課程問(wèn)題當(dāng)前90頁(yè)，總共140頁(yè)。AOV網(wǎng)——

用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexnetwork)，簡(jiǎn)稱AOV網(wǎng)。拓?fù)渑判颉?/p>

把AOV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過(guò)程叫~檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)。當(dāng)前91頁(yè)，總共140頁(yè)。在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧拓?fù)渑判虻姆椒ㄖ貜?fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止當(dāng)前92頁(yè)，總共140頁(yè)。C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏漠?dāng)前93頁(yè)，總共140頁(yè)。C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）當(dāng)前94頁(yè)，總共140頁(yè)。C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2（2）C9C3C4C5C6C7C8C10C11C12拓?fù)湫蛄校篊1--C2--C3（3）當(dāng)前95頁(yè)，總共140頁(yè)。C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4（4）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5（5）當(dāng)前96頁(yè)，總共140頁(yè)。C6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7（6）C11拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9C6C8C9C10C12C6C8C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11當(dāng)前97頁(yè)，總共140頁(yè)。C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12C8拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8當(dāng)前98頁(yè)，總共140頁(yè)。算法實(shí)現(xiàn)重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤叀Ｒ脏徑颖碜鞔鎯?chǔ)結(jié)構(gòu)把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧。當(dāng)前99頁(yè)，總共140頁(yè)。在實(shí)現(xiàn)拓?fù)渑判虻乃惴ㄖ?，采用鄰接表作為有向圖的存儲(chǔ)結(jié)構(gòu)，每個(gè)頂點(diǎn)設(shè)置一個(gè)單鏈表，每個(gè)單鏈表有一個(gè)表頭結(jié)點(diǎn)，在表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域count，這些表頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組，表頭結(jié)點(diǎn)定義如下：typedefstruct//表頭結(jié)點(diǎn){Vertexdata;//頂點(diǎn)信息

intcount;//存放頂點(diǎn)入度

ArcNode*firstarc;//指向第一條弧}Vnode;

在執(zhí)行拓?fù)渑判虻倪^(guò)程中，當(dāng)某個(gè)頂點(diǎn)的入度為零(沒(méi)有前驅(qū)頂點(diǎn))時(shí)，就將此頂點(diǎn)輸出，同時(shí)將該頂點(diǎn)的所有后繼頂點(diǎn)的入度減1，相當(dāng)于刪除所有以該頂點(diǎn)為尾的弧。為了避免重復(fù)檢測(cè)頂點(diǎn)的入度是否為零，需要設(shè)立一個(gè)棧來(lái)存放入度為零的頂點(diǎn)。執(zhí)行拓?fù)渑判虻乃惴ㄈ缦拢?/p>

當(dāng)前100頁(yè)，總共140頁(yè)。

voidtopsort(VNodeadj[],intn){inti,j;intstack[MAXV],top=0;//棧stack的指針為topArcNode*p;for(i=0;i<n;i++)if(adj[i].count==0)//建入度為0的頂點(diǎn)棧{top++;stack[top]=i;}while(top>0)//棧不為空{(diào)i=stack[top];top--;//頂點(diǎn)vi出棧

printf(“％d”,i);//輸出vip=adj[i].firstarc;//指向以vi為弧尾的第一條弧

while(p!=NULL){j=p->adjvex;//以vi為弧尾的弧的另一頂點(diǎn)vj

當(dāng)前101頁(yè)，總共140頁(yè)。

while(p!=NULL){j=p->adjvex;//以vi為弧尾的弧的另一頂點(diǎn)vjadj[j].count--;//頂點(diǎn)vj的入度減1

if(adj[j].count==0)//入度為0的相鄰頂點(diǎn)入棧{top++;stack[top]=j;}p=p->nextarc;//指向以vi為弧尾的下一條弧}}}

可見(jiàn)，對(duì)于有n個(gè)頂點(diǎn)和e條邊的有向圖而言，for循環(huán)中建立入度為0的頂點(diǎn)棧時(shí)間為O（n）；若在拓?fù)渑判蜻^(guò)程中不出現(xiàn)有向環(huán)，則每個(gè)頂點(diǎn)出棧、入棧和入度減1的操作在while(top>0)循環(huán)語(yǔ)句中均執(zhí)行e次，因此拓?fù)渑判蚩偟臅r(shí)間花費(fèi)為O(n+e)。

當(dāng)前102頁(yè)，總共140頁(yè)。例設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件事件V1——表示整個(gè)工程開(kāi)始事件V9——表示整個(gè)工程結(jié)束987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE網(wǎng)（ActivityOnEdge）邊表示活動(dòng)用頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間；網(wǎng)中只有：唯一一個(gè)入度為0的點(diǎn)源點(diǎn)唯一一個(gè)出度為0的點(diǎn)匯點(diǎn)完成整項(xiàng)工程至少需要多少時(shí)間？哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？7.5.2關(guān)鍵路徑當(dāng)前103頁(yè)，總共140頁(yè)。Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間ee(i)——表示活動(dòng)ai的最早開(kāi)始時(shí)間el(i)——表示活動(dòng)ai的最遲開(kāi)始時(shí)間

el(i)-ee(i)——表示完成活動(dòng)ai的時(shí)間余量關(guān)鍵活動(dòng)就是時(shí)間余量el(i)-ee(i)＝0的活動(dòng)關(guān)鍵路徑

——

路徑長(zhǎng)度最長(zhǎng)的路徑叫~關(guān)鍵活動(dòng)

——

關(guān)鍵路徑上的活動(dòng)叫~987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4

AOE網(wǎng)常用于表示工程的計(jì)劃或進(jìn)度。由于實(shí)際工程只有一個(gè)開(kāi)始點(diǎn)和一個(gè)結(jié)束點(diǎn)，同時(shí)AOE網(wǎng)應(yīng)當(dāng)是無(wú)環(huán)的。

當(dāng)前104頁(yè)，總共140頁(yè)。如何找ee(i)=el(i)的關(guān)鍵活動(dòng)？設(shè)活動(dòng)ai用弧<j,k>表示，其持續(xù)時(shí)間記為：dut(<j,k>)則有：（1）ee(i)=Ve(j)

（2）el(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開(kāi)始向前遞推(2)從Vl(n)=Ve(n)開(kāi)始向后遞推Ve(j)=從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度；Vl(k)=從頂點(diǎn)k到匯點(diǎn)的最短路徑長(zhǎng)度。當(dāng)前105頁(yè)，總共140頁(yè)。987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)eeelel-ee00002266046258377077071031616014140033求關(guān)鍵路徑步驟求Ve(i)->求Vl(j)->求ee(i),el(i),計(jì)算el(i)-ee(i)當(dāng)前106頁(yè)，總共140頁(yè)。算法描述輸入頂點(diǎn)和弧信息，建立其鄰接表計(jì)算每個(gè)頂點(diǎn)的入度對(duì)其進(jìn)行拓?fù)渑判蚺判蜻^(guò)程中求頂點(diǎn)的Ve[i]將得到的拓?fù)湫蛄羞M(jìn)棧按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的ee[i]和el[i],找出ee[i]=el[i]的關(guān)鍵活動(dòng)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4按拓?fù)渑判虻捻樞蛴?jì)算Ve按逆拓?fù)渑判虻捻樞蛴?jì)算Vl因此：對(duì)以拓?fù)渑判蛩惴榛A(chǔ)修改關(guān)鍵路徑算法當(dāng)前107頁(yè)，總共140頁(yè)。987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlink

vexnextvexdata

info123456789123456789011121122

26

34

45^

79^

51^

62^

51^

87^

84^

910^

94^當(dāng)前108頁(yè)，總共140頁(yè)。利用關(guān)鍵路徑法求AOE網(wǎng)的各關(guān)鍵活動(dòng)voidCriti