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

本章主要介紹圖的基本概念、圖的存儲(chǔ)結(jié)構(gòu)和有關(guān)圖的一些常用算法。通過本章學(xué)習(xí)，讀者應(yīng)該：1)

了解圖的定義和術(shù)語

2)掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)3)

掌握?qǐng)D的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法

4)

理解最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑等圖的常用算法

本章學(xué)習(xí)導(dǎo)讀

目前一頁\總數(shù)一百四十一頁\編于十四點(diǎn)1

圖（Graph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是線性關(guān)系，除開始結(jié)點(diǎn)和終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)直接前趨和直接后繼。在樹形結(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)用極為廣泛，特別是近年來的迅速發(fā)展，已滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。

目前二頁\總數(shù)一百四十一頁\編于十四點(diǎn)2

7.1圖的定義

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

7.3圖的遍歷

7.4圖的連通性問題

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

7.6最短路徑

第七章圖目前三頁\總數(shù)一百四十一頁\編于十四點(diǎn)3

圖定義

圖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ù)語目前四頁\總數(shù)一百四十一頁\編于十四點(diǎn)47.1圖的定義和術(shù)語圖的數(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)系的集合，即邊的集合。目前五頁\總數(shù)一百四十一頁\編于十四點(diǎn)5圖的術(shù)語有向圖:

對(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)的一條弧（arc），A為弧集合，x為弧尾（tail），y為弧頭（head)x弧尾y弧頭目前六頁\總數(shù)一百四十一頁\編于十四點(diǎn)6圖的術(shù)語無向圖:對(duì)一個(gè)圖G，若邊集E(G)為無向邊的集合，則稱該圖為無向圖。

①②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）目前七頁\總數(shù)一百四十一頁\編于十四點(diǎn)7圖的術(shù)語設(shè)n為頂點(diǎn)數(shù)，e為邊或弧的條數(shù)

對(duì)無向圖有：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ì)無向圖，每條邊連接2個(gè)頂點(diǎn)，故最多為n(n-1)/2

目前八頁\總數(shù)一百四十一頁\編于十四點(diǎn)8圖的術(shù)語端點(diǎn)和鄰接點(diǎn)

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

21453G2目前九頁\總數(shù)一百四十一頁\編于十四點(diǎn)9圖的術(shù)語起點(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目前十頁\總數(shù)一百四十一頁\編于十四點(diǎn)10圖的術(shù)語度

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

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

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

目前十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)11圖的術(shù)語子圖

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

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

①②③④⑤

①②G2③④⑤

目前十二頁\總數(shù)一百四十一頁\編于十四點(diǎn)12圖的術(shù)語簡(jiǎn)單圖

對(duì)不含多重邊和自環(huán)的圖。2145321453簡(jiǎn)單圖非簡(jiǎn)單圖目前十三頁\總數(shù)一百四十一頁\編于十四點(diǎn)13圖的術(shù)語完全圖

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

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

邊或弧很多的圖。

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

網(wǎng)：邊或弧上帶有權(quán)值的圖。目前十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)14圖的術(shù)語路徑

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

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

使得i=1,2,…k,

弧ai的頭vi,尾為vi-1

。

路徑長(zhǎng)度：路徑上邊或弧的數(shù)目目前十五頁\總數(shù)一百四十一頁\編于十四點(diǎn)15圖的術(shù)語簡(jiǎn)單路徑：除首尾兩點(diǎn)外，其他各點(diǎn)都不相同的路徑稱為簡(jiǎn)單路徑。簡(jiǎn)單路徑目前十六頁\總數(shù)一百四十一頁\編于十四點(diǎn)16圖的術(shù)語回路:無重復(fù)邊的閉路徑。環(huán)：閉的簡(jiǎn)單路徑，稱為環(huán)?；芈返皇黔h(huán)環(huán)目前十七頁\總數(shù)一百四十一頁\編于十四點(diǎn)17圖的術(shù)語連通圖：任何兩點(diǎn)都有路徑的圖。

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

的，則稱該圖是連通圖(vi<>vj)有向圖：若圖中任意兩個(gè)頂點(diǎn)vi,vj，都存在

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

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

(vi<>vj)目前十八頁\總數(shù)一百四十一頁\編于十四點(diǎn)18圖的術(shù)語連通分量：

無向圖：無向圖中極大連通子圖，稱為

連通分量

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

強(qiáng)連通分量目前十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)19生成樹圖的術(shù)語生成樹

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

①②④⑤

①②④⑤

