數(shù)據(jù)結(jié)構(gòu)第七章 圖

第7章圖本章中介紹下列主要內(nèi)容：圖的定義圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷操作圖的幾個(gè)典型問(wèn)題第7章圖

圖(Graph)是一種比線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

線性結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的一對(duì)一關(guān)系。在這種結(jié)構(gòu)中，除第一個(gè)和最后一個(gè)元素外，任何一個(gè)元素都有唯一的一個(gè)直接前驅(qū)和直接后繼。

樹(shù)結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的一對(duì)多的關(guān)系。在這種結(jié)構(gòu)中，每個(gè)元素對(duì)下(層)可以有0個(gè)或多個(gè)元素相聯(lián)系，對(duì)上(層)只有唯一的一個(gè)元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。圖結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的多對(duì)多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個(gè)元素之間可能存在關(guān)系。即結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。圖的應(yīng)用極為廣泛，已滲入到諸如語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支。第7章圖7.1

圖的基本概念7.1.1圖的定義和術(shù)語(yǔ)一個(gè)圖(G)定義為一個(gè)偶對(duì)(V,E)，記為G=(V,E)。其中：V是頂點(diǎn)(Vertex)的非空有限集合，記為V(G)；E是無(wú)序集V&V的一個(gè)子集，記為E(G)，其元素是圖的弧(Arc)。將頂點(diǎn)集合為空的圖稱為空?qǐng)D。其形式化定義為：G=(V，E)V={v|vdataobject}E={<v,w>|v,wV∧p(v,w)}P(v,w)表示從頂點(diǎn)v到頂點(diǎn)w有一條直接通路。

弧(Arc)

：表示兩個(gè)頂點(diǎn)v和w之間存在一個(gè)關(guān)系，用頂點(diǎn)偶對(duì)<v,w>表示。通常根據(jù)圖的頂點(diǎn)偶對(duì)將圖分為有向圖和無(wú)向圖。

有向圖(Digraph)：

若圖G的關(guān)系集合E(G)中，頂點(diǎn)偶對(duì)<v,w>的v和w之間是有序的，稱圖G是有向圖。在有向圖中，若<v,w>E(G)，表示從頂點(diǎn)v到頂點(diǎn)w有一條弧。其中：v稱為弧尾(tail)或始點(diǎn)(initial

node)，w稱為弧頭(head)或終點(diǎn)(terminalnode)

。定義和術(shù)語(yǔ)（2）無(wú)向圖(Undigraph)：若圖G的關(guān)系集合E(G)中，頂點(diǎn)偶對(duì)<v,w>的v和w之間是無(wú)序的，稱圖G是無(wú)向圖。在無(wú)向圖中，若<v,w>E(G)，有<w,v>E(G)，即E(G)是對(duì)稱，則用無(wú)序?qū)?v,w)表示v和w之間的一條邊(Edge)，因此(v,w)和(w,v)代表的是同一條邊。定義和術(shù)語(yǔ)（3）

例1：設(shè)有有向圖G1和無(wú)向圖G2，形式化定義：G1=(V1，E1)V1={a,b,c,d,e}E1={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>}G2=(V2，E2)V2={a,b,c,d}E2={(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)}abcd(b)無(wú)向圖G2

(a)有向圖G1

acbde

完全無(wú)向圖：對(duì)于無(wú)向圖，若圖中頂點(diǎn)數(shù)為n，用e表示邊的數(shù)目，則e[0，n(n-1)/2]。具有n(n-1)/2條邊的無(wú)向圖稱為完全無(wú)向圖。

完全無(wú)向圖另外的定義是：對(duì)于無(wú)向圖G=(V，E)，若vi，vj

V，當(dāng)vi≠vj時(shí)，有(vi,vj)E，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條無(wú)向邊，這樣的無(wú)向圖稱為完全無(wú)向圖。定義和術(shù)語(yǔ)（4）完全有向圖：對(duì)于有向圖，若圖中頂點(diǎn)數(shù)為n，用e表示弧的數(shù)目，則e[0，n(n-1)]。具有n(n-1)條邊的有向圖稱為完全有向圖。完全有向圖另外的定義是：對(duì)于有向圖G=(V，E)，若vi，vjV

，當(dāng)vi≠vj時(shí)，有<vi,vj>E∧<vj,vi>E，即圖中任意兩個(gè)不同的頂點(diǎn)間都有一條弧，這樣的有向圖稱為完全有向圖。定義和術(shù)語(yǔ)（5）有很少邊或弧的圖（e<n㏒n）的圖稱為稀疏圖，反之稱為稠密圖。

權(quán)(Weight)：與圖的邊和弧相關(guān)的數(shù)。權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。子圖和生成子圖：設(shè)有圖G=(V，E)和G’=(V’，E’)，若V’V且E’E，則稱圖G’是G的子圖；若V’=V且E’E，則稱圖G’是G的一個(gè)生成子圖。定義和術(shù)語(yǔ)（6）頂點(diǎn)的鄰接(Adjacent)：對(duì)于無(wú)向圖G=(V，E)，若邊(v,w)E，則稱頂點(diǎn)v和w互為鄰接點(diǎn)，即v和w相鄰接。邊(v,w)依附(incident)與頂點(diǎn)v和w。對(duì)于有向圖G=(V，E)，若有向弧<v,w>E，則稱頂點(diǎn)v

“鄰接到”頂點(diǎn)w，頂點(diǎn)w“鄰接自”頂點(diǎn)v，弧<v,w>與頂點(diǎn)v和w

“相關(guān)聯(lián)”。頂點(diǎn)的度、入度、出度：對(duì)于無(wú)向圖G=(V，E)，viV，圖G中依附于vi的邊的數(shù)目稱為頂點(diǎn)vi的度(degree)，記為TD(vi)。定義和術(shù)語(yǔ)（7）

顯然，在無(wú)向圖中，所有頂點(diǎn)度的和是圖中邊的2倍。即∑TD(vi)=2e(i=1,2,…,n，e為圖的邊數(shù))。對(duì)有向圖G=(V，E)，若viV，圖G中以vi作為起點(diǎn)的有向邊(弧)的數(shù)目稱為頂點(diǎn)vi的出度(Outdegree)，記為OD(vi)；以vi作為終點(diǎn)的有向邊(弧)的數(shù)目稱為頂點(diǎn)vi的入度(Indegree)，記為ID(vi)。頂點(diǎn)vi的出度與入度之和稱為vi的度，記為TD(vi)。即

TD(vi)=OD(vi)+ID(vi)

定義和術(shù)語(yǔ)（8）路徑(Path)、路徑長(zhǎng)度、回路(Cycle)：對(duì)無(wú)向圖G=(V，E)，若從頂點(diǎn)vi經(jīng)過(guò)若干條邊能到達(dá)vj，稱頂點(diǎn)vi和vj是連通的，又稱頂點(diǎn)vi到vj有路徑。對(duì)有向圖G=(V，E)，從頂點(diǎn)vi到vj有有向路徑，指的是從頂點(diǎn)vi經(jīng)過(guò)若干條有向邊(弧)能到達(dá)vj?；蚵窂绞菆DG中連接兩頂點(diǎn)間所經(jīng)過(guò)的頂點(diǎn)序列。Path=vi0vi1…vim，vijV且(vij-1,vij)Ej=1,2,…,m定義和術(shù)語(yǔ)（9）路徑上邊或有向邊(弧)的數(shù)目稱為該路徑的長(zhǎng)度。在一條路徑中，若沒(méi)有重復(fù)相同的頂點(diǎn)，該路徑稱為簡(jiǎn)單路徑；第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路(環(huán))；在一個(gè)回路中，若除第一個(gè)與最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路(簡(jiǎn)單環(huán))。定義和術(shù)語(yǔ)（10）連通圖、圖的連通分量：對(duì)無(wú)向圖G=(V，E)，若vi，vj

