本章主要介紹圖的基本概念、圖的存儲結(jié)構(gòu)和有關(guān)圖的一些常課件

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

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

2)掌握圖的各種存儲結(jié)構(gòu)3)

掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法

4)

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

第6章圖2022/10/281本章主要介紹圖的基本概念、圖的存儲結(jié)構(gòu)和有關(guān)

圖(Graph)是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)：對結(jié)點(diǎn)的前趨和后繼個數(shù)不加限制的數(shù)據(jù)結(jié)構(gòu)，描述元素之間”多對多”關(guān)系。圖的應(yīng)用極廣，已滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支中。在線性結(jié)構(gòu)中，結(jié)點(diǎn)之間是線性關(guān)系，除開始結(jié)點(diǎn)和終端結(jié)點(diǎn)外，每個結(jié)點(diǎn)只有一個直接前趨和直接后繼。在樹形結(jié)構(gòu)中，結(jié)點(diǎn)之間實(shí)質(zhì)上是層次關(guān)系，同層上的每個結(jié)點(diǎn)可以和下一層的零個或多個結(jié)點(diǎn)（即孩子）相關(guān)，但只和上一層的一個結(jié)點(diǎn)（即雙親）相關(guān)（根結(jié)點(diǎn)除外），樹是圖的特例?。?！圖的引入：哥尼斯堡橋問題2022/10/282圖(Graph)是一種較線性表和樹更為復(fù)雜的非線性結(jié)

6.1.1圖的定義

圖G是由一個頂點(diǎn)(vertex)構(gòu)成的有窮非空集V(G)和一個由邊(edge)R構(gòu)成的有窮允空集E(G)組成的數(shù)據(jù)結(jié)構(gòu)。Graph=(V,E)

V={x|x

某個數(shù)據(jù)對象}，是頂點(diǎn)的有窮非空集合；

E——邊的有限集合無向圖：R={(x,y)|x,y

V},頂點(diǎn)間無次序關(guān)系有向圖：R={<x,y>|x,y

V&&Path(x,y)}是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。Path(x,y)表示從x到y(tǒng)的一條單向通路,它是有方向的。x弧尾，y弧頭。6.1圖及其基本運(yùn)算

2022/10/2836.1.1圖的定義6.1圖及其基本

6.1.2圖的基本術(shù)語RZYX有向圖與無向圖有向圖中：邊用<x,y>表示，且x與y是有序的。

a.有向圖中的邊稱為“弧”

b.x——弧尾或初始點(diǎn)y——弧頭或終端點(diǎn)無向圖：邊用(x,y)表示，且頂x與y是無序的。完全圖在具有n個頂點(diǎn)的有向圖中，最大弧數(shù)為

n(n-1)

在具有n個頂點(diǎn)的無向圖中，最大邊數(shù)為

n(n-1)/2頂點(diǎn)的度無向圖：與該頂點(diǎn)相關(guān)的邊的數(shù)目有向圖：入度ID(v)：以該頂點(diǎn)為頭的弧的數(shù)目出度OD(v)：以該頂點(diǎn)為尾頭的弧的數(shù)目在有向圖中,頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。XSRZY2022/10/2846.1.2圖的基本術(shù)語RZYX有向圖與無向圖XSR無向圖和有向圖度

1.無向圖G1中頂點(diǎn)3的度為4，頂點(diǎn)5的度為3。2.有向圖G3中頂點(diǎn)1的出度OD(1)=3，入度ID(1)=1，其度TD(1)=4。在圖6-1中，圖(a)為無向圖，其中G1的頂點(diǎn)集合和邊集合分別為：V(G1)={1，2，3，4，5，6，7}，E(G1)={(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)}。圖(c)為有向圖，其中G3的頂點(diǎn)集合和弧集合分別為V(G3)={1，2，3，4，5，6}，E(G3)={<1，2>，<1，3>，<1，4>，<3，1>，<4，5>，<5，6>，<6，4>}

2022/10/285無向圖和有向圖度在圖6-1中，圖(a)為無向圖，其2．路徑和回路在無向圖G中，若存在一個頂點(diǎn)序列Vp,Vi1，Vi2，…，Vin，Vq,使得（Vp,Vi1）,(Vi1,Vi2),…..，(Vin,Vq)均屬于E（G），則稱頂點(diǎn)Vp到Vq存在一條路徑。若一條路徑上除起點(diǎn)和終點(diǎn)可以相同外，其余頂點(diǎn)均不相同，則稱此路徑為簡單路徑。起點(diǎn)和終點(diǎn)相同的路徑稱為回路；簡單路徑組成的回路稱為簡單回路。路徑長度

路徑上經(jīng)過的邊的數(shù)目稱為該路徑的路徑長度。非帶權(quán)圖的路徑長度是指此路徑上邊/弧的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊/弧的權(quán)之和。2022/10/2862．路徑和回路2022/10/226簡單路徑:若路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù),則稱這樣的路徑為簡單路徑?；芈?若路徑上第一個頂點(diǎn)v1與最后一個頂點(diǎn)vm重合,則稱這樣的路徑為回路或環(huán)。2022/10/287簡單路徑:若路徑上各頂點(diǎn)v1,v2,...,vm均不互3.邊和弧邊:無向圖中頂點(diǎn)的偶對，寫成（Vx，Vy）或（Vy，Vx）?；?有向圖中頂點(diǎn)的偶對,〈Vx,Vy〉表示從Vx到Vy?；☆^:弧的終點(diǎn)弧尾:弧的起點(diǎn)弧〈Vx，Vy〉

弧尾Vx弧頭Vy4．子圖設(shè)有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。2022/10/2883.邊和弧弧〈Vx，Vy〉4．子圖2022/10/228圖6-3連通分量和強(qiáng)連通分量5．連通性在無向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對頂點(diǎn)vi和vj（vi，vj∈V）都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。圖6-1中G1是連通圖，G2是非連通圖。G2中有3個連通分量，如圖6-3（a）所示。6．強(qiáng)連通圖與強(qiáng)連通分量

在有向圖中,若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。