①②④⑤

①②④⑤

有向樹

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

目前二十頁\總數(shù)一百四十一頁\編于十四點(diǎn)20生成樹、生成森林生成樹一個(gè)連通圖的生成樹是它的極小連通子圖，在n個(gè)頂點(diǎn)的情形下，有n-1條邊。生成樹是對(duì)連通圖而言的是連通圖的極小連通子圖包含圖中的所有頂點(diǎn)有且僅有n-1條邊

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

一個(gè)有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。目前二十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)21圖有兩種存儲(chǔ)結(jié)構(gòu)

鄰接矩陣鄰接表7.2圖的存儲(chǔ)結(jié)構(gòu)目前二十二頁\總數(shù)一百四十一頁\編于十四點(diǎn)227.2.1鄰接矩陣鄰接矩陣(AdjacencyMatrix)是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G＝(V，E)是具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣。7.2圖的存儲(chǔ)結(jié)構(gòu)

無向圖的鄰接矩陣是以主對(duì)角線對(duì)稱的，有向圖的鄰接矩陣可能是不對(duì)稱的。在有向圖中：第i行1的個(gè)數(shù)就是頂點(diǎn)i的出度，第j列1的個(gè)數(shù)就是頂點(diǎn)j的入度。在無向圖中,第i行(列)1的個(gè)數(shù)就是頂點(diǎn)i的度。目前二十三頁\總數(shù)一百四十一頁\編于十四點(diǎn)23一、鄰接矩陣（用二維數(shù)組表示）例如：G1的鄰接矩陣?yán)纾篏2的鄰接矩陣無向圖的鄰接矩陣為對(duì)稱矩陣G212345G11234目前二十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)24

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

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

目前二十五頁\總數(shù)一百四十一頁\編于十四點(diǎn)25

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

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

OD(vi)=

ID(vi)=

TD（vi）=目前二十六頁\總數(shù)一百四十一頁\編于十四點(diǎn)26若G是網(wǎng)（有權(quán)圖），鄰接矩陣定義為V2V1V3V435214如圖：

Wij若<vi,vj>

或<vj,vi>

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

0或若其它V1V2V3V4V1V2V3V4目前二十七頁\總數(shù)一百四十一頁\編于十四點(diǎn)27

頂點(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)。

目前二十八頁\總數(shù)一百四十一頁\編于十四點(diǎn)28

鄰接表

圖的鏈?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)。類似于樹的孩子鏈表表示法。在鄰接表中為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，用單鏈表中的一個(gè)結(jié)點(diǎn)表示依附于該頂點(diǎn)的一條邊（或表示以該頂點(diǎn)為弧尾的一條弧），稱為邊（或弧）結(jié)點(diǎn)。

目前二十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)2925341543533412212123451.無向圖鄰接表G212345adjvexnextarcvexdatafirstarc目前三十頁\總數(shù)一百四十一頁\編于十四點(diǎn)302.有向圖鄰接表234143121234如圖G1的鄰接表為：G11234目前三十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)31

在鄰接表的邊鏈表中，各個(gè)邊結(jié)點(diǎn)的鏈入順序任意，視邊結(jié)點(diǎn)輸入次序而定。設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，則用鄰接表表示無向圖時(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)。目前三十二頁\總數(shù)一百四十一頁\編于十四點(diǎn)32存儲(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;目前三十三頁\總數(shù)一百四十一頁\編于十四點(diǎn)3325341543533412212123451.無向圖鄰接表二、鄰接表G212345adjvexnextarcvexdatafirstarc目前三十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)341.無向圖鄰接表對(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目前三十五頁\總數(shù)一百四十一頁\編于十四點(diǎn)35二、鄰接表（adjacencylist）如圖G2的鄰接表為：2534154353341221212345G212345目前三十六頁\總數(shù)一百四十一頁\編于十四點(diǎn)36BACDFE例20A141B0452C353D254E015F123目前三十七頁\總數(shù)一百四十一頁\編于十四點(diǎn)372.有向圖鄰接表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目前三十八頁\總數(shù)一百四十一頁\編于十四點(diǎn)38142301201234

ABCDE2.有向圖的鄰接表ABECF可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。目前三十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)393.有向圖逆鄰接表123411431234此時(shí)，第i條鏈表上的結(jié)點(diǎn)數(shù)，為Vi的入度如圖G1的逆鄰接表為：①②③④G1目前四十頁\總數(shù)一百四十一頁\編于十四點(diǎn)40ABECD有向圖的逆鄰接表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