V，vi和vj都是連通的，則稱圖G是連通圖，否則稱為非連通圖。若G是非連通圖，則極大的連通子圖稱為G的連通分量。對(duì)有向圖G=(V，E)，若vi，vj

V，都有以vi為起點(diǎn)，

vj

為終點(diǎn)以及以vj為起點(diǎn)，vi為終點(diǎn)的有向路徑，稱圖G是強(qiáng)連通圖，否則稱為非強(qiáng)連通圖。若G是非強(qiáng)連通圖，則極大的強(qiáng)連通子圖稱為G的強(qiáng)連通分量。

“極大”的含義：指的是對(duì)子圖再增加圖G中的其它頂點(diǎn)，子圖就不再連通。定義和術(shù)語(yǔ)（11）

生成樹(shù)、生成森林：一個(gè)連通圖(無(wú)向圖)的生成樹(shù)是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)和只有足以構(gòu)成一棵樹(shù)的n-1條邊，稱為圖的生成樹(shù)，如圖7-2所示。關(guān)于無(wú)向圖的生成樹(shù)的幾個(gè)結(jié)論：

◆

一棵有n個(gè)頂點(diǎn)的生成樹(shù)有且僅有n-1條邊；

◆

如果一個(gè)圖有n個(gè)頂點(diǎn)和小于n-1條邊，則是非連通圖；adbc圖7-2圖G2的一棵生成樹(shù)◆

如果多于n-1條邊，則一定有環(huán)；◆

有n-1條邊的圖不一定是生成樹(shù)。

有向圖的生成森林是這樣一個(gè)子圖，由若干棵有向樹(shù)組成，含有圖中全部頂點(diǎn)。有向樹(shù)是只有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1的有向圖，如圖7-3所示。

網(wǎng)：每個(gè)邊(或弧)都附加一個(gè)權(quán)值的圖，稱為帶權(quán)圖。帶權(quán)的連通圖(包括弱連通的有向圖)稱為網(wǎng)或網(wǎng)絡(luò)。網(wǎng)絡(luò)是工程上常用的一個(gè)概念，用來(lái)表示一個(gè)工程或某種流程，如圖7-4所示。圖7-3有向圖及其生成森林abcde(a)有向圖(b)生成森林acbde354126abcde3圖7-4帶權(quán)有向圖7.1.2

圖的抽象數(shù)據(jù)類型定義

圖是一種數(shù)據(jù)結(jié)構(gòu)，加上一組基本操作就構(gòu)成了圖的抽象數(shù)據(jù)類型。圖的抽象數(shù)據(jù)類型定義如下：ADTGraph{數(shù)據(jù)對(duì)象V：具有相同特性的數(shù)據(jù)元素集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}VR={<v,w>|<v,w>|v,wV∧p(v,w)，<v,w>表示從v到w的弧，P(v,w)定義了弧<v,w>的信息}基本操作P：Create_Graph()：圖的創(chuàng)建操作。

初始條件：無(wú)。操作結(jié)果：生成一個(gè)沒(méi)有頂點(diǎn)的空?qǐng)DG。GetVex(G,v)：求圖中的頂點(diǎn)v的值。初始條件：圖G存在，v是圖中的一個(gè)頂點(diǎn)。操作結(jié)果：生成一個(gè)沒(méi)有頂點(diǎn)的空?qǐng)DG。

……

DFStraver(G,V)：從v出發(fā)對(duì)圖G深度優(yōu)先遍歷。

初始條件：圖G存在。操作結(jié)果：對(duì)圖G深度優(yōu)先遍歷，每個(gè)頂點(diǎn)訪問(wèn)且只訪問(wèn)一次。}ADTGraph7.2圖的存儲(chǔ)結(jié)構(gòu)

圖的存儲(chǔ)結(jié)構(gòu)比較復(fù)雜，其復(fù)雜性主要表現(xiàn)在：

◆

任意頂點(diǎn)之間可能存在聯(lián)系，無(wú)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系。

◆

圖中頂點(diǎn)的度不一樣，有的可能相差很大，若按度數(shù)最大的頂點(diǎn)設(shè)計(jì)結(jié)構(gòu)，則會(huì)浪費(fèi)很多存儲(chǔ)單元，反之按每個(gè)頂點(diǎn)自己的度設(shè)計(jì)不同的結(jié)構(gòu)，又會(huì)影響操作。圖的常用的存儲(chǔ)結(jié)構(gòu)有：鄰接矩陣、鄰接鏈表、十字鏈表、鄰接多重表和邊表。7.2.1鄰接矩陣(數(shù)組)表示法基本思想：對(duì)于有n個(gè)頂點(diǎn)的圖，用一維數(shù)組vexs[n]存儲(chǔ)頂點(diǎn)信息，用二維數(shù)組A[n][n]存儲(chǔ)頂點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點(diǎn)在vexs數(shù)組中的下標(biāo)代表頂點(diǎn)，鄰接矩陣中的元素A[i][j]存放的是頂點(diǎn)i到頂點(diǎn)j之間關(guān)系的信息。

1無(wú)向圖--無(wú)權(quán)圖的鄰接矩陣

無(wú)向無(wú)權(quán)圖G=(V，E)有n(n≧1)個(gè)頂點(diǎn)，其鄰接矩陣是n階對(duì)稱方陣，如圖7-5所示。其元素的定義如下：(a)無(wú)向圖

abcd圖7-5無(wú)向無(wú)權(quán)圖的數(shù)組存儲(chǔ)(b)頂點(diǎn)矩陣vexsabcd0111101111011110(c)鄰接矩陣1若(vi,vj)E，即vi,vj鄰接0若(vi,vj)E，即vi,vj不鄰接A[i][j]=

1無(wú)向圖--帶權(quán)圖的鄰接矩陣

無(wú)向帶權(quán)圖G=(V，E)的鄰接矩陣如圖7-6所示。其元素的定義如下：(a)帶權(quán)無(wú)向圖

(b)頂點(diǎn)矩陣圖7-6無(wú)向帶權(quán)圖的數(shù)組存儲(chǔ)(c)鄰接矩陣354126abcde3vexsabcde∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞Wij

若(vi,vj)E，即vi,vj鄰接，權(quán)值為wij∞

若(vi,vj)E，即vi,vj不鄰接時(shí)A[i][j]=無(wú)向圖鄰接矩陣的特性：

◆

鄰接矩陣是對(duì)稱方陣；

◆

對(duì)于頂點(diǎn)vi，其度數(shù)是第i行的非0元素的個(gè)數(shù)；

◆

無(wú)向圖的邊數(shù)是上(或下)三角形矩陣中非0元素個(gè)數(shù)。

2有向圖--

無(wú)權(quán)圖的鄰接矩陣

若有向無(wú)權(quán)圖G=(V，E)有n(n≧1)個(gè)頂點(diǎn)，則其鄰接矩陣是n階對(duì)稱方陣，如圖7-7所示。元素定義如下：1若<vi,vj>E，從vi到vj有弧A[i][j]=0若<vi,vj>E從vi到vj