2022/10/289圖6-3連通分量和強(qiáng)連通分量5．連通性2022/10/27．鄰接點(diǎn)頂點(diǎn):圖中的結(jié)點(diǎn)鄰接點(diǎn):無向圖中，若邊(Ｖx,Ｖy)E，兩頂點(diǎn)之間有條邊，則兩頂點(diǎn)互為鄰接點(diǎn)。x——y(x,y)有向圖中，若弧(Ｖx,Ｖy)E，從x到y(tǒng)有一條弧，則y是x的鄰接點(diǎn)，但x不是y的鄰接點(diǎn)。xy<x,y>VxVyＶx、Ｖy互為鄰接點(diǎn)VxVyＶy是Ｖx的鄰接點(diǎn)2022/10/28107．鄰接點(diǎn)VxVyＶx、Ｖy互為鄰接點(diǎn)VxVyＶy是Ｖx的鄰1鄰接矩陣鄰接矩陣(AdjacencyMatrix)是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G＝(V，E)是具有n個頂點(diǎn)的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣。6.1.3圖的存儲結(jié)構(gòu)

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

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

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

的入度。在無向圖中,第i

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

的度。2022/10/28111鄰接矩陣6.1.3圖的存儲結(jié)構(gòu)無圖6-6

有向圖及其鄰接矩陣

圖6-5無向圖及其鄰接矩陣

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

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

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

ID(vi)=

TD（vi）=2022/10/2813無向圖，（vi，vj）和（vj，vi）表示同一條邊，因頂點(diǎn)表:一個記錄各個頂點(diǎn)信息的一維數(shù)組，鄰接矩陣：一個表示各個頂點(diǎn)之間的關(guān)系（邊或?。┑亩S數(shù)組。

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

#defineMAX_VERTICES

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

AdjMatrixarcs;//鄰接矩陣

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

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