的入度。目前四十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)414.帶權(quán)有向圖的鄰接表鏈表中每個(gè)結(jié)點(diǎn)為三個(gè)域.

鄰接點(diǎn)權(quán)帶權(quán)圖的邊結(jié)點(diǎn)中info保存該邊上的權(quán)值。目前四十二頁\總數(shù)一百四十一頁\編于十四點(diǎn)42ABECD4.帶權(quán)有向圖的鄰接表ABCDE0123411037^04

4223^28^102254837125^頂點(diǎn)Vi的邊鏈表的頭結(jié)點(diǎn)存放在下標(biāo)為i的頂點(diǎn)數(shù)組中。目前四十三頁\總數(shù)一百四十一頁\編于十四點(diǎn)43

十字鏈表

十字鏈表(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目前四十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)44圖7-8十字鏈表

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

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

目前四十五頁\總數(shù)一百四十一頁\編于十四點(diǎn)45十字鏈表的數(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;目前四十六頁\總數(shù)一百四十一頁\編于十四點(diǎn)467.2.4鄰接多重表

鄰接多重表是無向圖的另一種鏈?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)如下：

目前四十七頁\總數(shù)一百四十一頁\編于十四點(diǎn)47圖7-9鄰接多重表

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

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

目前四十八頁\總數(shù)一百四十一頁\編于十四點(diǎn)48鄰接多重表的結(jié)點(diǎn)數(shù)據(jù)類型定義如下：

#defineMAXV<最大頂點(diǎn)個(gè)數(shù)>typedefstruct//邊結(jié)點(diǎn)類型{intmark;//訪問標(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;

目前四十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)497.3圖的遍歷

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

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

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

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

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

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

深度優(yōu)先搜索遍歷（簡(jiǎn)稱DFS）廣度優(yōu)先搜索遍歷（簡(jiǎn)稱BFS）目前五十頁\總數(shù)一百四十一頁\編于十四點(diǎn)50

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

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

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

接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。目前五十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)51

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

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

被訪問，就立即讓visited[i]為1，防止它被多次訪問。目前五十二頁\總數(shù)一百四十一頁\編于十四點(diǎn)52

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

v1

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

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

目前五十三頁\總數(shù)一百四十一頁\編于十四點(diǎn)53深度優(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

目前五十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)54整個(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)都遍歷到。目前五十五頁\總數(shù)一百四十一頁\編于十四點(diǎn)55

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

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

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

目前五十六頁\總數(shù)一百四十一頁\編于十四點(diǎn)56

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

廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先搜索的示例目前五十七頁\總數(shù)一百四十一頁\編于十四點(diǎn)57廣度優(yōu)先搜索過程可描述為：（1）f=0;r=0;//隊(duì)列初始化，空隊(duì)列；f-隊(duì)首指針，r-隊(duì)尾指針（2）訪問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;（b）visited[w]=1;（c）insert(Queue,f,r,w);//w進(jìn)隊(duì)列

目前五十八頁\總數(shù)一百四十一頁\編于十四點(diǎn)58

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

InitQueue(Q);//置空的輔助隊(duì)列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){//v尚未訪問visited[v]=1;Visit(v);//訪問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);

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

}//if}//while}//BFSTraverse目前五十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)59課堂練習(xí)練習(xí)1、寫出右圖的鄰接矩陣表示。ACBDEF目前六十頁\總數(shù)一百四十一頁\編于十四點(diǎn)60課堂練習(xí)練習(xí)2、寫出右圖的鄰接表表示。ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧目前六十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)61課堂練習(xí)練習(xí)3、根據(jù)右圖的如下存儲(chǔ)表示，寫出以頂點(diǎn)A為出發(fā)點(diǎn)進(jìn)行DFS的頂點(diǎn)訪問序列。ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧A，B，D，E，F(xiàn)，C目前六十二頁\總數(shù)一百四十一頁\編于十四點(diǎn)62課堂練習(xí)ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

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

最小生成樹