沒(méi)有弧(a)有向圖acbde圖7-7有向無(wú)權(quán)圖的數(shù)組存儲(chǔ)(b)頂點(diǎn)矩陣vexsabcde(c)鄰接矩陣0110100000000111100000010

2有向圖--帶權(quán)圖的鄰接矩陣

有向帶權(quán)圖G=(V，E)的鄰接矩陣如圖7-8所示。其元素的定義如下：wij

若<vi,vj>E，即vi,vj鄰接，權(quán)值為wij∞

若<vi,vj>E，即vi,vj不鄰接時(shí)A[i][j]=圖7-8帶權(quán)有向圖的數(shù)組存儲(chǔ)(b)頂點(diǎn)矩陣vexsabcde(c)鄰接矩陣∞62∞∞∞∞

∞

∞3∞3∞1∞∞4

∞∞5∞∞

∞∞∞(a)帶權(quán)有向圖

354126abcde3有向圖鄰接矩陣的特性：◆

對(duì)于頂點(diǎn)vi，第i行的非0元素的個(gè)數(shù)是其出度OD(vi)；第i列的非0元素的個(gè)數(shù)是其入度ID(vi)?！?/p>

鄰接矩陣中非0元素的個(gè)數(shù)就是圖的弧的數(shù)目。

3圖的鄰接矩陣的操作

圖的鄰接矩陣的實(shí)現(xiàn)比較容易，定義兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)信息(數(shù)據(jù)元素)和邊或弧的信息(數(shù)據(jù)元素之間的關(guān)系)。其存儲(chǔ)結(jié)構(gòu)形式定義如下：#defineINFINITYMAX_VAL/*最大值∞*//*根據(jù)圖的權(quán)值類型，分別定義為最大整數(shù)或?qū)崝?shù)*/#defineMAX_VEX30/*最大頂點(diǎn)數(shù)目*/typedef

enum{DG,AG,WDG,WAG}GraphKind;/*{有向圖，無(wú)向圖，帶權(quán)有向圖，帶權(quán)無(wú)向圖}*/typedef

struct

ArcCell{VRType

adj;/*弧或邊兩頂點(diǎn)關(guān)系,1或0或權(quán)值或無(wú)窮*/InfoType*Info;/*弧或邊的其它信息*/}ArcCell;/*弧或邊的結(jié)構(gòu)定義*/typedef

struct{GraphKindkind;/*圖的種類標(biāo)志*/int

vexnum,arcnum;/*圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)*/VexType

vexs[MAX_VEX];/*頂點(diǎn)向量*/ArcCell

arcs[MAX_VEX][MAX_VEX];}MGraph;/*圖的結(jié)構(gòu)定義*/利用上述定義的數(shù)據(jù)結(jié)構(gòu)，可以方便地實(shí)現(xiàn)圖的各種操作。(1)圖的創(chuàng)建AdjGraph*Create_Graph(MGraph*G){printf(“請(qǐng)輸入圖的種類標(biāo)志：”);scanf(“%d”,&G->kind);G->vexnum=0;/*初始化頂點(diǎn)個(gè)數(shù)*/return(G);}

(2)圖的頂點(diǎn)定位

圖的頂點(diǎn)定位操作實(shí)際上是確定一個(gè)頂點(diǎn)在vexs數(shù)組中的位置(下標(biāo))，其過(guò)程完全等同于在順序存儲(chǔ)的線性表中查找一個(gè)數(shù)據(jù)元素。int

LocateVex(MGraph*G,VexType*vp){intk;for(k=0;k<G->vexnum;k++)if(G->vexs[k]==*vp)return(k);return(-1);/*圖中無(wú)此頂點(diǎn)*/}

(3)向圖中增加頂點(diǎn)

向圖中增加一個(gè)頂點(diǎn)的操作，類似在順序存儲(chǔ)的線性表的末尾增加一個(gè)數(shù)據(jù)元素。int

AddVertex(MGraph*G,VexType*vp){intk,j;if(G->vexnum>=MAX_VEX){printf(“VertexOverflow!\n”);return(-1);}if(LocateVex(G,vp)!=-1){printf(“Vertexhasexisted!\n”);return(-1);}k=G->vexnum;G->vexs[G->vexnum++]=*vp;if(G->kind==DG||G->kind==AG)for(j=0;j<G->vexnum;j++)G->adj[j][k].ArcVal=G->adj[k][j].ArcVal=0;

/*是不帶權(quán)的有向圖或無(wú)向圖*/elsefor(j=0;j<G->vexnum;j++){G->adj[j][k].ArcVal=INFINITY;G->adj[k][j].ArcVal=INFINITY;

/*是帶權(quán)的有向圖或無(wú)向圖*/}return(k);}

(4)向圖中增加一條弧

根據(jù)給定的弧或邊所依附的頂點(diǎn)，修改鄰接矩陣中所對(duì)應(yīng)的數(shù)組元素。

int

AddArc(MGraph*G,ArcType*arc){intk,j;k=LocateVex(G,&arc->vex1);j=LocateVex(G,&arc->vex1);if(k==-1||j==-1){printf(“Arc’sVertexdonotexisted!\n”);return(-1);}if(G->kind==DG||G->kind==WDG){G->adj[k][j].ArcVal=arc->ArcVal;G->adj[k][j].ArcInfo=arc->ArcInfo;

/*是有向圖或帶權(quán)的有向圖*/}else{G->adj[k][j].ArcVal=arc->ArcVal;G->adj[j][k].ArcVal=arc->ArcVal;G->adj[k][j].ArcInfo=arc->ArcInfo;G->adj[j][k].ArcInfo=arc->ArcInfo;

/*是無(wú)向圖或帶權(quán)的無(wú)向圖,需對(duì)稱賦值*/}return(1);}7.2.2

鄰接鏈表法基本思想：對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。第i個(gè)單鏈表表示依附于頂點(diǎn)Vi的邊(對(duì)有向圖是以頂點(diǎn)Vi為頭或尾的弧)。

1結(jié)點(diǎn)結(jié)構(gòu)與鄰接鏈表示例

鏈表中的結(jié)點(diǎn)稱為表結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)由三個(gè)域組成，如圖7-9(a)所示。其中鄰接點(diǎn)域(adjvex)指示與頂點(diǎn)Vi鄰接的頂點(diǎn)在圖中的位置(頂點(diǎn)編號(hào))，鏈域(nextarc)指向下一個(gè)與頂點(diǎn)Vi鄰接的表結(jié)點(diǎn)，數(shù)據(jù)域(info)存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。對(duì)于無(wú)權(quán)圖，如果沒(méi)有與邊相關(guān)的其他信息，可省略此域。

每個(gè)鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)(稱為頂點(diǎn)結(jié)點(diǎn))，由兩個(gè)域組成，如圖7-9(b)所示。鏈域(firstarc)指向鏈表中的第一個(gè)結(jié)點(diǎn)，數(shù)據(jù)域(data)

存儲(chǔ)頂點(diǎn)名或其他信息。adjvexinfonextarc表結(jié)點(diǎn)：datafirstarc頂點(diǎn)結(jié)點(diǎn)：圖7-9鄰接鏈表結(jié)點(diǎn)結(jié)構(gòu)用鄰接鏈表存儲(chǔ)圖時(shí)，對(duì)無(wú)向圖，其鄰接鏈表是唯一的，如圖7-10所示；對(duì)有向圖，其鄰接鏈表有兩種形式，如圖7-11所示。圖7-10無(wú)向圖及其鄰接鏈表v1v2v3v4v501234MAX_VEX-1v1