2022/10/2814頂點(diǎn)表:一個記錄各個頂點(diǎn)信息的一維數(shù)組，2022/10/建立鄰接矩陣算法:voidCreateMGraph(MGraph&G){inti,j,k,w;charv1,v2;printf("Inputvexnum&arcnum:");scanf("%d,%d",&G.vexnum,&G.arcnum);printf("InputVertices:");scanf("%s",G.vexs);for(i=0;i<G.vexnum;i++)scanf("%c",&G.vexs[i]);for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) G.arcs[i][j]=0;for(k=0;k<G.arcnum;k++){printf("InputArcs(v1,v2&w):\n"); scanf("%c%c,%d",&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2);j=LocateVex(G,v2);voidPrintMGraph(MGraphG)//輸出{inti,j;printf("OutputVertices:");printf("%s",G.vexs);printf("\n");printf("OutputAdjMatrix:\n");for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)printf("%4d",G.arcs[i][j]); printf("\n");}return;}G.arcs[i][j]=w;G.arcs[j][i]=w;}return;}2022/10/2815建立鄰接矩陣算法:voidPrintMGraph(MGra

2鄰接表

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

鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰接表中為圖中每個頂點(diǎn)建立一個單鏈表，用單鏈表中的一個結(jié)點(diǎn)表示依附于該頂點(diǎn)的一條邊（或表示以該頂點(diǎn)為弧尾的一條弧），稱為邊（或?。┙Y(jié)點(diǎn)。把同一個頂點(diǎn)發(fā)出的邊鏈接在同一個邊鏈表中，鏈表的每一個結(jié)點(diǎn)代表一條邊，叫做表結(jié)點(diǎn)（邊結(jié)點(diǎn)），鄰接點(diǎn)域vertex保存與該邊相關(guān)聯(lián)的另一頂點(diǎn)的頂點(diǎn)下標(biāo)，鏈域link存放指向同一鏈表中下一個表結(jié)點(diǎn)的指針，數(shù)據(jù)域info存放邊的權(quán)。邊鏈表的表頭指針存放在頭結(jié)點(diǎn)中。頭結(jié)點(diǎn)以順序結(jié)構(gòu)存儲，其數(shù)據(jù)域data存放頂點(diǎn)信息，鏈域firstarc指向鏈表中第一個頂點(diǎn)。表結(jié)點(diǎn)頭結(jié)點(diǎn)vertexlinkinfodatafirstarc2022/10/28162鄰接表表結(jié)點(diǎn)頭結(jié)點(diǎn)vertexlinkinfod帶權(quán)圖的邊結(jié)點(diǎn)中info保存該邊上的權(quán)值。頂點(diǎn)Vi的邊鏈表的頭結(jié)點(diǎn)存放在下標(biāo)為i的頂點(diǎn)數(shù)組中。在鄰接表的邊鏈表中，各個邊結(jié)點(diǎn)的鏈入順序任意，視邊結(jié)點(diǎn)輸入次序而定。設(shè)圖中有n個頂點(diǎn)，e條邊，則用鄰接表表示無向圖時，需要n個頂點(diǎn)結(jié)點(diǎn)，2e個邊結(jié)點(diǎn)；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點(diǎn)結(jié)點(diǎn)，e個邊結(jié)點(diǎn)。建立鄰接表的時間復(fù)雜度為O(n*e)。若頂點(diǎn)信息即為頂點(diǎn)的下標(biāo)，則時間復(fù)雜度為O(n+e)。2022/10/2817帶權(quán)圖的邊結(jié)點(diǎn)中info保存該邊上的權(quán)值有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第i

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

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

的入度。2022/10/2818有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第i個鏈表中圖6-6為圖6-6(a)的的鄰接表和逆鄰接表圖6-7有向圖的鄰接表和逆鄰接表6-6(a)2022/10/2819圖6-6為圖6-6(a)的的鄰接表和逆鄰接表圖6-7網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表2022/10/2820網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表2022/10/22203正交鏈表存儲表示(十字鏈表）

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

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

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

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

hlink指向弧頭相同的下一條弧，tlink指向弧尾相同的下一條?。籨ata頂點(diǎn)信息，firstin以該頂點(diǎn)為頭的第一個弧結(jié)點(diǎn)，firstout以該結(jié)點(diǎn)為尾的第一個弧結(jié)點(diǎn)headvextailvexhlinktlinkinfofirstindatafirstout頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)2022/10/28213正交鏈表存儲表示(十字鏈表）

十字鏈表圖7-8十字鏈表

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

4321323120120301ùùùùùùùù03212022/10/2822圖7-8十字鏈表圖6-8為圖6-6(a)有向圖的正交鏈鄰接多重表的結(jié)構(gòu)定義：

typedefstructedge*edge_pointer;Typesturctedge{

shortintmarked;intvertex1;intvertex2;edge_pointerpath1;edge_pointerpath2;};Edge_pointergraph[MAX_VERTICES];2022/10/2823鄰接多重表的結(jié)構(gòu)定義：2022/10/2223帶權(quán)的邊權(quán)

某些圖的邊或弧具有與它相關(guān)的數(shù),稱之為權(quán)。權(quán)可以代表一個頂點(diǎn)到另一個頂點(diǎn)的距離，耗費(fèi)等。網(wǎng)絡(luò)這種帶權(quán)連通圖圖一般稱為網(wǎng)絡(luò)。如圖6-4所示。

2022/10/2824帶權(quán)的邊2022/10/22246.2圖的基本運(yùn)算與基本操作

圖的基本運(yùn)算也包括查找、插入和刪除。（1）頂點(diǎn)定位運(yùn)算

確定頂點(diǎn)v在圖中的位置；（2）取頂點(diǎn)運(yùn)算

求取圖中第i個頂點(diǎn)；（3）求第一個鄰接點(diǎn)運(yùn)算

求圖中頂點(diǎn)v的第一個鄰接點(diǎn)；（4）求下一個鄰接點(diǎn)運(yùn)算

已知w為圖中頂點(diǎn)v的某個鄰接點(diǎn)，求頂點(diǎn)w的下一個鄰接點(diǎn)；（5）插入頂點(diǎn)運(yùn)算

在圖中增添一個頂點(diǎn)v作為圖的第n+1個頂點(diǎn)，其中n為插入該頂點(diǎn)前圖的頂點(diǎn)個數(shù)；（6）插入弧運(yùn)算

在圖中增添一條從頂點(diǎn)v到頂點(diǎn)w的弧。（7）刪除頂點(diǎn)運(yùn)算

從圖中刪除頂點(diǎn)v以及所有與頂點(diǎn)v相關(guān)聯(lián)的弧。（8）刪除弧運(yùn)算從圖中刪除一條從頂點(diǎn)v到頂點(diǎn)w的弧。2022/10/28256.2圖的基本運(yùn)算與基本操作2022/10/2225存儲表示typedefstructArcNode{ intadjvex; structArcNode*nextarc; intinfo;}ArcNode;//邊結(jié)點(diǎn)類型typedefstructVNode{ VertexTypedata; ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{ AdjListvertices;//鄰接表

intvexnum,arcnum;}ALGraph;2022/10/2826存儲表示2022/10/2226intLocateVex(ALGraphG,charu){ inti; for(i=0;i<G.vexnum;i++){if(u==G.vertices[i].data)returni;} if(i==G.vexnum){printf("Erroru!\n");exit(1);} return0;}voidCreateALGraph_adjlist(ALGraph&G){ inti,j,k,w;charv1,v2; ArcNode*p; printf("Inputvexnum&arcnum:"); scanf("%d,%d",&G.vexnum,&G.arcnum); printf("InputVertices:"); for(i=0;i<G.vexnum;i++){ scanf("%c",&G.vertices[i].data); G.vertices[i].firstarc=NULL;}}2022/10/2827intLocateVex(ALGraphG,charu

printf("InputArcs(v1,v2&w):\n");for(k=0;k<G.arcnum;k++){ scanf("%c,%c,%d",&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=w; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; } return;2022/10/2828printf("InputArcs(v1,v2&w6.2圖的基本操作：圖的遍歷圖的遍歷順序有兩種：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）

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

但是，在圖中有回路，從圖中某一頂點(diǎn)出發(fā)訪問圖中其它頂點(diǎn)時，可能又會回到出發(fā)點(diǎn)，而圖中或許還有頂點(diǎn)沒有訪問到，因此，圖的遍歷較樹的遍歷更復(fù)雜。圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。

2022/10/28296.2圖的基本操作：圖的遍歷圖的遍歷順序有兩種：2022/6.2.1深度優(yōu)先搜索（DFS）1．深度優(yōu)先搜索思想深度優(yōu)先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪問過，在G中任選一個頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遞歸調(diào)用包含以下操作：（1）訪問搜索到的未被訪問的鄰接點(diǎn)；（2）將此頂點(diǎn)的visited數(shù)組元素值置1；（3）搜索該頂點(diǎn)的未被訪問的鄰接點(diǎn)，若該鄰接點(diǎn)存在，則從此鄰接點(diǎn)開始進(jìn)行同樣的訪問和搜索。

深度優(yōu)先搜索DFS可描述為：（1）訪問v0頂點(diǎn)；（2）置

visited[v0]=1；（3）搜索v0未被訪問的鄰接點(diǎn)w，若存在鄰接點(diǎn)w，則DFS(w)。

2022/10/28306.2.1深度優(yōu)先搜索（DFS）2022/10/2230

遍歷過程：

DFS在訪問圖中某一起始頂點(diǎn)v后，由v出發(fā)，訪問它的任一鄰接頂點(diǎn)w1；再從w1出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點(diǎn)w2；然后再從w2出發(fā)，進(jìn)行類似的訪問，…如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn)u為止。接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。2022/10/2831遍歷過程：2022/10/2231深度優(yōu)先搜索的示例圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個頂點(diǎn)之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。為了避免重復(fù)訪問，可設(shè)置一個標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點(diǎn)i

被訪問，就立即讓visited[i]為1，防止它被多次訪問。2022/10/2832深度優(yōu)先搜索的示例圖中可能存在回路，且圖的任對上圖，深度優(yōu)先搜索遍歷的順序（之一）為：

v1

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

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

2022/10/2833對上圖，深度優(yōu)先搜索遍歷的順序（之一）為：圖6-10深度優(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個頂點(diǎn)出發(fā)DFS

2022/10/2834深度優(yōu)先搜索算法：2022/10/2234整個圖的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);}對于連通圖，從一個頂點(diǎn)出發(fā)，調(diào)用DFS函數(shù)即可將所有頂點(diǎn)都遍歷到。2022/10/2835整個圖的DFS遍歷2022/10/22356.2.2廣度優(yōu)先搜索（BFS）1．廣度優(yōu)先搜索思想

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

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

2022/10/28366.2.2廣度優(yōu)先搜索（BFS）2022/10/22361．廣度優(yōu)先搜索思想設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問，在G中任選一頂點(diǎn)i作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是：

（1）從圖中的某個頂點(diǎn)V出發(fā)，訪問之；并將其訪問標(biāo)志置為已被訪問，即visited[i]=1；（2）依次訪問頂點(diǎn)V的各個未被訪問過的鄰接點(diǎn)，將V的全部鄰接點(diǎn)都訪問到；（3）分別從這些鄰接點(diǎn)出發(fā)，依次訪問它們的未被訪問過的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直到圖中所有已被訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問到。

依此類推，直到圖中所有頂點(diǎn)都被訪問完為止。2022/10/28371．廣度優(yōu)先搜索思想2022/10/2237

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

廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先搜索的示例2022/10/2838廣度優(yōu)先搜索在搜索訪問一層時，需要記住已被訪問的頂點(diǎn)，廣度優(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)對所有x的鄰接點(diǎn)wifvisited[w]=0then（a）訪問w;（b）visited[w]=1;（c）insert(Queue,f,r,w);//w進(jìn)隊(duì)列

2022/10/2839廣度優(yōu)先搜索過程可描述為：2022/10/2239以鄰接表為存儲結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法如下：#defineMAXV<最大頂點(diǎn)數(shù)>voidbfs(ALGraph*g,intv){ArcNode*p;intqueue[MAXV];//定義存放隊(duì)列的數(shù)組

intvisited[MAXV]；//定義存放結(jié)點(diǎn)的訪問標(biāo)志的數(shù)組

intf=0,r=0,x,i;//隊(duì)列頭尾指針初始化，把隊(duì)列置空

for(i=0,i<g->n;i++)//訪問標(biāo)志數(shù)組初始化

visited[i]=0;printf(“％d”,v);//訪問初始頂點(diǎn)vvisited[v]=1;//置已訪問標(biāo)記

r=(r+1)％MAXV;queue[r]=v;//v進(jìn)隊(duì)

while(f!=r){//若隊(duì)列不空時循環(huán)

f=(f+1)％MAXV;x=queuet[f];//出隊(duì)并賦給xp=g->adjlist[x].firstarc;//找與頂點(diǎn)x鄰接的第一個頂點(diǎn)

2022/10/2840以鄰接表為存儲結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法如下：2022/10p=g->adjlist[x].firstarc;//找與頂點(diǎn)x鄰接的第一個頂點(diǎn)

while(p!=NULL){if(visited[p->adjvex]==0)//若當(dāng)前鄰接點(diǎn)未被訪問{visited[p->adjvex]=l;//置該頂點(diǎn)已被訪問的標(biāo)志

printf(“％d”，p->adjvex);//訪問該頂點(diǎn)

r=(r+1)％MAXV;queue[r]=p->adjvex;//該頂點(diǎn)進(jìn)隊(duì)}

p=p->nextarc;//找下一個鄰接點(diǎn)}}}

//w進(jìn)隊(duì)列

2022/10/2841p=g->adjlist[x].firstarc;202算法分析：如果使用鄰接表表示圖，則循環(huán)的總時間代價為d0+d1+…+dn-1=O(e)，其中的di是頂點(diǎn)i的度。如果使用鄰接矩陣，則對于每一個被訪問過的頂點(diǎn)，循環(huán)要檢測矩陣中的n個元素，總的時間代價為O(n2)。2022/10/2842算法分析：如果使用鄰接表表示圖，則循環(huán)的總時間代價為6.2.3連通分支/*程序6-3求連通分支的算法*/voidconnected(void){inti;for(i=0;i<n;i++)if(!visited[i]){dfs(i);printf(“\n”);}}2022/10/28436.2.3連通分支/*程序6-3求連通分支的算法*/206.2.4生成樹

1.生成樹在一個無向連通圖G中，其所有頂點(diǎn)和遍歷該圖經(jīng)過的所有邊所構(gòu)成的子圖G′稱做圖G的生成樹。一個圖可以有多個生成樹，從不同的頂點(diǎn)出發(fā)，采用不同的遍歷順序，遍歷時所經(jīng)過的邊也就不同，例如圖7-12的(b)和(c)為圖7-12(a)的兩棵生成樹。其中(b)是通過DFS得到的，稱為深度優(yōu)先生成樹；(c)是通過BFS得到的，稱為廣度優(yōu)先生成樹。

圖6-12生成樹

2022/10/28446.2.4生成樹1.生成樹圖6-12生成樹20在圖論中，常常將樹定義為一個無回路連通圖。一個帶權(quán)的無向連通圖，其每個生成樹所有邊上的權(quán)值之和可能不同，我們把所有邊上權(quán)值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實(shí)際應(yīng)用。例如，通訊線路鋪設(shè)造價最優(yōu)問題。最小生成樹的的約束條件：1.只能使用圖中的邊2.只能使用恰好n-1條邊3.只能使用無回路的邊所以生成樹是連通圖中的極小連通子圖.不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。如深度優(yōu)先生成樹、廣度優(yōu)先生成樹6.3最小生成樹

2022/10/2845在圖論中，常常將樹定義為一個無回路連通圖。一個構(gòu)造最小生成樹的算法有很多，下面主要介紹克魯斯卡爾(Kruskal)算法和普里姆(Prim)算法。

程序6-7克魯斯卡爾(Kruskal)算法克魯斯卡爾算法是一種按權(quán)值遞增的次序選擇合適的邊來構(gòu)造最小生成樹的方法。

算法的基本思想：在圖中任取一個頂點(diǎn)K作為開始點(diǎn)，令U={k}，W=V-U，其中V為圖中所有頂點(diǎn)集，然后找一個頂點(diǎn)在U中，另一個頂點(diǎn)在W中的邊中最短的一條，找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點(diǎn)全部加入U集合中，并從W中刪去這些頂點(diǎn)，然后重新調(diào)整U中頂點(diǎn)到W中頂點(diǎn)的距離,使之保持最小，再重復(fù)此過程，直到W為空集止。2022/10/2846構(gòu)造最小生成樹的算法有很多，下面主要介紹克魯斯卡爾(Kr程序6-7克魯斯卡爾(Kruskal)算法T={}While(Tcontainslessthann-1edges&&Eisnotempty){choosealeastcostedge(v,w)fromE;delete(v,w)fromE;if((v,w)doesnotcreateacycleinT)add(v,w)toT;elsediscard(v,w);}If(Tcontainsfewerthann-1edges)printf(“Nospanningtree\n”);如果給定帶權(quán)無向連通圖G有e條邊，且邊已經(jīng)按權(quán)值遞增的次序存放在數(shù)組E中，則用克魯斯卡爾算法構(gòu)造最小生成樹的時間復(fù)雜度為O(e)?？唆斔箍査惴ǖ臅r間復(fù)雜度與邊數(shù)e有關(guān)，該算法適合于求邊數(shù)較少的帶權(quán)無向連通圖的最小生成樹。

2022/10/2847程序6-7克魯斯卡爾(Kruskal)算法如果給應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程:2022/10/2848應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程:2022/10/22為實(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)個數(shù)，e為圖G的邊數(shù)?？唆斔箍査惴ㄈ缦拢?defineMAXE<最大邊數(shù)>#defineMAXV<最大頂點(diǎn)數(shù)>typedefstruct{intvex1;//邊的起始頂點(diǎn)intvex2;//邊的終止頂點(diǎn)intweight;//邊的權(quán)值}Edge;Voidkruskal(EdgeE[],intn,inte){inti,j,m1,m2,sn1,sn2,k;intvset[MAXV];for(i=0;i<n;i++)//初始化輔助數(shù)組

vset[i]=i;

2022/10/2849為實(shí)現(xiàn)克魯斯卡爾算法需設(shè)置一維輔助數(shù)組E，按權(quán)值從小到大的順k=1;//表示當(dāng)前構(gòu)造最小生成樹的第k條邊，初值為1

j=0;//E中邊的下標(biāo)，初值為0while(k<e)//生成的邊數(shù)小于e時繼續(xù)循環(huán){ml=E[j].vex1;m2=E[j].vex2;//取一條邊的兩個鄰接點(diǎn)

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

if(sn1!=sn2)//兩頂點(diǎn)分屬于不同的集合，該邊是最小生成樹的一條邊

{printf(“(m1，m2)：％d＼n”,E[j].weight);k++;//生成邊數(shù)增lfor(i=0;i<n;i++)//兩個集合統(tǒng)一編號

if(vset[i]=//集合編號為sn2的改為sn1vset[i]=sn1;}j++;//掃描下一條邊}}2022/10/2850k=1;//表示當(dāng)前構(gòu)造最小生成樹的第k

程序6-8普里姆(Prim)算法基本思想：是按逐個將頂點(diǎn)連通的方式來構(gòu)造最小生成樹的。從只包含一個頂點(diǎn)的樹T開始，把一條代價最小的邊(u,v)，加入T中，使T∪{(u,v)}仍是一顆樹。重復(fù)上述過程只到包含n-1條邊為止。形式化的算法描述：T={}；

TV={0}；

while(Tcontainsfewerthann-1edges){let(u,v)betheleastcostedgesuchthatu∈TVandv∈TV;if(thereisnosuchedge)break;addvtoTV;add(u,v)toT;}if(Tcontainsfewerthann-1edges)printf(“Nospanningtree\n”);}2022/10/2851程序6-8普里姆(Prim)算法2022/10/22應(yīng)用普里姆(Prim)構(gòu)造最小生成樹的過程:012345610201345610252501234561022250123456102212a)b)c)d)e)f)2250134561022122501234561022122022/10/2852應(yīng)用普里姆(Prim)構(gòu)造最小生成樹的過程:01234561Sollin算法：教材P183初始狀態(tài)同前圖，此時森林中每個棵樹是單獨(dú)一個頂點(diǎn)。下一步為每個頂點(diǎn)選邊，分別是：(0,5),(1,6),(2,3),(3,2),(4,3),(5,0),(6,1)去掉重復(fù)的邊后：(0,5),(1,6),(2,3),(4,3)得到a)森林，再加上(5,4),(1,2)得到b)圖:a)b)25012345610221216140123456102212142022/10/2853Sollin算法：教材P183a)b)2501234566.4最短路徑