目前六十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)64普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡(luò)N={V,E}中的某一頂點(diǎn)u0出發(fā),選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v),將其頂點(diǎn)加入到生成樹頂點(diǎn)集合U中。 以后每一步從一個(gè)頂點(diǎn)在U中,而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點(diǎn)加入到集合U中。如此繼續(xù)下去,直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。采用鄰接矩陣作為圖的存儲(chǔ)表示。目前六十五頁\總數(shù)一百四十一頁\編于十四點(diǎn)65252510504613228102514242216185046132504613210原圖(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212目前六十六頁\總數(shù)一百四十一頁\編于十四點(diǎn)66普里姆(Prim)算法在構(gòu)造過程中，還設(shè)置了兩個(gè)輔助數(shù)組：

lowcost[]存放生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹外各頂點(diǎn)的各邊上的當(dāng)前最小權(quán)值；nearvex[]記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近(即權(quán)值最小)。5046132281025142422161812目前六十七頁\總數(shù)一百四十一頁\編于十四點(diǎn)67普里姆(Prim)算法若選擇從頂點(diǎn)0出發(fā)，即u0=0，則兩個(gè)輔助數(shù)組的初始狀態(tài)為：02810

-1000000

lowcostnearvex01234565046132281025142422161812目前六十八頁\總數(shù)一百四十一頁\編于十四點(diǎn)68然后反復(fù)做以下工作在lowcost[]中選擇nearvex[i]-1&&lowcost[i]最小的邊,用v標(biāo)記它。則選中的權(quán)值最小的邊為(nearvex[v],v),相應(yīng)的權(quán)值為lowcost[v]。將nearvex[v]改為-1,表示它已加入生成樹頂點(diǎn)集合,將邊(nearvex[v],v,lowcost[v])加入生成樹的邊集合。取lowcost[i]=min{lowcost[i],Edge[v][i]}，即用生成樹頂點(diǎn)集合外各頂點(diǎn)i到剛加入該集合的新頂點(diǎn)v的距離Edge[v][i]與原來它們到生成樹頂點(diǎn)集合中頂點(diǎn)的最短距離lowcost[i]做比較,取距離近的作為這些集合外頂點(diǎn)到生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)的最短距離。如果生成樹頂點(diǎn)集合外頂點(diǎn)i到剛加入該集合的新頂點(diǎn)v的距離比原來它到生成樹頂點(diǎn)集合中頂點(diǎn)的最短距離還要近，則修改nearvex[i]:nearvex[i]=v。表示生成樹外頂點(diǎn)i到生成樹內(nèi)頂點(diǎn)v當(dāng)前距離最近。目前六十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)6902810

-1000000

lowcostnearvex0123456選v=5選邊(0,5)目前七十頁\總數(shù)一百四十一頁\編于十四點(diǎn)70頂點(diǎn)v=5加入生成樹頂點(diǎn)集合：02825

10

-10005

-10

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

加入生成樹1204613210255目前七十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)710123456頂點(diǎn)v=4加入生成樹頂點(diǎn)集合：02822

2510

24

-100

4

-1-1

4

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

加入生成樹125046132102522目前七十二頁\總數(shù)一百四十一頁\編于十四點(diǎn)72頂點(diǎn)v=3加入生成樹頂點(diǎn)集合：02812

222510

18

-103

-1-1-1

3

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

加入生成樹12504613210252212目前七十三頁\總數(shù)一百四十一頁\編于十四點(diǎn)73lowcostnearvex0123456頂點(diǎn)v=2加入生成樹頂點(diǎn)集合：0

16

1222251018

-1

2

-1-1-1-13

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

加入生成樹125041321025221612目前七十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)74頂點(diǎn)v=1加入生成樹頂點(diǎn)集合：01612222510

14

-1-1

-1

-1-1-1

1

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

加入生成樹125046132102514221612目前七十五頁\總數(shù)一百四十一頁\編于十四點(diǎn)75lowcostnearvex0123456頂點(diǎn)v=6加入生成樹頂點(diǎn)集合：0161222251014

-1-1

-1

-1-1-1-1

50461322810251424221618原圖邊(1,6,14)

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

(0,5,10),(5,4,25),(4,3,22), (3,2,12),(2,1,16),(1,6,14)目前七十六頁\總數(shù)一百四十一頁\編于十四點(diǎn)76采用鄰接表作為存儲(chǔ)結(jié)構(gòu)：設(shè)置一個(gè)輔助數(shù)組closedge[]：

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

adjvex域記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近(即權(quán)值最小)。即記錄該邊所依附的在U中的頂點(diǎn)。目前七十七頁\總數(shù)一百四十一頁\編于十四點(diǎn)77利用普里姆算法建立最小生成樹:---了解（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];}目前七十八頁\總數(shù)一百四十一頁\編于十四點(diǎn)78closedge[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];}}}目前七十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)79

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

目前八十頁\總數(shù)一百四十一頁\編于十四點(diǎn)80克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的基本思想：設(shè)一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn),沒有邊的非連通圖T={V,},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。當(dāng)在