v2v3

v4┇┇v5

213?02?0314?204?23?(a)有向圖v1v2v3v4v513?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51(b)正鄰接鏈表，出度直觀2?02?2?01234MAX_VEX-1v11v22v31v42┇┇┇v513?04?(c)逆鄰接鏈表，入度直觀圖7-11有向圖及其鄰接鏈表結(jié)構(gòu)體定義，詳見(jiàn)P163鄰接表法的特點(diǎn)

◆

表頭向量中每個(gè)分量就是一個(gè)單鏈表的頭結(jié)點(diǎn)，分量個(gè)數(shù)就是圖中的頂點(diǎn)數(shù)目；

◆

在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲(chǔ)空間；

◆

在無(wú)向圖，頂點(diǎn)Vi的度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)；

◆

對(duì)有向圖可以建立正鄰接表或逆鄰接表。正鄰接表是以頂點(diǎn)Vi為出度(即為弧的起點(diǎn))而建立的鄰接表；逆鄰接表是以頂點(diǎn)Vi為入度(即為弧的終點(diǎn))而建立的鄰接表；

◆

在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)Vi的出(或入)度；求入(或出)度，須遍歷整個(gè)鄰接表；◆

在鄰接表上容易找出任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)；7.2.3

十字鏈表法

十字鏈表(OrthogonalList)是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是將有向圖的正鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表。在這種結(jié)構(gòu)中，每條弧的弧頭結(jié)點(diǎn)和弧尾結(jié)點(diǎn)都存放在鏈表中，并將弧結(jié)點(diǎn)分別組織到以弧尾結(jié)點(diǎn)為頭(頂點(diǎn))結(jié)點(diǎn)和以弧頭結(jié)點(diǎn)為頭(頂點(diǎn))結(jié)點(diǎn)的鏈表中。這種結(jié)構(gòu)的結(jié)點(diǎn)邏輯結(jié)構(gòu)如圖7-12所示。弧結(jié)點(diǎn)tailvex

headvexinfohlink

tlink頂點(diǎn)結(jié)點(diǎn)Datafirstin

firstout圖7-12十字鏈表結(jié)點(diǎn)結(jié)構(gòu)◆

data域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息；◆

指針域firstin：指向以該頂點(diǎn)為弧頭的第一條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)；◆

指針域firstout：指向以該頂點(diǎn)為弧尾的第一條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)；◆

尾域tailvex：指示弧尾頂點(diǎn)在圖中的位置；◆

頭域headvex：指示弧頭頂點(diǎn)在圖中的位置；◆

指針域hlink：指向弧頭相同的下一條弧；◆

指針域tlink：指向弧尾相同的下一條??；◆

Info域：指向該弧的相關(guān)信息；V0V1V2V30102∧2023∧∧30∧31∧32∧∧0213V0V1∧V2V3圖7-13有向圖的十字鏈表結(jié)構(gòu)有向圖的十字鏈表結(jié)構(gòu)結(jié)構(gòu)體定義，詳見(jiàn)P1657.2.4

鄰接多重表

鄰接多重表(AdjacencyMultilist)是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鄰接表是無(wú)向圖的一種有效的存儲(chǔ)結(jié)構(gòu)，在無(wú)向圖的鄰接表中，一條邊(v,w)的兩個(gè)表結(jié)點(diǎn)分別初選在以v和w為頭結(jié)點(diǎn)的鏈表中，很容易求得頂點(diǎn)和邊的信息，但在涉及到邊的操作會(huì)帶來(lái)不便。鄰接多重表的結(jié)構(gòu)和十字鏈表類似，每條邊用一個(gè)結(jié)點(diǎn)表示；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)與鄰接表中的完全相同，而表結(jié)點(diǎn)包括六個(gè)域如圖7-14所示。datafirstedge頂點(diǎn)結(jié)點(diǎn)圖7-14鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)markivex

ilink

jvex

jlinkinfo◆

Data域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息；◆

指針域firstedge：指向依附于該頂點(diǎn)的第一條邊所對(duì)應(yīng)的表結(jié)點(diǎn)；◆

標(biāo)志域mark：用以標(biāo)識(shí)該條邊是否被訪問(wèn)過(guò)；◆

ivex和jvex域：分別保存該邊所依附的兩個(gè)頂點(diǎn)在圖中的位置；◆

info域：保存該邊的相關(guān)信息；◆

指針域ilink：指向下一條依附于頂點(diǎn)ivex的邊；◆

指針域jlink：指向下一條依附于頂點(diǎn)jvex的邊；

鄰接多重表與鄰接表的區(qū)別：

后者的同一條邊用兩個(gè)表結(jié)點(diǎn)表示，而前者只用一個(gè)表結(jié)點(diǎn)表示；除標(biāo)志域外，鄰接多重表與鄰接表表達(dá)的信息是相同的，因此，操作的實(shí)現(xiàn)也基本相似。圖7-15無(wú)向圖及其多重鄰接鏈表v1v2v3v4v1v2v3v401230102∧21∧230∧3∧結(jié)構(gòu)體定義，詳見(jiàn)P166-1677.3

圖的遍歷

圖的遍歷(TraveringGraph)：從圖的某一頂點(diǎn)出發(fā)，訪遍圖中的其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次。圖的遍歷算法是各種圖的操作的基礎(chǔ)。

◆

復(fù)雜性：圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能在訪問(wèn)了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原頂點(diǎn)。

◆

解決辦法：在遍歷過(guò)程中記下已被訪問(wèn)過(guò)的頂點(diǎn)。設(shè)置一個(gè)輔助向量Visited[1…n](n為頂點(diǎn)數(shù))，其初值為0，一旦訪問(wèn)了頂點(diǎn)vi后，使Visited[i]為1或?yàn)樵L問(wèn)的次序號(hào)。圖的遍歷算法有深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。采用的數(shù)據(jù)結(jié)構(gòu)是(正)鄰接鏈表。7.3.1深度優(yōu)先搜索算法深度優(yōu)先搜索(DepthFirstSearch--DFS)遍歷類似樹(shù)的先序遍歷，是樹(shù)的先序遍歷的推廣。1

算法思想

設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，則：⑴

從圖中某個(gè)頂點(diǎn)vi出發(fā)，訪問(wèn)vi；然后找到vi的一個(gè)鄰接頂點(diǎn)vi1；⑵從vi1出發(fā)，深度優(yōu)先搜索訪問(wèn)和vi1相鄰接且未被訪問(wèn)的所有頂點(diǎn)；⑶轉(zhuǎn)⑴

，直到和vi相鄰接的所有頂點(diǎn)都被訪問(wèn)為止⑷繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn)vj作為起始頂點(diǎn)，轉(zhuǎn)(1)，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。圖7-17無(wú)向圖深度優(yōu)先搜索遍歷(a)無(wú)向圖Gv1v2v3v4v5(b)G的鄰接鏈表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21?20?01?4?3?

無(wú)向圖的深度優(yōu)先搜索遍歷示例(紅色箭頭)。某種DFS次序是：v1→

v3→

v2→

v4→

v5由算法思想知，這是一個(gè)遞歸過(guò)程。因此，先設(shè)計(jì)一個(gè)從某個(gè)頂點(diǎn)(編號(hào))為v0開(kāi)始深度優(yōu)先搜索的函數(shù)，便于調(diào)用。代碼詳見(jiàn)P1692算法實(shí)現(xiàn)3算法分析