與傳遞閉包交通網(wǎng)絡(luò)中常常提出這樣的問題：從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短?若兩個頂點(diǎn)之間沒有邊，則認(rèn)為兩個頂點(diǎn)無通路，但有可能有間接通路(從其它頂點(diǎn)達(dá)到)。路徑上的開始頂點(diǎn)(出發(fā)點(diǎn))稱為源點(diǎn)，路徑上的最后一個頂點(diǎn)稱為終點(diǎn)，并假定討論的權(quán)值不能為負(fù)數(shù)。最短路徑：如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。對于帶權(quán)的圖，通常把一條路徑上所經(jīng)過邊或弧上的權(quán)值之和定義為該路徑的路徑長度。從一個頂點(diǎn)到另一個頂點(diǎn)可能存在著多條路徑，把路徑長度最短的那條路徑稱為最短路徑，其路徑長度稱為最短路徑長度。無權(quán)圖實(shí)際上是有權(quán)圖的一種特例，我們可以把無權(quán)圖的每條邊或弧的權(quán)值看成是l，每條路徑上所經(jīng)過的邊或弧數(shù)即為路徑長度。2022/10/28546.4最短路徑與傳遞閉包交通網(wǎng)絡(luò)中常常提出這樣6.4.1邊上權(quán)值非負(fù)情形的單源最短路徑問題—Dijkstra算法(貪心算法)迪杰斯特拉6.4.2所有頂點(diǎn)之間的最短路徑—Floyd算法邊上權(quán)值非負(fù)情形的單源最短路徑問題問題的提法：給定一個帶權(quán)有向圖D與源點(diǎn)v，求從v到D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。2022/10/28556.4.1邊上權(quán)值非負(fù)情形的單源最短路徑問題2022/106.4.1求一頂點(diǎn)（單源點(diǎn)）到其余頂點(diǎn)的最短路徑