E中選到一條具有最小權(quán)值的邊時(shí),若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點(diǎn)在同一個(gè)連通分量上為止。目前八十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)81應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程10504613228102514242216181250461325046132原圖(a)(b)目前八十二頁\總數(shù)一百四十一頁\編于十四點(diǎn)821012504613228102514242216181250461325046132101412原圖(c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123目前八十三頁\總數(shù)一百四十一頁\編于十四點(diǎn)83為實(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;

目前八十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)84

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)造最小生成樹的第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ù)一百四十一頁\編于十四點(diǎn)85

{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)無向連通圖G有e條邊，且邊已經(jīng)按權(quán)值遞增的次序存放在數(shù)組E中，則用克魯斯卡爾算法構(gòu)造最小生成樹的時(shí)間復(fù)雜度為O(e)?？唆斔箍査惴ǖ臅r(shí)間復(fù)雜度與邊數(shù)e有關(guān)，該算法適合于求邊數(shù)較少的帶權(quán)無向連通圖的最小生成樹。

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

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

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

——表示課程有向弧

——若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生選修課程問題目前八十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)89AOV網(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è)線性序列的過程叫~檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV網(wǎng)必定不存在環(huán)。目前九十頁\總數(shù)一百四十一頁\編于十四點(diǎn)90在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧拓?fù)渑判虻姆椒ㄖ貜?fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止目前九十一頁\總數(shù)一百四十一頁\編于十四點(diǎn)91C1C2C3C4C5C6C7C8C9C10C11C12拓?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ù)湫蛄胁皇俏ㄒ坏哪壳熬攀揬總數(shù)一百四十一頁\編于十四點(diǎn)92C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）目前九十三頁\總數(shù)一百四十一頁\編于十四點(diǎn)93C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2（2）C9C3C4C5C6C7C8C10C11C12拓?fù)湫蛄校篊1--C2--C3（3）目前九十四頁\總數(shù)一百四十一頁\編于十四點(diǎn)94C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4（4）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5（5）目前九十五頁\總數(shù)一百四十一頁\編于十四點(diǎn)95C6C8C10C11C12拓?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目前九十六頁\總數(shù)一百四十一頁\編于十四點(diǎn)96C6C8C12拓?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目前九十七頁\總數(shù)一百四十一頁\編于十四點(diǎn)97算法實(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)棧。目前九十八頁\總數(shù)一百四十一頁\編于十四點(diǎn)98在實(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ù)渑判虻倪^程中，當(dāng)某個(gè)頂點(diǎn)的入度為零(沒有前驅(qū)頂點(diǎn))時(shí)，就將此頂點(diǎn)輸出，同時(shí)將該頂點(diǎn)的所有后繼頂點(diǎn)的入度減1，相當(dāng)于刪除所有以該頂點(diǎn)為尾的弧。為了避免重復(fù)檢測(cè)頂點(diǎn)的入度是否為零，需要設(shè)立一個(gè)棧來存放入度為零的頂點(diǎn)。執(zhí)行拓?fù)渑判虻乃惴ㄈ缦拢?/p>

目前九十九頁\總數(shù)一百四十一頁\編于十四點(diǎn)99

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

目前一百頁\總數(shù)一百四十一頁\編于十四點(diǎn)100

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為弧尾的下一條弧}}}

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

目前一百零一頁\總數(shù)一百四十一頁\編于十四點(diǎn)101例設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件事件V1——表示整個(gè)工程開始事件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)鍵路徑目前一百零二頁\總數(shù)一百四十一頁\編于十四點(diǎn)102Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間ee(i)——表示活動(dòng)ai的最早開始時(shí)間el(i)——表示活動(dòng)ai的最遲開始時(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=4AOE網(wǎng)常用于表示工程的計(jì)劃或進(jìn)度。由于實(shí)際工程只有一個(gè)開始點(diǎn)和一個(gè)結(jié)束點(diǎn)，同時(shí)AOE網(wǎng)應(yīng)當(dāng)是無環(huán)的。

目前一百零三頁\總數(shù)一百四十一頁\編于十四點(diǎn)103如何找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開始向前遞推(2)從Vl(n)=Ve(n)開始向后遞推Ve(j)=從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度；Vl(k)=從頂點(diǎn)k到匯點(diǎn)的最短路徑長(zhǎng)度。目前一百零四頁\總數(shù)一百四十一頁\編于十四點(diǎn)104987645321a2=4