遍歷時(shí)，對(duì)圖的每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)。其實(shí)質(zhì)就是對(duì)每個(gè)頂點(diǎn)查找鄰接頂點(diǎn)的過(guò)程，取決于存儲(chǔ)結(jié)構(gòu)。當(dāng)圖有e條邊，其時(shí)間復(fù)雜度為O(e)，總時(shí)間復(fù)雜度為O(n+e)。7.3.2廣度優(yōu)先搜索算法

廣度優(yōu)先搜索(BreadthFirstSearch--BFS)遍歷類似樹(shù)的按層次遍歷的過(guò)程。1

算法思想設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，則：⑴

從圖中某個(gè)頂點(diǎn)vi出發(fā)，訪問(wèn)vi；⑵訪問(wèn)vi的所有相鄰接且未被訪問(wèn)的所有頂點(diǎn)vi1，vi2，…，vim；⑶以vi1，vi2，…，vim的次序，以vij(1≦j≦m)依此作為vi，轉(zhuǎn)⑴；⑷繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn)vk作為起始頂點(diǎn)，轉(zhuǎn)⑴，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。有向圖的廣度優(yōu)先搜索遍歷示例(紅色箭頭)。上述圖的BFS次序是：v1→

v2→

v4→

v3→

v5(b)G’的正鄰接鏈表13?014?2?3?01234MAX_VEX-1v12v20?v33v41┇┇┇v51圖7-18有向圖廣度優(yōu)先搜索遍歷(a)有向圖G’v1v2v3v4v5

2

算法實(shí)現(xiàn)

為了標(biāo)記圖中頂點(diǎn)是否被訪問(wèn)過(guò)，同樣需要一個(gè)訪問(wèn)標(biāo)記數(shù)組；其次，為了依此訪問(wèn)與vi相鄰接的各個(gè)頂點(diǎn)，需要附加一個(gè)隊(duì)列來(lái)保存訪問(wèn)vi的相鄰接的頂點(diǎn)。代碼實(shí)現(xiàn)詳見(jiàn)P170。

3算法分析用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的唯一區(qū)別是鄰接點(diǎn)搜索次序不同，因此，廣度優(yōu)先搜索算法遍歷圖的總時(shí)間復(fù)雜度為O(n+e)。7.4

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

本節(jié)所討論的內(nèi)容是圖的遍歷算法的具體應(yīng)用。7.4.1無(wú)向圖的連通分量與生成樹(shù)1無(wú)向圖的連通分量和生成樹(shù)

對(duì)于無(wú)向圖，對(duì)其進(jìn)行遍歷時(shí)：◆

若是連通圖：僅需從圖中任一頂點(diǎn)出發(fā)，就能訪問(wèn)圖中的所有頂點(diǎn)；◆

若是非連通圖：需從圖中多個(gè)頂點(diǎn)出發(fā)。每次從一個(gè)新頂點(diǎn)出發(fā)所訪問(wèn)的頂點(diǎn)集序列恰好是各個(gè)連通分量的頂點(diǎn)集；(a)無(wú)向圖Gv1v2v3v4v5(b)G的鄰接鏈表01234MAX_VEX-1v1

v2v3

v4┇┇v5

21?20?01?4?3?圖7-19無(wú)向圖及深度優(yōu)先生成森林(c)深度優(yōu)先生成森林v1v2v3v4v5無(wú)向非連通圖，按圖中給定的鄰接表進(jìn)行深度優(yōu)先搜索遍歷，2次調(diào)用DFS所得到的頂點(diǎn)訪問(wèn)序列集是：

{v1,v3,v2}和{v4,v5}

⑴若G=(V,E)是無(wú)向連通圖，頂點(diǎn)集和邊集分別是V(G)，E(G)。若從G中任意點(diǎn)出發(fā)遍歷時(shí)，E(G)被分成兩個(gè)互不相交的集合：T(G)：遍歷過(guò)程中所經(jīng)過(guò)的邊的集合；B(G)：遍歷過(guò)程中未經(jīng)過(guò)的邊的集合；顯然：E(G)=T(G)∪B(G)，T(G)∩B(G)=?

顯然，圖G’=(V,T(G))是G的極小連通子圖，且G’是一棵樹(shù)。G’稱為圖G的一棵生成樹(shù)。從任意點(diǎn)出發(fā)按DFS算法得到生成樹(shù)G’稱為深度優(yōu)先生成樹(shù)；按BFS算法得到的G’稱為廣度優(yōu)先生成樹(shù)。

⑵

若G=(V,E)是無(wú)向非連通圖，對(duì)圖進(jìn)行遍歷時(shí)得到若干個(gè)連通分量的頂點(diǎn)集：V1(G),V2(G),…,Vn(G)和相應(yīng)所經(jīng)過(guò)的邊集：T1(G),T2(G),…,Tn(G)

則對(duì)應(yīng)的頂點(diǎn)集和邊集的二元組：Gi=(Vi(G),Ti(G))(1≦i≦n)是對(duì)應(yīng)分量的生成樹(shù)，所有這些生成樹(shù)構(gòu)成了原來(lái)非連通圖的生成森林。說(shuō)明：當(dāng)給定無(wú)向圖要求畫(huà)出其對(duì)應(yīng)的生成樹(shù)或生成森林時(shí)，必須先給出相應(yīng)的鄰接表，然后才能根據(jù)鄰接表畫(huà)出其對(duì)應(yīng)的生成樹(shù)或生成森林。7.4.2

有向圖的強(qiáng)連通分量

對(duì)于有向圖，在其每一個(gè)強(qiáng)連通分量中，任何兩個(gè)頂點(diǎn)都是可達(dá)的。VG，與V可相互到達(dá)的所有頂點(diǎn)就是包含V的強(qiáng)連通分量的所有頂點(diǎn)。設(shè)從V可到達(dá)(以V為起點(diǎn)的所有有向路徑的終點(diǎn))的頂點(diǎn)集合為T1(G)，而到達(dá)V(以V為終點(diǎn)的所有有向路徑的起點(diǎn))的頂點(diǎn)集合為T2(G)，則包含V的強(qiáng)連通分量的頂點(diǎn)集合是：

T1(G)∩T2(G)。

求有向圖G的強(qiáng)連通分量的基本步驟是：⑴對(duì)G進(jìn)行深度優(yōu)先遍歷，生成G的深度優(yōu)先生成森林T。⑵對(duì)森林T的頂點(diǎn)按中序遍歷順序進(jìn)行編號(hào)。⑶

改變G中每一條弧的方向，構(gòu)成一個(gè)新的有向圖G’。⑷

按⑵中標(biāo)出的頂點(diǎn)編號(hào)，從編號(hào)最大的頂點(diǎn)開(kāi)始對(duì)G’進(jìn)行深度優(yōu)先搜索，得到一棵深度優(yōu)先生成樹(shù)。若一次完整的搜索過(guò)程沒(méi)有遍歷G’的所有頂點(diǎn)，則從未訪問(wèn)的頂點(diǎn)中選擇一個(gè)編號(hào)最大的頂點(diǎn)，由它開(kāi)始再進(jìn)行深度優(yōu)先搜索，并得到另一棵深度優(yōu)先生成樹(shù)。在該步驟中，每一次深度優(yōu)先搜索所得到的生成樹(shù)中的頂點(diǎn)就是G的一個(gè)強(qiáng)連通分量的所有頂點(diǎn)。