單源點(diǎn)最短路徑是指：給定一個出發(fā)點(diǎn)(單源點(diǎn))和一個有向網(wǎng)G=(V，E),求出源點(diǎn)到其它各頂點(diǎn)之間的最短路徑。迪杰斯特拉(Dijkstra)在做了大量觀察后,首先提出了按路徑長度遞增產(chǎn)生各頂點(diǎn)的最短路徑算法,我們稱之為迪杰斯特拉算法。算法的基本思想是:設(shè)置并逐步擴(kuò)充一個集合S，存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S，其中V為網(wǎng)中所有頂點(diǎn)集合。按最短路徑長度遞增的順序逐個以V-S中的頂點(diǎn)加到S中，直到S中包含全部頂點(diǎn)，而V-S為空。2022/10/28566.4.1求一頂點(diǎn)（單源點(diǎn)）到其余頂點(diǎn)的最短路徑2022具體做法是:設(shè)源點(diǎn)為V0,則S中只包含頂點(diǎn)V0，令W=V-S，則W中包含除V0外圖中所有頂點(diǎn)，V0對應(yīng)的距離值為0，W中頂點(diǎn)對應(yīng)的距離值是這樣規(guī)定的：若圖中有弧<V0,Vj>則Vj頂點(diǎn)的距離為此弧權(quán)值，否則為∞(一個很大的數(shù))，然后每次從W中的頂點(diǎn)中選一個其距離值為最小的頂點(diǎn)Vm加入到S中，每往S中加入一個頂點(diǎn)Vm，就要對W中的各個頂點(diǎn)的距離值進(jìn)行一次修改。若加進(jìn)Vm做中間頂點(diǎn)，使<V0,Vm>+<Vm,Vj>的值小于<V0,Vj>值，則用<V0,Vm>+<Vm,Vj>代替原來Vj的距離，修改后再在W中選距離值最小的頂點(diǎn)加入到S中，如此進(jìn)行下去，直到S中包含了圖中所有頂點(diǎn)為止。實(shí)現(xiàn)的算法：P185程序6-9,6-10,6-112022/10/2857具體做法是:設(shè)源點(diǎn)為V0,則S中只包含頂點(diǎn)V0，令W