⑸

重復(fù)步驟⑷，直到G’中的所有頂點(diǎn)都被訪問(wèn)。dacfeb(a)有向圖G654321dacfeb(b)執(zhí)行步驟(1)和(2)acdfeb(c)執(zhí)行步驟(3)adcbef(d)執(zhí)行步驟(4)和(5)圖7-20利用深度優(yōu)先搜索求有向圖的強(qiáng)連通分量

在算法實(shí)現(xiàn)時(shí)，建立一個(gè)數(shù)組in_order[n]存放深度優(yōu)先生成森林的中序遍歷序列。對(duì)每個(gè)頂點(diǎn)v，在調(diào)用DFS函數(shù)結(jié)束時(shí)，將頂點(diǎn)依次存放在數(shù)組in_order[n]中。圖采用十字鏈表作為存儲(chǔ)結(jié)構(gòu)最合適。7.4.3

最小生成樹(shù)

如果連通圖是一個(gè)帶權(quán)圖，則其生成樹(shù)中的邊也帶權(quán)，生成樹(shù)中所有邊的權(quán)值之和稱為生成樹(shù)的代價(jià)。

最小生成樹(shù)(MinimumSpanningTree)：帶權(quán)連通圖中代價(jià)最小的生成樹(shù)稱為最小生成樹(shù)。最小生成樹(shù)在實(shí)際中具有重要用途，如設(shè)計(jì)通信網(wǎng)。設(shè)圖的頂點(diǎn)表示城市，邊表示兩個(gè)城市之間的通信線路，邊的權(quán)值表示建造通信線路的費(fèi)用。n個(gè)城市之間最多可以建n(n-1)/2條線路，如何選擇其中的n-1條，使總的建造費(fèi)用最低?基本原則是：◆

盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路；◆

選擇n-1條邊構(gòu)成最小生成樹(shù)。以上的基本原則是基于MST的如下性質(zhì)：設(shè)G=(V，E)是一個(gè)帶權(quán)連通圖，U是頂點(diǎn)集V的一個(gè)非空子集。若u∈U

，v∈V-U，且(u,v)是U中頂點(diǎn)到V-U中頂點(diǎn)之間權(quán)值最小的邊，則必存在一棵包含邊(u,v)的最小生成樹(shù)。

構(gòu)造最小生成樹(shù)的算法有許多，基本原則是：

設(shè)圖G的任何一棵最小生成樹(shù)都不包含邊(u,v)。設(shè)T是G的一棵生成樹(shù)，則T是連通的，從u到v必有一條路徑(u,…,v)，當(dāng)將邊(u,v)加入到T中時(shí)就構(gòu)成了回路。則路徑(u,…,v)中必有一條邊(u’,v’)，滿足u’∈U，v’∈V-U。刪去邊(u’,v’)便可消除回路，同時(shí)得到另一棵生成樹(shù)T’。

由于(u,v)是U中頂點(diǎn)到V-U中頂點(diǎn)之間權(quán)值最小的邊，故(u,v)的權(quán)值不會(huì)高于(u’,v’)的權(quán)值，T’的代價(jià)也不會(huì)高于T，T’是包含(u,v)的一棵最小生成樹(shù)，與假設(shè)矛盾。證明：用反證法證明。7.5.1普里姆(Prim)算法

從連通網(wǎng)N=(U，E)中找最小生成樹(shù)T=(U，TE)

。1算法思想(P174頁(yè))⑴

若從頂點(diǎn)v0出發(fā)構(gòu)造，U={v0}，TE={}；⑵

先找權(quán)值最小的邊(u，v)，其中u∈U且v∈V-U，并且子圖不構(gòu)成環(huán)，則U=U∪{v}，TE=TE∪{(u，v)}

；⑶

重復(fù)⑵

，直到U=V為止。則TE中必有n-1條邊，

T=(U，TE)就是最小生成樹(shù)。v1v3v2v4v54857121136(a)v2v45(b)(c)v53v2v45(d)v14v53v2v45v36(e)v14v53v2v45圖7-21按prime算法從v2出發(fā)構(gòu)造最小生成樹(shù)的過(guò)程

iclosedge01234UV-UKadjvexlwcostv28v2

7v25v212{v2}{v1,v3,v4,v5}3adjvexlwcostv44v27v20v43{v2,v4}{v1,v3,v5}4adjvexlwcostv44v56v20v40{v2,v4,v5}{v1,v3}0adjvexlwcostv40v56v20v40{v2,v4,v5,v1}{v3}2adjvexlwcostv40v50v20v40{v2,v4,v5,v1,v3}{}表7-1構(gòu)造過(guò)程中輔組數(shù)組closedge中各分量的值的變化情況

算法實(shí)現(xiàn)：P175

設(shè)帶權(quán)連通圖有n個(gè)頂點(diǎn)，則算法的主要執(zhí)行是二重循環(huán)：求closedge中權(quán)值最小的邊，頻度為n-1；

修改closedge數(shù)組，頻度為n。因此，整個(gè)算法的時(shí)間復(fù)雜度是O(n2)，與邊的數(shù)目無(wú)關(guān)。算法分析：7.5.2克魯斯卡爾(Kruskal)算法1

算法思想（P176）設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是其最小生成樹(shù)。初值：U=V，TE={}。對(duì)G中的邊按權(quán)值大小從小到大依次選取。⑴

選取權(quán)值最小的邊(vi，vj)，若邊(vi，vj)加入到TE后形成回路，則舍棄該邊(邊(vi，vj)；否則，將該邊并入到TE中，即TE=TE∪{(vi，vj)}。⑵

重復(fù)⑴

，直到TE中包含有n-1條邊為止。v1v3v2v4v54857121136(a)(b)3v5v4v36(e)v14v53v2v45圖7-22按kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程(c)v143v5v4(d)v25v143v5v4設(shè)帶權(quán)連通圖有n個(gè)頂點(diǎn)，e條邊，則算法的主要執(zhí)行是：◆

Vset數(shù)組初始化：時(shí)間復(fù)雜度是O(n)；◆

邊表按權(quán)值排序：若采用堆排序或快速排序，選擇最小邊時(shí)間復(fù)雜度是O(㏒e)；◆

又生成每個(gè)連通分量，判斷回路；整個(gè)算法的時(shí)間復(fù)雜度是O(e㏒e)。算法分析：7.6

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

有向無(wú)環(huán)圖(DirectedAcyclingGraph)：是圖中沒(méi)有回路(環(huán))的有向圖。是一類具有代表性的圖，主要用于研究工程項(xiàng)目的工序問(wèn)題、工程時(shí)間進(jìn)度問(wèn)題等。一個(gè)工程(project)都可分為若干個(gè)稱為活動(dòng)(active)的子工程(或工序)，各個(gè)子工程受到一定的條件約束：某個(gè)子工程必須開(kāi)始于另一個(gè)子工程完成之后；整個(gè)工程有一個(gè)開(kāi)始點(diǎn)(起點(diǎn))和一個(gè)終點(diǎn)。人們關(guān)心：◆

工程能否順利完成?影響工程的關(guān)鍵活動(dòng)是什么?◆

估算整個(gè)工程完成所必須的最短時(shí)間是多少?對(duì)工程的活動(dòng)加以抽象：圖中頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(ActivityOnVertexNetwork

，AOV網(wǎng))。AOV網(wǎng)7.6.1拓?fù)渑判?