程序6-10單源最短路徑算法

voidshortestpath(intv,intcost[][max_vertices],intdistance[],intn,shortintfound[]){inti,u,w;

for(i=0;i<n;i++){found[i]=FALSE;distance[i]=cost[v][i];}found[v]=TRUE;distance[v]=0;

for(i=0;i<n-2;i++)u=choose(distance,n,found);found[u]=TRUE;for(w=0;w<n;w++)if(!found[w])if(distance[u]+cost[u][w]<distance[w])distance[w]=distance[u]+cost[u][w];}}2022/10/2858程序6-10單源最短路徑算法2022/10/225圖6-16帶權(quán)有向圖

設(shè)G=(V，E)是一個帶權(quán)有向圖，指定的頂點(diǎn)v0為源點(diǎn)，求v0到圖的其余各頂點(diǎn)的最短路徑。如圖7-16所示，若以頂點(diǎn)0為v0，它到其余各頂點(diǎn)的最短路徑分別為：頂點(diǎn)0頂點(diǎn)1：無路徑頂點(diǎn)0頂點(diǎn)2：最短路徑為（0，2），最短路徑長度為10頂點(diǎn)0頂點(diǎn)4：最短路徑為（0，4），最短路徑長度為30頂點(diǎn)0頂點(diǎn)3：最短路徑為（0，4，3），最短路徑長度為50頂點(diǎn)0頂點(diǎn)5：最短路徑為（0，4，3，5），最短路徑長度為60

2022/10/2859圖6-16帶權(quán)有向圖設(shè)G=(V，E)是一個帶權(quán)有向圖，指從以上圖6-16的最短路徑可以看出：1)最短路徑并不一定是經(jīng)過邊或弧數(shù)最少的路徑。如從頂點(diǎn)0到頂點(diǎn)5的路徑（0，5）長度為100，路徑（0，4，5）長度為90，路徑（0，2，3，5）長度為70，路徑（0，4，3，5）長度為60，其中最短路徑為（0，4，3，5），最短路徑長度為60。2)這些最短路徑中，長度最短的路徑上只有一條弧，且它的權(quán)值在從源點(diǎn)出發(fā)的所有弧的權(quán)值中最小。如從源點(diǎn)0出發(fā)有3條弧，其中以弧<0，2>的權(quán)值為最小。此時（0，2）不僅是頂點(diǎn)0到頂點(diǎn)2的一條最短路徑，而且它在從源點(diǎn)0到其它各頂點(diǎn)的最短路徑中長度最短。3)按照路徑長度遞增的次序產(chǎn)生最短路徑。求得第二條最短路徑（0，4）；之后求得第三條最短路徑（0，4，3），它經(jīng)過已求出的第二條最短路徑（0，4）到達(dá)頂點(diǎn)3；求得的第四條最短路徑（0，4，3，5），經(jīng)過已求出的第三條最短路徑（0，4，3）到達(dá)頂點(diǎn)5。

2022/10/2860從以上圖6-16的最短路徑可以看出：2022/10/2260迪杰斯特拉算法的求解過程：2022/10/2861迪杰斯特拉算法的求解過程：2022/10/2261圖6-17迪杰斯特拉算法求最短路徑過程及結(jié)果在狄克斯特拉算法中，求一條最短路徑所花費(fèi)的時間：從V-S中選取具有最小距離的頂點(diǎn)vk花費(fèi)時間O(n)；修改V-S中頂點(diǎn)的距離花費(fèi)時間O(n)；輸出最短路徑花費(fèi)時間O(n)。因此求出n-1條最短路徑的時間復(fù)雜度為O(n2)。

2022/10/2862圖6-17迪杰斯特拉算法求最短路徑過程及結(jié)果在狄克斯6.4.2所有頂點(diǎn)對之間的最短路徑