定義拓?fù)渑判?TopologicalSort)：由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的操作?！?/p>

集合上的關(guān)系：集合A上的關(guān)系是從A到A的關(guān)系(AA)。◆

關(guān)系的自反性：若a∈A有(a，a)∈R，稱集合A上的關(guān)系R是自反的?！?/p>

關(guān)系的對(duì)稱性：如果對(duì)于a，b∈A，只要有(a，b)∈R就有(b，a)∈R

，稱集合A上的關(guān)系R是對(duì)稱的?！?/p>

關(guān)系的對(duì)稱性與反對(duì)稱性：如果對(duì)于a，b∈A

，只要有(a，b)∈R就有(b，a)∈R

，稱集合A上的關(guān)系R是對(duì)稱的。如果對(duì)于a，b∈A

，僅當(dāng)a=b時(shí)有(a，b)∈R和(b，a)∈R

，稱集合A上的關(guān)系R是反對(duì)稱的?！?/p>

關(guān)系的傳遞性：若a，b，c∈A，若(a，b)∈R，并且(b，c)∈R

，則(a，c)∈R，稱集合A上的關(guān)系R是傳遞的?！?/p>

偏序：若集合A上的關(guān)系R是自反的，反對(duì)稱的和傳遞的，則稱R是集合A上的偏序關(guān)系?！?/p>

全序：設(shè)R是集合A上的偏序關(guān)系，a，b∈A，必有aRb或bRa，則稱R是集合A上的全序關(guān)系。

即偏序是指集合中僅有部分元素之間可以比較，而全序是指集合中任意兩個(gè)元素之間都可以比較。在AOV網(wǎng)中，若有有向邊<i,j>，則i是j的直接前驅(qū)，j是i的直接后繼；推而廣之，若從頂點(diǎn)i到頂點(diǎn)j有有向路徑，則i是j的前驅(qū)，j是i的后繼。在AOV網(wǎng)中，不能有環(huán)，否則，某項(xiàng)活動(dòng)能否進(jìn)行是以自身的完成作為前提條件。

檢查方法：對(duì)有向圖的頂點(diǎn)進(jìn)行拓?fù)渑判?，若所有頂點(diǎn)都在其拓?fù)溆行蛐蛄兄?，則無(wú)環(huán)。

有向圖的拓?fù)渑判颍簶?gòu)造AOV網(wǎng)中頂點(diǎn)的一個(gè)拓?fù)渚€性序列(v’1,v’2,?,v’n)，使得該線性序列不僅保持原來(lái)有向圖中頂點(diǎn)之間的優(yōu)先關(guān)系，而且對(duì)原圖中沒(méi)有優(yōu)先關(guān)系的頂點(diǎn)之間也建立一種(人為的)優(yōu)先關(guān)系。

2

拓?fù)渑判蛩惴ㄋ惴ㄋ枷擘?/p>

在AOV網(wǎng)中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出；

②

在AOV網(wǎng)中刪除該頂點(diǎn)以及從該頂點(diǎn)出發(fā)的(以該頂點(diǎn)為尾的弧)所有有向弧(邊)；③

重復(fù)①、②，直到圖中全部頂點(diǎn)都已輸出(圖中無(wú)環(huán))或圖中不存在無(wú)前驅(qū)的頂點(diǎn)(圖中必有環(huán))。3算法實(shí)現(xiàn)說(shuō)明◆采用正鄰接鏈作為AOV網(wǎng)的存儲(chǔ)結(jié)構(gòu)；◆

設(shè)立堆棧，用來(lái)暫存入度為0的頂點(diǎn)；◆刪除頂點(diǎn)以它為尾的?。夯☆^頂點(diǎn)的入度減1。算法實(shí)現(xiàn)v1v2v3v4v5v6(a)有向圖(b)輸出v1后v4v2v3v5v6圖7-23有向圖的拓?fù)渑判蜻^(guò)程(c)輸出v6后v4v2v3v5(d)輸出v4后v2v3v5(e)輸出v3后v2v5(1)

統(tǒng)計(jì)各頂點(diǎn)入度的函數(shù)voidcount_indegree(ALGraph*G){intk;LinkNode*p;for(k=0;k<G->vexnum;k++)G->adjlist[k].indegree=0;/*頂點(diǎn)入度初始化*/for(k=0;k<G->vexnum;k++){p=G->adjlist[k].firstarc;while(p!=NULL)/*頂點(diǎn)入度統(tǒng)計(jì)*/{G->adjlist[p->adjvex].indegree++;p=p->nextarc;}}}3算法實(shí)現(xiàn)說(shuō)明◆采用正鄰接鏈作為AOV網(wǎng)的存儲(chǔ)結(jié)構(gòu)；◆設(shè)立堆棧，用來(lái)暫存入度為0的頂點(diǎn)；◆刪除頂點(diǎn)以它為尾的?。夯☆^頂點(diǎn)的入度減1。

(2)

拓?fù)渑判蛩惴╥nt

Topologic_Sort(ALGraph*G,int

topol[])/*頂點(diǎn)的拓?fù)湫蛄斜４嬖谝痪S數(shù)組topol中*/{intk,no,vex_no,top=0,count=0,boolean=1;int

stack[MAX_VEX];/*用作堆棧*/LinkNode*p;count_indegree(G);/*統(tǒng)計(jì)各頂點(diǎn)的入度*/for(k=0;k<G->vexnum;k++)if(G->adjlist[k].indegree==0)stack[++top]=G->adjlist[k].data;do{if(top==0)boolean=0;else{no=stack[top--];/*棧頂元素出棧*/

topl[++count]=no;/*記錄頂點(diǎn)序列*/p=G->adjlist[no].firstarc;while(p!=NULL)/*刪除以頂點(diǎn)為尾的弧*/{vex_no=p->adjvex;G->adjlist[vex_no].indegree--;if(G->adjlist[vex_no].indegree==0)stack[++top]=vex_no;p=p->nextarc;}}}while(boolean==0);if(count<G->vexnum)return(-1);elsereturn(1);}算法分析：

設(shè)AOV網(wǎng)有n個(gè)頂點(diǎn)，e條邊，則算法的主要執(zhí)行是：◆

統(tǒng)計(jì)各頂點(diǎn)的入度：時(shí)間復(fù)雜度是O(n+e)；◆

入度為0的頂點(diǎn)入棧：時(shí)間復(fù)雜度是O(n)；◆

排序過(guò)程：頂點(diǎn)入棧和出棧操作執(zhí)行n次，入度減1的操作共執(zhí)行e次，時(shí)間復(fù)雜度是O(n+e)；

因此，整個(gè)算法的時(shí)間復(fù)雜度是O(n+e)。7.6.2關(guān)鍵路徑(CriticalPath)

與AOV網(wǎng)相對(duì)應(yīng)的是AOE(ActivityOnEdge)，是邊表示活動(dòng)的有向無(wú)環(huán)圖，如圖7-24所示。圖中頂點(diǎn)表示事件(Event)，每個(gè)事件表示在其前的所有活動(dòng)已經(jīng)完成，其后的活動(dòng)可以開(kāi)始；弧表示活動(dòng)，弧上的權(quán)值表示相應(yīng)活動(dòng)所需的時(shí)間或費(fèi)用。v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2圖7-24一個(gè)AOE網(wǎng)

1

與AOE有關(guān)的研究問(wèn)題◆

完成整個(gè)工程至少需要多少時(shí)間?◆

哪些活動(dòng)是影響工程進(jìn)度(費(fèi)用)的關(guān)鍵?

工程完成最短時(shí)間：從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度(路徑上各活動(dòng)持續(xù)時(shí)間之和)。長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑，關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)是影響整個(gè)工程的關(guān)鍵。設(shè)v0是起點(diǎn)，從v0到vi的最長(zhǎng)路徑長(zhǎng)度稱為事件vi的最早發(fā)生時(shí)間，即是以vi為尾的所有活動(dòng)的最早發(fā)生時(shí)間。若活動(dòng)ai是弧<j,k>，持續(xù)時(shí)間是dut(<j,k>)，設(shè)：◆e(i)：表示活動(dòng)ai的最早開(kāi)始時(shí)間；◆

l(i)：在不影響進(jìn)度的前提下，表示活動(dòng)ai的最晚開(kāi)始時(shí)間；則l(i)-e(i)表示活動(dòng)ai的時(shí)間余量，若l(i)-e(i)=0，表示活動(dòng)ai是關(guān)鍵活動(dòng)?！?/p>

ve(i)：表示事件vi的最早發(fā)生時(shí)間，即從起點(diǎn)到頂點(diǎn)vi的最長(zhǎng)路徑長(zhǎng)度；

◆

vl(i)：表示事件vi的最晚發(fā)生時(shí)間。則有以下關(guān)系：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)7-10j=0，表示vj是起點(diǎn)Max{ve(i)+dut(<i,j>)|<vi,vj>是網(wǎng)中的弧}ve(j)=7-2

含義是：源點(diǎn)事件的最早發(fā)生時(shí)間設(shè)為0；除源點(diǎn)外，只有進(jìn)入頂點(diǎn)vj的所有弧所代表的活動(dòng)全部結(jié)束后，事件vj才能發(fā)生。即只有vj的所有前驅(qū)事件vi的最早發(fā)生時(shí)間ve(i)計(jì)算出來(lái)后，才能計(jì)算ve(j)。

方法是：對(duì)所有事件進(jìn)行拓?fù)渑判?，然后依次按拓?fù)漤樞蛴?jì)算每個(gè)事件的最早發(fā)生時(shí)間。ve(n-1)j=n-1，表示vj是終點(diǎn)Min{vl(k)-dut(<j,k>)|<vj,vk>是網(wǎng)中的弧}vl(j)=7-3

含義是：只有vj的所有后繼事件vk的最晚發(fā)生時(shí)間vl(k)計(jì)算出來(lái)后，才能計(jì)算vl(j)。

方法是：按拓?fù)渑判虻哪骓樞?，依次?jì)算每個(gè)事件的最晚發(fā)生時(shí)間。

2

求AOE中關(guān)鍵路徑和關(guān)鍵活動(dòng)⑴

算法思想①利用拓?fù)渑判蚯蟪鯝OE網(wǎng)的一個(gè)拓?fù)湫蛄校?/p>

②從拓?fù)渑判虻男蛄械牡谝粋€(gè)頂點(diǎn)(源點(diǎn))開(kāi)始，按拓?fù)漤樞蛞来斡?jì)算每個(gè)事件的最早發(fā)生時(shí)間ve(i)

；

③從拓?fù)渑判虻男蛄械淖詈笠粋€(gè)頂點(diǎn)(匯點(diǎn))開(kāi)始，按逆拓?fù)漤樞蛞来斡?jì)算每個(gè)事件的最晚發(fā)生時(shí)間vl(i)

；

對(duì)于圖7-24的AOE網(wǎng)，處理過(guò)程如下：◆

拓?fù)渑判虻男蛄惺牵?v0,v1,v2,v3,

v4,v5,v6,v7,v8)頂點(diǎn)v0v1v2v3v4v5v6v7v8ve(i)0310122217202833vl(i)0910232217312833表7-2圖7-24的ve(i)和vl(i)的值◆

根據(jù)計(jì)算ve(i)的公式(7-2)和計(jì)算vl(i)的公式(7-3)，計(jì)算各個(gè)事件的ve(i)和vl(i)值，如表7-2所示。◆

根據(jù)關(guān)鍵路徑的定義，知該AOE網(wǎng)的關(guān)鍵路徑是：(v0,v2,v4,v7,v8)和(v0,v2,v5,v7,v8)。◆

關(guān)鍵路徑活動(dòng)是：<v0,v2>，<v2,v4>，<v2,v5>，<v4,v7>，<v5,v7>，<v5,v8>。⑵

算法實(shí)現(xiàn)voidcritical_path(ALGraph*G){intj,k,m;LinkNode*p;if(Topologic_Sort(G)==-1)printf(“\nAOE網(wǎng)中存在回路，錯(cuò)誤!!\n\n”);else{for(j=0;j<G->vexnum;j++)

ve[j]=0;/*事件最早發(fā)生時(shí)間初始化*/for(m=0;m<G->vexnum;m++){j=topol[m];p=G->adjlist[j].firstarc;for(;p!=NULL;p=p->nextarc)

{k=p->adjvex;if(ve[j]+p->weight>ve[k])

ve[k]=ve[j]+p->weight;}}/*計(jì)算每個(gè)事件的最早發(fā)生時(shí)間ve值*/for(j=0;j<G->vexnum;j++)

vl[j]=ve[j];/*事件最晚發(fā)生時(shí)間初始化*/for(m=G->vexnum-1;m>=0;m--){j=topol[m];p=G->adjlist[j].firstarc;for(;p!=NULL;p=p->nextarc){k=p->adjvex;if(vl[k]-p->weight<vl[j])

vl[j]=vl[k]-p->weight;

}}/*計(jì)算每個(gè)事件的最晚發(fā)生時(shí)間vl值*/for(m=0;m<G->vexnum;m++){p=G->adjlist[m].firstarc;for(;p!=NULL;p=p->nextarc){k=p->adjvex;if((ve[m]+p->weight)==vl[k])

printf(“<%d,%d>,m,j”);}}/*輸出所有的關(guān)鍵活動(dòng)*/}/*endofelse*/}⑶

算法分析

設(shè)AOE網(wǎng)有n個(gè)事件，e個(gè)活動(dòng)，則算法的主要執(zhí)行是：◆

進(jìn)行拓?fù)渑判颍簳r(shí)間復(fù)雜度是O(n+e)；◆

求每個(gè)事件的ve值和vl值：時(shí)間復(fù)雜度是O(n+e)；◆

根據(jù)ve值和vl值找關(guān)鍵活動(dòng)：時(shí)間復(fù)雜度是O(n+e)；

因此，整個(gè)算法的時(shí)間復(fù)雜度是O(n+e)。7.7

最短路徑若用帶權(quán)圖表示交通網(wǎng)，圖中頂點(diǎn)表示地點(diǎn)，邊代表兩地之間有直接道路，邊上的權(quán)值表示路程(或所花費(fèi)用或時(shí)間)。從一個(gè)地方到另一個(gè)地方的路徑長(zhǎng)度表示該路徑上各邊的權(quán)值之和。問(wèn)題：◆

兩地之間是否有通路?◆

在有多條通路的情況下，哪條最短?

考慮到交通網(wǎng)的有向性，直接討論的是帶權(quán)有向圖的最短路徑問(wèn)題，但解決問(wèn)題的算法也適用于無(wú)向圖。將一個(gè)路徑的起始頂點(diǎn)稱為