頂點(diǎn)對之間的最短路徑是指：對于給定的有向網(wǎng)G=(V,E),對G中任意一對頂點(diǎn)有序?qū)、W(V≠W),找出V到W和W到V的最短距離。解決此問題的一個有效方法是:輪流以每一個頂點(diǎn)為源點(diǎn),重復(fù)執(zhí)行迪杰斯特拉算法n次,即可求得每一對頂點(diǎn)之間的最短路徑,總的時間復(fù)雜度為O(n3)

帶權(quán)的鄰接矩陣來存儲表示圖G，若i=j,cost[i][j]=0,右<i,j>i≠j不在G中則設(shè)置cost[i][j]為一個充分大的數(shù)。令A(yù)(k)[i][j]表示從頂點(diǎn)i出發(fā)，只經(jīng)過序號小于等于k的中間頂點(diǎn),到達(dá)頂點(diǎn)j的最距離。A(k)[i][j]=min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}其中k=1,2,…,n2022/10/28636.4.2所有頂點(diǎn)對之間的最短路徑帶權(quán)的鄰接矩例6-5下圖給出了一個有向圖及其代價鄰接矩陣A-1，對于這個圖：A(1)[0][2]不等于min{A(1)[0][2],A(0)[0][1]+A(0)[1][2]}，實(shí)際上A(1)[0][2]=-∞0121-2101∞-201∞∞∞程序6-12所有頂點(diǎn)對之間的最短路徑算法

voidallcosts(intcost[][max_vertices],intdistance[][max_verticers],intn){inti,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++)distance[i][j]=cost[i][j];for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(distance[i][k]+distance[k][j]<distance[i][j])distance[i][j])=distance[i][k]+distance[k][j];}2022/10/2864例6-5下圖給出了一個有向圖及其代價鄰接矩陣A-1，對于1.拓?fù)渑判?/p>

通常我們把計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都當(dāng)成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動。這些活動完成時，整個工程也就完成了。例如，計(jì)算機(jī)專業(yè)學(xué)生的課程開設(shè)可看成是一個工程，每一門課程就是工程中的活動，圖7-21給出了若干門所開設(shè)的課程，其中有些課程的開設(shè)有先后關(guān)系，有些則沒有先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開設(shè)，如開設(shè)數(shù)據(jù)結(jié)構(gòu)課程之前必須先學(xué)完程序設(shè)計(jì)基礎(chǔ)及離散數(shù)學(xué)，而開設(shè)離散數(shù)學(xué)則必須先并行學(xué)完高等數(shù)學(xué)、程序設(shè)計(jì)基礎(chǔ)課程。6.5活動網(wǎng)絡(luò)-拓?fù)渑判?/p>

2022/10/28651.拓?fù)渑判?.5活動網(wǎng)絡(luò)-拓?fù)渑判?022/10/2圖6-21課程名稱及相應(yīng)的課程安排次序

圖6-22課程安排的AOV網(wǎng)在圖6-22中，我們用一種有向圖來表示課程開設(shè)，在這種有向圖中，頂點(diǎn)表示活動，有向邊表示活動的優(yōu)先關(guān)系，這有向圖叫做頂點(diǎn)表示活動的網(wǎng)絡(luò)(ActireOnVertices)簡稱為AOV網(wǎng)。2022/10/2866圖6-21課程名稱及相應(yīng)的課程安排次序圖6-22課程安AOV網(wǎng)——ActivityOnVertexNetwork[頂點(diǎn)表示活動的網(wǎng)]用頂點(diǎn)表示活動，用弧表示活動間的優(yōu)先關(guān)系的有向圖，稱為AOV在AOV網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán)。因?yàn)榄h(huán)的存在意味著某項(xiàng)活動將以自己為先決條件，顯然無法形成拓?fù)湫蛄小Ｍ負(fù)渑判颍和ǔＴ贏OV網(wǎng)中，將所有活動排列成一個拓?fù)湫蛄械倪^程叫做拓?fù)渑判?TopologicalSort)。當(dāng)且僅當(dāng)頂點(diǎn)序列滿足下列條件：有向圖G中存在從頂點(diǎn)vi到vj的一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必須排在vj之前。拓?fù)渑判蚪Y(jié)果不唯一，如圖6-22

可得一個拓?fù)湫蛄校篊1，C3，C2，C4，C7，C6，C5也可得到另一個拓?fù)湫蛄校篊2，C7，C1，C3，C4，C5，C62022/10/2867AOV網(wǎng)——ActivityOnVertexNetwo拓?fù)渑判虻姆椒ǎ狠斎階OV網(wǎng)絡(luò)。令n為頂點(diǎn)個數(shù)。 在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點(diǎn),并輸出之;從圖中刪去該頂點(diǎn),同時刪去所有它發(fā)出的有向邊;重復(fù)以上、步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?；或圖中剩下的頂點(diǎn)都有前驅(qū)而不能刪除，則必包含環(huán)路6-13算法：for(i=0;i<n;i++){ifeveryvertexhasapredecessor{fprintf(stderr,”Networkcycle.”);Pickavertexvthathasnopredecessors;outputv;Deletevandalledgesleadingoutofvfromthenetwork;}2022/10/2868拓?fù)渑判虻姆椒ǎ?022/10/2268拓?fù)渑判虻倪^程2022/10/2869拓?fù)渑判虻倪^程2022/10/2269最后得到的拓?fù)溆行蛐蛄袨镃4,C0,C3,C2,C1,C5。拓樸排序算法的實(shí)現(xiàn)：使用鄰接矩陣表示2022/10/2870最后得到的拓?fù)溆行蛐蛄袨镃4,C0,C3,C2

【例6-3】請給出圖6-24所示的有向圖G的拓?fù)渑判蜻^程。圖6-24有向圖G及其鄰接矩陣

拓?fù)湫蛄校?612342022/10/2871【例6-3】請給出圖6-24所示的有向圖G的拓?fù)渑判蜻^程。

【解】依據(jù)拓?fù)渑判蛩惴?，將圖6-24中入度為0的兩個頂點(diǎn)l和5相繼入棧；頂點(diǎn)5出棧，輸出，且以頂點(diǎn)5為尾的弧的另一頂點(diǎn)入度減一，如另一頂點(diǎn)2的入度值由2變?yōu)?，另一頂點(diǎn)6的入度值由1變?yōu)?。將入度為0的頂點(diǎn)6入棧；頂點(diǎn)6出棧，輸出，且以頂點(diǎn)6為尾的弧的另一頂點(diǎn)入度減一，如另一頂點(diǎn)4的入度值由2變?yōu)?；依次類推得到拓?fù)湫蛄校?61234，拓?fù)渑判蜻^程棧的變化見圖6-25。入度為0的頂點(diǎn)可以按不同順序入棧，因此還可以得到其它拓?fù)湫蛄校?52364，152634，156234，512364，516234，512634。

圖6-25拓?fù)渑判蜻^程的棧

2022/10/2872【解】依據(jù)拓?fù)渑判蛩惴?，將圖6-24中入度為0的兩個頂點(diǎn)l6.5.2AOE網(wǎng)-關(guān)鍵路徑

AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖。AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：(1)完成整個工程至少需要多少時間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?(2)為縮短完成工程所需的時間,應(yīng)當(dāng)加快哪些活動?在AOE網(wǎng)絡(luò)中,有些活動順序進(jìn)行，有些活動并行進(jìn)行。從源點(diǎn)到各個頂點(diǎn)，以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長度也可能不同。只有各條路徑上所有活動都完成了，整個工程才算完成。因此，完成整個工程所需的時間取決于從源點(diǎn)到匯點(diǎn)的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(CriticalPath)。2022/10/28736.5.2AOE網(wǎng)-關(guān)鍵路徑 AOE網(wǎng)是一個帶權(quán)的有向無圖6-26是一個AOE網(wǎng)，該網(wǎng)中有11個活動和9個事件。每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始。如事件v4表示a3和a4活動已經(jīng)完成，a6和a7活動可以開始。每個弧上的權(quán)值表示完成相應(yīng)活動所需要的時間，如完成活動a0需要6天，a7需要7天。圖6-26AOE網(wǎng)

V8V4V1V6V3a0=6a9=2a5=2a2=5a3=1a4=1V0a1=4V2V7V5a10=4a8=4a6=9a7=7AOE網(wǎng)常用于表示工程的計(jì)劃或進(jìn)度。AOE網(wǎng)存在唯一的入度為0的開始點(diǎn)（又稱源點(diǎn)）和唯一的出度為0的結(jié)束點(diǎn)（又稱匯點(diǎn)），圖6-26的AOE網(wǎng)從事件v0開始，以事件v8結(jié)束。同時AOE網(wǎng)應(yīng)當(dāng)是無環(huán)的。

2022/10/2874圖6-26是一個AOE網(wǎng)，該網(wǎng)中有11個活動和9個事件定義幾個與計(jì)算關(guān)鍵活動有關(guān)的量：

事件Vi

的最早可能開始時間e(i)

是從源點(diǎn)V0到頂點(diǎn)Vi的最長路徑長度。

事件Vi的最遲允許開始時間l[i]

是在保證匯點(diǎn)Vn-1在Ve[n-1]時刻完成的前提下，事件Vi

的允許的最遲開始時間。

活動ak的最早可能開始時間e[k]

設(shè)活動ak在邊<

Vi,Vj>上，則e[k]是從源點(diǎn)V0到頂點(diǎn)Vi

的最長路徑長度。因此,e[k]=e[i]。

活動ak的最遲允許開始時間l[k]

l[k]是在不會引起時間延誤的前提下，該活動允許的最遲開始時間。

l[k]=l[j]-dur(<i,j>)。

其中，dur(<i,j>)是完成ak所需的時間V8V4V1V6V3a0=6a9=2a5=2a2=5a3=1a4=1V0a1=4V2V7V5a10=4a8=4a6=9a7=72022/10/2875定義幾個與計(jì)算關(guān)鍵活動有關(guān)的量：事件Vi的最早可能開始時

時間余量l[k]-e[k]

表示活動ak的最早可能開始時間和最遲允許開始時間的時間余量。l[k]==e[k]表示活動ak是沒有時間余量的關(guān)鍵活動。為找出關(guān)鍵活動,需要求各個活動的e[k]與l[k]，以判別是否l[k]==e[k].為求得e[k]與l[k]，需要先求得從源點(diǎn)V0到各個頂點(diǎn)Vi的e[i]和l[i]。設(shè)活動ai(i=1,2,…,e)在帶權(quán)有向邊<

Vk,Vl>上,i表示活動ai，它的持續(xù)時間用dur(<Vk,Vl>)表示，則有

early(i)=earliest[Vk]；

late(i)=latest[Vl]-dur(<Vk,Vl>)；k=1,2,…,e。計(jì)算關(guān)鍵路徑的算法:計(jì)算關(guān)鍵路徑時，可以一邊進(jìn)行拓?fù)渑判蛞贿呌?jì)算各頂點(diǎn)的earliest[Vi]。為了簡化算法，假定在求關(guān)鍵路徑之前已經(jīng)對各頂點(diǎn)實(shí)現(xiàn)了拓?fù)渑判?，并按拓?fù)溆行虻捻樞驅(qū)Ω黜旤c(diǎn)重新進(jìn)行了編號。算法在求earliest[Vi],i=0,1,…,n-1時按拓?fù)溆行虻捻樞蛴?jì)算，在求latest[Vi],i=n-1,n-2,…,0時按逆拓?fù)溆行虻捻樞蛴?jì)算。2022/10/2876時間余量l[k]-e[k]設(shè)活動ai(i=1

【例6-4】圖6-29是一個具有8個活動和6個事件的AOE網(wǎng)，試求其關(guān)鍵路徑?！窘狻坑蒭(i)和l(i)的遞推公式，依次求出所有事件的最早發(fā)生時間e(i)和最遲發(fā)生時間l(i)，如下：圖6-29AOE網(wǎng)

頂點(diǎn)最早發(fā)生時間e(i)最遲發(fā)生時間l(i)v1v6v5v4v3v208662387624