圖的基本概念

1第7章圖7.1圖的基本概念7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.6最短路徑2

圖是比樹形結(jié)構(gòu)更為復(fù)雜的非線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，除了開始結(jié)點(diǎn)和終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有唯一的直接前趨和直接后繼，結(jié)點(diǎn)之間存在一對(duì)一的線性關(guān)系；在樹形結(jié)構(gòu)中，結(jié)點(diǎn)之間存在一對(duì)多的層次關(guān)系，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只能有一個(gè)直接前趨（即雙親），但每個(gè)結(jié)點(diǎn)允許有零或多7.1圖的基本概念3個(gè)直接后繼（即孩子），即每一層上的結(jié)點(diǎn)可以與它下面一層中的多個(gè)結(jié)點(diǎn)相關(guān)，但是只能和它上面一層的一個(gè)結(jié)點(diǎn)（雙親結(jié)點(diǎn)）相關(guān)。而在圖結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是一種多對(duì)多的網(wǎng)狀關(guān)系，任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。4

圖的應(yīng)用已滲透到語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電子、通訊、數(shù)學(xué)、計(jì)算機(jī)科學(xué)等諸多學(xué)科領(lǐng)域。

本章首先介紹圖的概念，然后重點(diǎn)介紹圖的存儲(chǔ)結(jié)構(gòu)及常用算法。5

圖是由非空的有窮頂點(diǎn)集合V和表示頂點(diǎn)間關(guān)系的弧或邊的有窮集合E組成的二元組，一般記為：

G＝（V，E）其中，V={vi|vi∈dataobject}，E={<vi,vj>或（x，y）|vi,vj∈V}，dataobject是具有相同性質(zhì)的數(shù)據(jù)元素（即頂點(diǎn)）的集合；

1圖的定義6

有序?qū)?lt;vi,vj>表示從頂點(diǎn)vi到vj有一條邊單向相連稱作弧，且稱vi為弧尾（始點(diǎn)），vj為弧頭（終點(diǎn)），此時(shí)稱圖為有向圖。如圖7.1（a）中的G2為有向圖。若<vi,vj>∈E，且有<vj,vi>∈E，則可以用無序?qū)Γ╲i,vj）代替這兩個(gè)有序?qū)Γ磮D中的每條邊都是沒有方向的，則稱G為無向圖。如圖7.1（b）中的G1為無向圖。2有向圖與無向圖7有向圖——對(duì)于一個(gè)圖G，若邊集合E（G）為有向邊的集合，則稱該圖為有向圖。如圖7.1(a).無向圖——對(duì)于一個(gè)圖G，若邊集合E（G）為無向邊的集合，則稱該圖為無向圖。如圖7.1(b).（a）有向圖（b）無向圖圖7.1G8常用術(shù)語(yǔ)：(1)一條弧——在有序圖中，<v,w>表示從v到w的一條弧，v為弧尾，w為弧頭。即尖括號(hào)表示有序?qū)Α?2)一條邊——在無序圖中，(v,w)表示v和w之間的一條邊，即圓括號(hào)表示無序?qū)Α?3)完全圖——對(duì)于無向圖，設(shè)頂點(diǎn)數(shù)目為n，則有n(n-1)/2條邊的無向圖（即每對(duì)頂點(diǎn)間均存在有邊）。尾VW頭9(4)完全有向圖——對(duì)于有向圖，設(shè)頂點(diǎn)數(shù)目為n，則有n(n-1)條弧的有向圖（即每對(duì)頂點(diǎn)間均存在有弧）。(5)稀疏圖、稠密圖、子圖、鄰接點(diǎn)、網(wǎng)絡(luò);

(6)頂點(diǎn)的度TD（v）——（對(duì)無向圖）是與頂點(diǎn)有關(guān)的邊的數(shù)目，如G2中頂點(diǎn)v2的度為3;

入度ID(v）和出度OD（v）——（對(duì)有向圖）入度為該頂點(diǎn)的弧頭數(shù)目，出度為該頂點(diǎn)的弧尾數(shù)目，該頂點(diǎn)的度TD（v）=入度+出度，如圖G1中頂點(diǎn)V1:TD(v1)=ID(v1)+OD(v1)=1+2=310對(duì)于一個(gè)有n個(gè)頂點(diǎn)，e條邊或弧的圖，滿足如下關(guān)系：(7)路徑和路徑長(zhǎng)度——如圖7.3(a)中A—B有三條路徑，分別是：(8)簡(jiǎn)單路徑、回路或環(huán)——(9)連通、連通圖和連通分量——(10)強(qiáng)連通圖和強(qiáng)連通分量——(11)權(quán)和網(wǎng)——1112

將具有最大的邊數(shù)n(n-1)／2條邊的無向圖稱為無向完全圖；具有n(n-1)條弧的有向圖稱為有向完全圖。而將具有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。假設(shè)有兩個(gè)圖G=（V，E）和G’=（V’，E’），如果V’V且E’E，則稱G’為G的子圖。例如，圖7.2為圖7.1中圖G1和G2的一些子圖。3完全圖與子圖1314

對(duì)于無向圖G=（V，E），若（x，y）∈E，則稱x和y互為鄰接點(diǎn)，即x和y相鄰接，邊（x，y）依附于頂點(diǎn)x和y，或者說邊（x，y）和頂點(diǎn)x和y相關(guān)聯(lián)。同樣，對(duì)于有向圖，若<x，y>是一條弧，則稱頂點(diǎn)x鄰接到頂點(diǎn)y，頂點(diǎn)y鄰接于頂點(diǎn)x，或者稱弧<x，y>關(guān)聯(lián)于頂點(diǎn)x和y，也可以稱弧<x，y>與頂點(diǎn)x和y相關(guān)聯(lián)。

4鄰接與關(guān)聯(lián)15

在無向圖中，頂點(diǎn)V的度是與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，記為D(v)。而在有向圖中要區(qū)別頂點(diǎn)的入度和出度的概念。入度是指以頂點(diǎn)V為頭或終點(diǎn)的弧的數(shù)目，記為ID(v)；出度是指以頂點(diǎn)V為尾或始點(diǎn)的弧的數(shù)目，記為OD(v)，并將出度為0的頂點(diǎn)稱為終端頂點(diǎn)(或葉子)；頂點(diǎn)V的度則定義為該頂點(diǎn)的入度和出度之和，即D(v)＝ID(v)十OD(v)。

5度、入度和出度16

在無向圖G中，若存在一個(gè)頂點(diǎn)序列Vp，Vi1，Vi2，…，Vin，Vq，使得(Vp，Vi1)，(Vi1，Vi2)，…，(Vin，Vq)都是E中的邊，或者在有向圖中，若<Vp,Vi1>，<Vi1,Vi2>，…，<Vin,Vq>都是E中的弧，則稱Vp，Vi1，Vi2，…，Vin，Vq為從頂點(diǎn)Vp到頂點(diǎn)Vq的一條路徑，而將該路徑上邊或弧的數(shù)目稱為路徑長(zhǎng)度。如果在一條路徑上，除了Vp和Vq相同外，其他頂點(diǎn)都不相同，則稱此路徑為一條簡(jiǎn)單路徑，而將起點(diǎn)和終點(diǎn)相同（即Vp=Vq）的簡(jiǎn)單路徑稱為簡(jiǎn)單回路或環(huán)。

6路徑與回路17

在無向圖G中，如果從頂點(diǎn)Vi到Vj有路徑，則稱Vi和Vj是連通的。如果圖G中任意兩個(gè)不同的頂點(diǎn)Vi和Vj（即Vi≠Vj）都存在路徑連通，則稱該圖G是連通圖。一個(gè)無向圖G的極大連通子圖稱為此圖的連通分量。在有向圖G中，如果對(duì)于任意兩個(gè)不同的頂點(diǎn)Vi，Vj（即Vi≠Vj），都存在從Vi到Vj和從Vj到Vi的路徑，則稱該有向圖G是強(qiáng)連通圖。一個(gè)有向圖G的極大強(qiáng)連通子圖稱作該有向圖G的強(qiáng)連通分量。例如，圖7.1中的圖G2不是強(qiáng)連通圖。如無向圖圖7.3及它的3個(gè)連通分量（P159）。7連通圖與強(qiáng)連通18如下圖（a）中有兩個(gè)強(qiáng)連通分量，分別如圖（b）和（c）所示：19

有時(shí)在實(shí)際應(yīng)用中，圖的邊或弧具有與它相關(guān)的數(shù)稱作權(quán)。權(quán)可以表示一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、花費(fèi)的代價(jià)等。帶權(quán)的圖稱為網(wǎng)絡(luò)。

8網(wǎng)絡(luò)20

一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它包含有圖中全部的n個(gè)頂點(diǎn)和n-1條邊。如果在一棵生成樹上添加一條邊，則必定構(gòu)成一個(gè)環(huán)。例如，圖7.1中的G1即為其本身的生成樹。一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有且僅有n-1條邊。9生成樹217.2圖的存儲(chǔ)結(jié)構(gòu)

本節(jié)討論三種常用的圖與網(wǎng)的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣、鄰接表和鄰接多重表。

22

1、鄰接矩陣對(duì)一個(gè)具有n個(gè)頂點(diǎn)的圖或網(wǎng)，可以用一個(gè)一維數(shù)組表示其頂點(diǎn)信息，用鄰接矩陣來表示頂點(diǎn)間是否相鄰的關(guān)系。若G是一個(gè)具有n個(gè)頂點(diǎn)的圖，則G的鄰接矩陣A應(yīng)是具有如下性質(zhì)的n階方陣:

1(Vi，Vj)或〈Vi，Vj〉∈E（G）（即兩頂點(diǎn)相關(guān)聯(lián)）

A[i，j]＝

0(Vi，Vj)或〈Vi，Vj〉E（G）（即兩頂點(diǎn)無關(guān)聯(lián)）7.2.1鄰接矩陣（數(shù)組表示法）23例如，圖7.1中Gl和G2的鄰接矩陣A1和A2分別為：24

借助于鄰接矩陣很容易判斷出兩個(gè)頂點(diǎn)是否相鄰，并計(jì)算出各頂點(diǎn)的度。在無向圖中，頂點(diǎn)Vi的度是鄰接矩陣A中第i行的非零元素個(gè)數(shù)之和，即25

在有向圖中，頂點(diǎn)Vi的出度是鄰接矩陣A中第i行非零元素個(gè)數(shù)之和，而頂點(diǎn)Vi的入度是鄰接矩陣A中第i列非零元素個(gè)數(shù)之和，即網(wǎng)絡(luò)的鄰接矩陣A定義為:（Wij為權(quán)值）

wij (Vi，Vj)或〈Vi，Vj〉∈EA[i，j]=∞ (Vi，Vj)或〈Vi，Vj〉E2627

2、鄰接矩陣表示

#defineMAXVAL99999/*設(shè)最大值∞為99999*/#defineMAXNUM20/*最大頂點(diǎn)數(shù)*/typedefcharvertextype;/*頂點(diǎn)數(shù)據(jù)類型，此處設(shè)為char類型*/typedeffloatadjtype；/*權(quán)值類型*/typedefstruct{vertextypevex[MAXNUM];/*用一維數(shù)組表示頂點(diǎn)*/ adjtypearcs[MAXNUM][MAXNUM]；/*鄰接矩陣用二維數(shù)組表示*/ intn，e；/*圖的當(dāng)前頂點(diǎn)數(shù)和弧或邊數(shù)*/}*mgraph;

28voidcreatgraph(mgraphg) /*

采用鄰接矩陣表示法構(gòu)造無向網(wǎng)g*/{inti，j，k；floatw；

scanf(“%d%d”，&g->n，&g->e)；/*輸入圖的頂點(diǎn)數(shù)和邊數(shù)*/for(i=1；i<=g->n；i++)scanf(“%c”，&g->vex[i])；/*構(gòu)造頂點(diǎn)向量*/for(i=1；i<=g->n；i++) for(j=1；j<=g->n；j++)g->arcs[i][j]=MAXVAL；/*初始化鄰接矩陣*/for(k=1；k<=g->e；k++){scanf(“%d%d%f”，&i，&j，&w)；

g->arcs[i][j]=w；g->arcs[j][i]=w；/*權(quán)值賦予鄰接矩陣的相應(yīng)元素*/}}/*creagraph*/3、鄰接矩陣表示法構(gòu)造無向網(wǎng)291、結(jié)點(diǎn)結(jié)構(gòu)

鄰接表（AdjdcencyList）是圖或網(wǎng)的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表中，對(duì)圖或網(wǎng)中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，單鏈表中的結(jié)點(diǎn)表示該頂點(diǎn)的所有鄰接點(diǎn)。在有向圖中，某頂點(diǎn)所對(duì)應(yīng)的單鏈表中的結(jié)點(diǎn)是以該頂點(diǎn)為弧尾的頂點(diǎn)。每一個(gè)結(jié)點(diǎn)由三個(gè)域組成，其中，鄰接點(diǎn)域（adjvex）指示與頂點(diǎn)vi鄰接的頂點(diǎn)在圖中的序號(hào)，指針域（link）指示vi的下一個(gè)鄰接結(jié)點(diǎn)，有時(shí)，可以在結(jié)點(diǎn)中添加7.2.2鄰接表30

信息域（info）用于存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。為了能夠隨機(jī)訪問任一個(gè)頂點(diǎn)的鄰接鏈表，可以在每一個(gè)鄰接鏈表前增設(shè)一個(gè)表頭結(jié)點(diǎn)，然后將所有鄰接表的表頭結(jié)點(diǎn)存放在一個(gè)一維數(shù)組中。表結(jié)點(diǎn)和表頭結(jié)點(diǎn)結(jié)構(gòu)如下所示：31表結(jié)點(diǎn)類型定義：

#defineM50typedefstructnode{intadjvex；/*鄰接點(diǎn)域*/structnode*link；/*指針域*/}edgenode；

2、類型定義32typedefstructheadnode{vextypevexdata；/*頂點(diǎn)數(shù)據(jù)域*/structnode*firstarc；/*指針域指向鏈表中第一個(gè)結(jié)點(diǎn)*/}vexnode；鄰接表類型：

typedefvexnodeadjlist[M]；/*adjlist為鄰接表類型*/表頭結(jié)點(diǎn)類型定義：33

圖7.5（a）給出了圖7.1中無向圖G1的鄰接表，圖7.5（b）、（c）給出了圖7.1中有向圖G2的鄰接表和逆鄰接表。若要表示網(wǎng)的鄰接表，則只需在鏈表的每個(gè)結(jié)點(diǎn)中增加一個(gè)存放邊或弧的權(quán)值的數(shù)據(jù)域（info）即可。利用鄰接表可以很容易地查找到任一個(gè)頂點(diǎn)的鄰接點(diǎn)，但要判定任意兩個(gè)頂點(diǎn)vi和vj之間是否有邊或弧相連，則需要搜索第i個(gè)或第j個(gè)鏈表，在這一點(diǎn)上不及鄰接矩陣方便。

3、鄰接表與逆鄰接表34例：圖G1、G2的鄰接矩陣表示：（1）給每個(gè)頂點(diǎn)編號(hào)；（2）以每個(gè)頂點(diǎn)為頭建立一個(gè)單鏈；（3）單鏈中后繼結(jié)點(diǎn)為與該頭結(jié)點(diǎn)關(guān)聯(lián)的各結(jié)點(diǎn)。3536G2的逆鄰接矩陣：在有向圖中，以入度為鏈中后繼。37

voidcreatlist(vexnodeag[]，intn){edgenode*p;inti，j，k；charch；

for(i=1；i<=n；i++){scanf(“%c”，&ch)；/*讀入頂點(diǎn)信息*/ag[i].vexdata=ch；/*設(shè)頂點(diǎn)為字符型*/ag[i].firstarc=NULL；/*將每個(gè)鏈表初始化為空*/}scanf(“％d，％d”，&i，&j)；

while((i＞0)&&(j＞0))/*輸入的(i,j)為(0,0)作為結(jié)束標(biāo)記*/

4、無向圖的鄰接表生成算法38

{p=(edgenode*)malloc(sizeof(edgenode))；

p->adjvex=j；

p->link=ag[i].firstarc；

ag[i].firstarc=p；/*結(jié)點(diǎn)j插入到第i個(gè)鏈表*/p=(edgenode*)malloc(sizeof(edgenode))；

p->adjvex=i；

p->link=ag[j].firstarc；

ag[j].firstarc=p；/*結(jié)點(diǎn)i插入到第j個(gè)鏈表的頭部*/scanf(“％d，％d”，&i，&j)；

}}/*creatlist*/39

該算法的時(shí)間復(fù)雜度是O(n+e)（e為邊數(shù)）。有向圖鄰接表的建立算法與建立鄰接矩陣的算法相似，但在輸入一條弧的頂點(diǎn)序號(hào)<i，j>時(shí)只需生成一個(gè)結(jié)點(diǎn)（其adjvex域?yàn)閖）并將其插入到第i個(gè)頂點(diǎn)的鏈表中即可。407.2.3十字鏈表

十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。可以看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。在十字鏈表中，對(duì)應(yīng)于有向圖中每一條弧有一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)于每個(gè)頂點(diǎn)也有一個(gè)結(jié)點(diǎn)?；〗Y(jié)點(diǎn)結(jié)構(gòu)為5個(gè)域，分別是：尾結(jié)點(diǎn)位置（tailvex）、頭結(jié)點(diǎn)位置（headvex）、弧頭鏈域（hlink）指向弧頭相同的下一弧、弧尾鏈域（tlink）指向弧尾相同的下一弧、相關(guān)信息域（info）存放權(quán)值。41頂點(diǎn)結(jié)點(diǎn)有3個(gè)域，分別是：data域、指向以該頂點(diǎn)為弧頭或弧尾的第一個(gè)弧結(jié)點(diǎn)（firtin、firsout）?；〗Y(jié)點(diǎn)tailvexheadvexhlinktlinkinfoDataFirstifirstout頂點(diǎn)結(jié)點(diǎn)42例：有向圖的十字鏈表表示方法為：V1V2^V3V402^0131^32^^23^^30^20有向圖10230123以此類推，得出P165的有向圖的十字鏈表圖7.11以V1為弧頭的結(jié)點(diǎn)以V1為弧尾的結(jié)點(diǎn)弧頭相同者431、結(jié)點(diǎn)結(jié)構(gòu)

鄰接多重表是無向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接多重表中，每條邊用一個(gè)結(jié)點(diǎn)表示，每個(gè)結(jié)點(diǎn)由5個(gè)域組成，其結(jié)點(diǎn)結(jié)構(gòu)如下圖所示。其中，mark是標(biāo)志域，可用來標(biāo)記這條邊是否訪問過；ivex和jvex為該邊依附的兩個(gè)頂點(diǎn)vi、vj的序號(hào)；ilink指向依附于頂點(diǎn)vi的下一條邊；jlink指向依附于頂點(diǎn)vj的下一條邊。

7.2.4鄰接多重表44

而圖或網(wǎng)中每一個(gè)頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)由數(shù)據(jù)域(data)和指針域(firstarc)組成，數(shù)據(jù)域存放與該頂點(diǎn)有關(guān)的信息，指針域指示依附于該頂點(diǎn)的第一條邊。其結(jié)點(diǎn)結(jié)構(gòu)如下所示：

45

typedefstructarcnode {intmark，ivex，jvex；

structarcnode*ilink，*jlink；

}edgenode；

typedefstructvexnode{intdata；

structarcnode*firstarc；

}vexnode；2、類型定義：46圖7.6鄰接多重表示例例：無向圖的鄰接多重表。依附于1的下一條邊是依附于2的下一條邊是47作業(yè)基礎(chǔ)知識(shí)：題集7.1。48

和樹的遍歷運(yùn)算類似，圖的遍歷（TraversingGraph）是指從圖中的任一個(gè)頂點(diǎn)出發(fā)訪問圖中所有頂點(diǎn)，并且使每個(gè)頂點(diǎn)僅被訪問一次的運(yùn)算。由于圖結(jié)構(gòu)本身的復(fù)雜性，使得圖的遍歷要比樹的遍歷復(fù)雜得多。圖的遍歷是圖的一種重要操作，對(duì)圖的許多操作都可在遍歷過程中完成，如求解圖的連通性、拓?fù)渑判蚝颓箨P(guān)鍵路徑等問題。

7.3圖的遍歷49

根據(jù)搜索路徑的方向不同，通常有兩種遍歷圖的方法：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷，這兩種遍歷方法對(duì)無向圖或有向圖都適用。50

7.3.1深度優(yōu)先搜索遍歷

1、圖的深度優(yōu)先搜索圖的深度優(yōu)先搜索（DepthFirstSearch）遍歷類似于樹的前序遍歷。假設(shè)給定圖G的初始狀態(tài)是所有頂點(diǎn)都未被訪問過，在圖G中任選一個(gè)頂點(diǎn)v0為初始出發(fā)點(diǎn)，則深度優(yōu)先搜索遍歷的基本思想是：首先訪問頂點(diǎn)v0，并將其標(biāo)記為已被訪問過，然后，依次從v0出發(fā)搜索v0的每一個(gè)鄰接點(diǎn)，若未被訪問過，則以該鄰接點(diǎn)為出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索。具體作法是：首先訪問頂點(diǎn)v0，并將其標(biāo)記為已被訪問過，再訪問一個(gè)與v0相鄰的未被訪問過的頂點(diǎn)vi，接著訪問一個(gè)與vi相鄰接且未被訪問過的頂點(diǎn).51具體作法是：首先訪問頂點(diǎn)v0，并將其標(biāo)記為已被訪問過，再訪問一個(gè)與v0相鄰的未被訪問過的頂點(diǎn)vi，接著訪問一個(gè)與vi相鄰接且未被訪問過的頂點(diǎn)Vj，……，依此類推，直到某個(gè)被訪問的頂點(diǎn)的所有鄰接點(diǎn)均被訪問過為止，然后退回到尚有鄰接點(diǎn)未被訪問過的頂點(diǎn)vr，再?gòu)捻旤c(diǎn)vr的一個(gè)未被訪問的鄰接點(diǎn)出發(fā)，重復(fù)上述過程，直到圖中所有和v0有路徑相通的頂點(diǎn)都已被訪問過為止。例如，圖7.7中圖G，若從v1出發(fā)深度優(yōu)先搜索遍歷，結(jié)點(diǎn)的訪問順序可為:v1→v2→v5→v8→v4→v3→v6→v7。52例如，圖7.7中圖G，若從v1出發(fā)深度優(yōu)先搜索遍歷，結(jié)點(diǎn)的訪問順序可為（不是唯一的）:v1→v2→v5→v8→v4→v3→v6→v7。演示深度優(yōu)先遍歷圖.swf53voiddfs(vexnodeag[]，intv，intflag[])/*從v出發(fā)對(duì)圖g深度優(yōu)先搜索*/{edgenode*p；inti；flag[v]=l；/*作標(biāo)志用

printf(“％c＼n”，ag[v].vexdata)；/*訪問頂點(diǎn)v，設(shè)頂點(diǎn)類型為字符型*/p=ag[v].firstarc；/*p最初指向V的第一個(gè)鄰接點(diǎn)*/while（p!=NULL）

{i=p->adjvex；/*取出p指針?biāo)膏徑狱c(diǎn)的序號(hào)*/

2、深度優(yōu)先搜索遍歷的遞歸算法54

if(flag[i]==0)dfs(ag，i，flag)；p=p->link；/*查找下一個(gè)鄰接點(diǎn)*/}}

對(duì)整個(gè)圖深度優(yōu)先搜索遍歷的算法blt如下：

voidblt(vexnodeag[]，intn)/*對(duì)圖g按深度優(yōu)先搜索遍歷*/{inti；

intflag[M]；

for(i=1；i<=n；i++)flag[i]＝0；/*初始化標(biāo)志數(shù)組flag*/for(i=1；i<=n；i++)if(flag[i]==0)dfs(ag，i，flag)；/*調(diào)用深度優(yōu)先搜索算法dfs*/}551、圖的廣度優(yōu)先搜索廣度優(yōu)先搜索（BreadthFirstSearch）遍歷類似于樹的按層次遍歷。假設(shè)給定圖G的初始狀態(tài)是所有頂點(diǎn)都未被訪問過，在圖G中任選一個(gè)頂點(diǎn)v0為初始出發(fā)點(diǎn)，則廣度優(yōu)先搜索遍歷的基本思想是：首先訪問頂點(diǎn)v0，并將其標(biāo)記為已被訪問過，接著依次訪問v0的所有未被訪問過的鄰接點(diǎn)vl、v2、…、vd，然后，再依次訪問vl、v2、…、vd的所有未被訪問過的鄰接點(diǎn)，依此類推，直到圖中所有被訪問過的頂點(diǎn)的7.3.2廣度優(yōu)先搜索遍歷56

鄰接點(diǎn)都被訪問過為止；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問過的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。例如，圖7.7中圖G，從v1出發(fā)得到的廣度優(yōu)先搜索遍歷頂點(diǎn)序列為:v1→v2→v3→v4→v5→v6→v7→v8演示57

2、廣度優(yōu)先搜索遍歷算法

voidbfs(vexnodeag[]，intv，intflag[]){intq[M]，r=0，f=0；

edgenode*p;printf(“％c＼n”，ag[v].vexdata)；

flag[v]=l；

q[0]=v；/*剛訪問過的頂點(diǎn)序號(hào)入隊(duì)列*/while(f<=r)/*當(dāng)隊(duì)列不空時(shí)*/{v=q[f++]；/*訪問過的頂點(diǎn)（序號(hào)）出隊(duì)列*/p=ag[v].firstarc；/*p指向v的第一個(gè)鄰接點(diǎn)*/while(p!＝NULL)/*依次搜索v的鄰接點(diǎn)*/{v=p->adjvexif(flag[v]==0)58

{flag[v]＝l；/*置已被訪問過標(biāo)志*/printf(“％c＼n”，ag[v].vexdata)；/*訪問頂點(diǎn)v*/ q[++r]=v；/*被訪問過的頂點(diǎn)入隊(duì)列*/ }p=p->link；/*查找下一個(gè)鄰接點(diǎn)*/}}}/*bfs*/59作業(yè)基礎(chǔ)知識(shí)：題集7.3；601、生成樹在一個(gè)連通圖中,如果取它的全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖G`，即，若邊集中的邊既將G中的所有頂點(diǎn)連通又不形成回路，則稱子圖G`是原圖G的一棵生成樹。一個(gè)含n個(gè)頂點(diǎn)的連通圖的生成樹是圖的一個(gè)極小連通子圖，它包含圖中全部的n個(gè)頂點(diǎn)和足以保證任意兩頂點(diǎn)連通所需的n-1條邊。若從一個(gè)連通圖的任何一個(gè)頂點(diǎn)出發(fā)對(duì)圖進(jìn)行搜索遍歷，遍歷過程中經(jīng)過的邊（不7.4圖的連通性問題7.4.1生成樹和最小生成樹61含回邊）加上圖的所有頂點(diǎn)就可以構(gòu)成圖的生成樹。例如，深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖7.8給出了連通圖G及其生成樹。622、最小生成樹

若將一個(gè)帶權(quán)圖（網(wǎng)）的其對(duì)應(yīng)生成樹上的各邊權(quán)值之和稱為該生成樹的代價(jià)，那么，最小代價(jià)生成樹（簡(jiǎn)稱最小生成樹）就是指各邊權(quán)值的總和最小的生成樹。例如，圖7.9（a）所示的網(wǎng)G，其最小生成樹如圖7.9（b）所示。顯然，一個(gè)連通網(wǎng)的最小生成樹可能不是唯一的，但它們的總代價(jià)一定相同。

最小生成樹在實(shí)際應(yīng)用中有廣泛的用途。例如，假設(shè)要在n個(gè)城市之間建立通訊網(wǎng)絡(luò)，若用圖的頂點(diǎn)表示城市，邊表示連接兩城市之間的通信線路，則圖的生成樹就表示了可行的通訊網(wǎng)絡(luò)的方案。如果圖中的邊都帶上權(quán)，而且邊上的權(quán)值表示兩個(gè)城市之間的63通信線路，則圖的生成樹就表示了可行的通訊網(wǎng)絡(luò)的方案。如果圖中的邊都帶上權(quán)，而且邊上的權(quán)值表示兩個(gè)城市之間的距離，或者表示兩個(gè)城市之間建立通訊網(wǎng)絡(luò)所花的代價(jià)等。上面的問題就是要求構(gòu)造一個(gè)連通網(wǎng)的最小生成樹的問題。又如，在某個(gè)地區(qū)的一些村莊間要修建公路。公路的修建計(jì)劃可以用一個(gè)網(wǎng)來表示，用頂點(diǎn)表示村莊，邊表示連接兩個(gè)村莊間的公路，邊上的權(quán)值表示修建該條公路所需的代價(jià)，如果希望修建公路總費(fèi)用最小且各村莊間都有公路相通，則問題轉(zhuǎn)化為只要找到該公路網(wǎng)的一棵最小代價(jià)生成樹即可。

6465

3、最小生成樹的MST性質(zhì)設(shè)G=（V，E）是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)真子集（即）。若（u，v）是一條具有最小權(quán)值的邊，其中一個(gè)端點(diǎn)在U里，另一個(gè)端點(diǎn)不在U里（即u∈U，v∈V-U），則一定存在一棵包含此邊（u，v）的最小生成樹。這個(gè)性質(zhì)稱為MST性質(zhì)。那如何利用MST性質(zhì)來構(gòu)造最小生成樹呢？普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法就是其中較常用的兩種。66

1、普里姆（Prim）算法

普里姆（Prim）算法是從連通網(wǎng)中的一個(gè)頂點(diǎn)開始，以此作為生成樹的初始狀態(tài)，然后不斷地將網(wǎng)中的其它頂點(diǎn)添加到生成樹上而最終得到最小生成樹。假設(shè)一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)N=（V，E），T=（U，TE）是N的最小生成樹，U和TE的初值均為空集。首先從網(wǎng)N中任選一個(gè)頂點(diǎn)（設(shè)為u0），把這個(gè)頂點(diǎn)包括在生成樹里，即令U={u0}，TE=Φ，然后在那些其一個(gè)端點(diǎn)已在生成樹中另一個(gè)端點(diǎn)還未在生成樹里的邊（設(shè)為（u，v），7.4.2普里姆算法67

且u∈U，v∈V-U）中查找權(quán)值最小的一條邊（設(shè)為（u0，v0）），并把這條邊和邊所依附的那個(gè)不在生成樹中的端點(diǎn)添加進(jìn)生成樹中，即將（u0，v0）加入到TE中，同時(shí)把v0也加入到U中，如此進(jìn)行，每次往生成樹里加一個(gè)頂點(diǎn)和一條權(quán)值最小的邊，直到把所有的頂點(diǎn)都包括進(jìn)生成樹中為止，從而

T=（U，TE）即為N的最小生成樹。68

利用普里姆算法從頂點(diǎn)v1開始構(gòu)造連通網(wǎng)G的最小生成樹的過程。69

設(shè)立一個(gè)輔助數(shù)組closedge用以記錄每一次選擇的從U到V-U中具有最小權(quán)值的邊。設(shè)closedge數(shù)組下標(biāo)從1開始，數(shù)組中的元素closedge[i]對(duì)應(yīng)于序號(hào)為i的頂點(diǎn)vi，它包含adjvex和lowcost域。若頂點(diǎn)vi已在生成樹U中，則置closedge[i].lowcost=0；若頂點(diǎn)vi不在生成樹中，則用closedge[i].lowcost存放vi與生成樹中的頂點(diǎn)構(gòu)成的最小代價(jià)邊的權(quán)值，而用closedge[i].adjvex存放該最小邊所關(guān)聯(lián)的已在生成樹上的另一個(gè)頂點(diǎn)的序號(hào)。假設(shè)無向連通網(wǎng)以鄰接矩陣g存儲(chǔ)，從序號(hào)為k的頂點(diǎn)vk開始構(gòu)造最小生成樹，則輔助數(shù)組的初始2、普里姆（Prim）算法實(shí)現(xiàn)70情況為：closedge[k].lowcost=0，closedge[i].lowcost=g[k][i]，losedge[i].adjvex=k然后從數(shù)組中選出某一個(gè)j，若它滿足closedge[j].lowcost不等于0且是最小的值，則將vj添加到生成樹中，并修改closedge數(shù)組中的值，如此不斷進(jìn)行下去，直到全部的n個(gè)頂點(diǎn)都在生成樹中，從而就得到了要求的最小生成樹。71普里姆（Prim）算法描述：

#defineM50#defineMAXVAL999/*設(shè)MAXVAL為權(quán)值的上限*/struct{intadjvex；

floatlowcost；

}closedge[M]；

voidprim(mgraphg，intk){inti，j，p，v；

floatmin；

for(i=1；i<=g->n；i++)/*輔助數(shù)組初始化*/72

if(i!=k){closedge[i].adjvex=k；

closedge[i].lowcost=g->arcs[k][i]；

}closedge[k].lowcost=0；

for(j=1；j<=g->n；j++) {p=1；min=MAXVAL；

for(v=1；v<=g->n；v++)/*選取最小的權(quán)值及對(duì)應(yīng)的頂點(diǎn)Vp*/ if（（closedge[v].lowcost!=0）&&（closedge[v].lowcost<min））

{min=closedge[v].lowcost；p=v；

}73

printf(“%d%d%f\n”，closedge[p].adjvex，p，min)； closedge[p].lowcost=0；for(j=1；j<=g->n；j++)if(g->arcs[p][j]<closedge[j].lowcost){closedge[j].lowcost=g->arcs[p][j]；/*修改權(quán)值*/closedge[j].adjvex=p；

}}}/*prim*/

圖7.11給出了從頂點(diǎn)V1出發(fā)算法實(shí)現(xiàn)過程中輔助數(shù)組中各分量的值。普里姆算法的時(shí)間復(fù)雜度是O（n2），它適用于求邊稠密的網(wǎng)的最小生成樹。74757.4.3克魯斯卡爾算法

克魯斯卡爾（Kruskal）算法的基本思想是：假設(shè)連通網(wǎng)N=（V，E），令最小生成樹的初始狀態(tài)為無邊相連的n個(gè)相互獨(dú)立的頂點(diǎn)組成的非連通圖T=（V，{Φ}），圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量，并將e條邊按權(quán)值大小由小到大排序；在網(wǎng)的邊集E中從權(quán)值最小的邊開始依權(quán)值遞增順序查看每一條邊，如果該邊所依附的兩個(gè)頂點(diǎn)在不同的連通分量上，則選定此邊連接兩個(gè)連通分量為一個(gè)連通分量，即將此邊加入到T中，否則舍棄此邊而再76

選擇下一條權(quán)值次小的邊，依此類推，直至T中所有的頂點(diǎn)都在同一個(gè)連通分量上為止，此時(shí)，這個(gè)連通分量T就是一棵最小生成樹。Kruskal算法適合于求邊稀疏的無向連通網(wǎng)的最小生成樹。圖7.12給出了按克魯斯卡爾算法構(gòu)造連通網(wǎng)（圖（a））的最小生成樹的過程。77(c)(d)(e)78作業(yè)基礎(chǔ)知識(shí)：題集7.7；797.5有向無環(huán)圖及其應(yīng)用7.5.1拓?fù)渑判?/p>

1、有向無環(huán)圖有向無環(huán)圖（簡(jiǎn)稱為DAG圖）是指無環(huán)的有向圖，它是一類比有向樹更一般的特殊有向圖。如圖7.18給出了有向樹、DAG圖和有向圖的例子，（a）、（b）、（c）都是有向圖，（a）、（b）都是DAG圖，只有（a）是有向樹。利用有向無環(huán)圖可實(shí)現(xiàn)對(duì)相同子式的共享，從而節(jié)省存儲(chǔ)空間（如P179圖7.22、7.23所示）。8081

有向無環(huán)圖常用于描述任務(wù)安排問題。一般地說，一個(gè)較大的工程往往被劃分成許多子工程，這些子工程稱為活動(dòng)(Activity)，這些子工程之間通常受到一定條件的約束，但有些子工程沒有先決條件。只有這些子工程都順利完成后，整個(gè)工程才能完成。例如，一件設(shè)備的生產(chǎn)過程包含著許多工序；一個(gè)教學(xué)計(jì)劃包含許多課程等等。在每個(gè)計(jì)劃包含的許多活動(dòng)之間，各種計(jì)劃的執(zhí)行之間可能存在著先決條件。2、AOV網(wǎng)82

這種各個(gè)活動(dòng)之間的次序關(guān)系可以用一個(gè)有向圖來表示，圖中的每個(gè)頂點(diǎn)代表一個(gè)活動(dòng)。如果從頂點(diǎn)vi到vj之間存在弧<vi,vj>，則表示活動(dòng)i必須先于活動(dòng)j進(jìn)行，這種用頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)間先后關(guān)系的有向圖叫做頂點(diǎn)活動(dòng)網(wǎng)(ActivityOnVertexNetwork)，簡(jiǎn)稱AOV網(wǎng)。例如，圖7.19是關(guān)于計(jì)算機(jī)專業(yè)教學(xué)計(jì)劃中各課程之間的關(guān)系。它對(duì)應(yīng)的AOV網(wǎng)如圖7.20所示8384

AOV網(wǎng)應(yīng)該是有向無環(huán)圖，即不應(yīng)該出現(xiàn)回路。若帶有回路，從而使回路上的所有活動(dòng)都無法進(jìn)行，如圖7.21所示。85

3、拓?fù)渑判蛟贏OV網(wǎng)中，若不存在回路，則可將所有活動(dòng)排列成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有先決活動(dòng)都排在該活動(dòng)的前面。將一個(gè)有向無環(huán)圖中所有頂點(diǎn)在不違反先決條件的基礎(chǔ)上排成線性序列的過程稱為拓?fù)渑判?，并稱此線性序列為拓?fù)湫蛄小Ｓ葾OV網(wǎng)構(gòu)造拓?fù)湫蛄械膶?shí)際意義在于若按照拓?fù)湫蛄兄械捻旤c(diǎn)次序進(jìn)行每一項(xiàng)活動(dòng)，就能保證在開始每一項(xiàng)活動(dòng)時(shí)，它的所有前趨或先決活動(dòng)都已完成，從而使得整個(gè)工程按順序進(jìn)行。86

AOV網(wǎng)拓?fù)渑判颍海?）在AOV網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)(即沒有前趨的頂點(diǎn))，并將其輸出；（2）從網(wǎng)中刪除該頂點(diǎn)及以它為尾（即以該頂點(diǎn)為出發(fā)點(diǎn)）的所有弧即所有出邊；（3）重復(fù)執(zhí)行上述兩步，直到全部頂點(diǎn)被輸出，即拓?fù)渑判蛲瓿桑蛘弋?dāng)前的有向圖中不存在無前趨（入度為0）的頂點(diǎn)，說明該有向圖中存在有向環(huán)，拓?fù)渑判虿荒芾^續(xù)進(jìn)行下去。圖7.22給出了對(duì)有向無環(huán)圖G進(jìn)行拓?fù)渑判虻玫巾旤c(diǎn)的輸出序列的過程。87對(duì)于此圖也可以構(gòu)造得其它的拓?fù)溆行蛐蛄小?8

4、拓?fù)渑判蛩惴▽?shí)現(xiàn)采用鄰接表（如圖7.23所示）作為給定AOV網(wǎng)的存儲(chǔ)結(jié)構(gòu)，并在表頭結(jié)點(diǎn)中增設(shè)一個(gè)入度域in，用于存放各個(gè)頂點(diǎn)當(dāng)前的入度值，這樣，要選擇并輸出一個(gè)入度為0的頂點(diǎn)只要對(duì)頂點(diǎn)表的入度域進(jìn)行掃描即可實(shí)現(xiàn)，而刪除頂點(diǎn)和以它為尾的弧的操作只要將弧頭頂點(diǎn)的入度減1就可實(shí)現(xiàn)，即在輸出某個(gè)頂點(diǎn)后，要將該頂點(diǎn)的所有鄰接點(diǎn)的入度值減1。如在圖7.23中。8990

設(shè)置一個(gè)鏈棧來存放所有入度為0的頂點(diǎn)，每當(dāng)輸出頂點(diǎn)就從棧中彈出一個(gè)，每當(dāng)出現(xiàn)新的入度為0的頂點(diǎn)便將其入棧保存，并利用該頂點(diǎn)的入度域作為鏈棧單元使用，用于存放下一個(gè)入度為0的頂點(diǎn)序號(hào)。這樣，通過所有入度為0的表頭結(jié)點(diǎn)中的入度域就可以把入度為0的頂點(diǎn)（對(duì)應(yīng)表頭結(jié)點(diǎn)）都靜態(tài)鏈接起來。用鄰接表表示的AOV網(wǎng)的拓?fù)渑判蛩惴ú襟E如下：（1）掃描鄰接表，把所有入度值為0的頂點(diǎn)入棧；91

（2）當(dāng)棧非空時(shí)，將棧頂頂點(diǎn)元素出棧并輸出，然后在鄰接表中檢查該頂點(diǎn)的直接后繼即鄰接點(diǎn)，并把各鄰接頂點(diǎn)的入度值減l；（3）將新產(chǎn)生的入度為0的頂點(diǎn)入棧；（4）重復(fù)步驟（2）、（3），直至?？諘r(shí)為止，若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n（即小于n），則說明有向圖中有環(huán)，不可進(jìn)行拓?fù)渑判颍駝t，拓?fù)渑判蛲瓿伞?2#defineM50typedefstructnode/*邊表結(jié)點(diǎn)*/{intadjvex；/*鄰接點(diǎn)域*/structnode*next；/*指針域*/}edgenode；typedefstructheadnode/*頂點(diǎn)表頭結(jié)點(diǎn)*/{vextypevex；

intin；/*入度域*/edgenode*firstarc；/*指針域指向鏈表中第一個(gè)結(jié)點(diǎn)*/}vexnode；typedefvexnodeadjlist；/*adjlist為鄰接表類型*/AOV網(wǎng)的鄰接表的表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的類型定義如下：93拓?fù)渑判虻乃惴ǎ?/p>

inttopsort(adjlistg[]，intn){inttop，m，k，i，j；edgenode*p；

m=0；top=0；

for(i=1；i<=n；i++)if(g[i].in==0){g[i].in=top；top=i；

}while(top!=0){j=top；top=g[top].in；

printf(“％d＼t”，g[j].vex)；

m++；

p=g[j].firstarc；94

while(p!=NULL){k=p->adjvex；

g[k].in--；

if(g[k].in==0){g[k].in=top；top=k；

}p=p->next；

}}printf(“m=％d＼t”，m)；if（m<n）{printf(“thenetworkhasacycle\t”)；return(0)；

}95

elsereturn(1)；

}/*topsort*/

對(duì)拓?fù)渑判蚨?，具有n個(gè)頂點(diǎn)e條邊的AOV網(wǎng)建立鄰接表需O(n+e)的時(shí)間，搜索入度為０的頂點(diǎn)需O(n)的時(shí)間。在拓?fù)渑判蜻^程中若AOV網(wǎng)無環(huán)路，每個(gè)頂點(diǎn)入棧和出棧各n次，入度減１的操作共執(zhí)行e次，所需時(shí)間為Ｏ(n+e)，所以算法總的時(shí)間復(fù)雜度為Ｏ(n+e)。967.5.2關(guān)鍵路徑

與AOV網(wǎng)相對(duì)應(yīng)的是AOE網(wǎng)（ActivityOnEdge），用事件作頂點(diǎn)，用活動(dòng)作有向邊，這樣的圖稱為事件結(jié)點(diǎn)網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖，（Event），弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間，通常，AOE網(wǎng)在工程計(jì)劃上可用來估算工程完成的時(shí)間。97V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2圖7.29一個(gè)AOE網(wǎng)

例如，P183圖7.29是一個(gè)有9件事情（頂點(diǎn)），11項(xiàng)活動(dòng)（?。┑腁OE網(wǎng)。與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間，比如，活動(dòng)a1需要6天，活動(dòng)a2需要4天等。98

事件V1表示整個(gè)工程可以開始，事件V5表示活動(dòng)a4,a5已經(jīng)完成，活動(dòng)a7,a8可以開始這個(gè)狀態(tài)，事件V9表示整個(gè)工程結(jié)束。整個(gè)工程一開始，活動(dòng)a1,a2,a3就可以并行地進(jìn)行，而活動(dòng)a4,a5,a6只有當(dāng)事件V2,V3,V4分別發(fā)生后才能進(jìn)，當(dāng)活動(dòng)a10,a11完成后，整個(gè)工程就可以完成了。V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2圖7.29一個(gè)AOE網(wǎng)

99

表示實(shí)際工程計(jì)劃的事件網(wǎng)絡(luò)應(yīng)該是無環(huán)的，且存在唯一的入度為0的開始結(jié)點(diǎn)（如圖中的V1）及唯一的出度為0的完成結(jié)點(diǎn)（如圖中的V9）。利用事件結(jié)點(diǎn)網(wǎng)絡(luò)可以進(jìn)行工程安排估算，研究完成整個(gè)工程至少需要多少時(shí)間，為縮短整個(gè)工程的完成時(shí)間應(yīng)該加快哪些活動(dòng)的速度。為解決這問題，可采用PERT、CMP等技術(shù)。

V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2圖7.29一個(gè)AOE網(wǎng)

100

因?yàn)樵谑录Y(jié)點(diǎn)網(wǎng)絡(luò)中，活動(dòng)可以并行地進(jìn)行，所以完成整個(gè)工程的最少時(shí)間是從開始結(jié)點(diǎn)到完成結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度（路徑長(zhǎng)度等于路徑上各邊的權(quán)值之和）。具有最大長(zhǎng)度的路徑稱作關(guān)鍵路徑。如圖中路徑V1，V2，V5，V8，V9是一條關(guān)鍵路徑，長(zhǎng)度為18，也就是說整個(gè)工程至少要18天才能完成。

V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2圖7.29一個(gè)AOE網(wǎng)

101

分析關(guān)鍵路徑的目的是找出關(guān)鍵活動(dòng)，即不按期完成就會(huì)影響整個(gè)工程的完成的時(shí)間的活動(dòng)，例如圖中a1,a4等。找到了關(guān)鍵活動(dòng)就可以適當(dāng)調(diào)度，投入較多的人力和物力在關(guān)鍵活動(dòng)上，才能保證整個(gè)工程按期完成，并可爭(zhēng)取提前完成。V1V2V3V4V5V6V7V8V9a1=6a2=4a3=5a5=1a4=1a6=2a8=7a7=9a9=4a11=4a10=2圖7.29一個(gè)AOE網(wǎng)

102

為找關(guān)鍵活動(dòng)，先定義幾個(gè)相關(guān)的量：（1）事件Vi的最早發(fā)生時(shí)間e(i)是從結(jié)點(diǎn)V1到Vi的最長(zhǎng)路徑長(zhǎng)度，這個(gè)時(shí)間決定了所有以Vi為尾的弧所表示的活動(dòng)的最早開始時(shí)間。例如：事件v9最早發(fā)生時(shí)間為：

從v1到v9的最長(zhǎng)路徑長(zhǎng)度18；例如：活動(dòng)a6最早開始時(shí)間為:e(6)=5；頭k尾jai頂點(diǎn)vi103（2）事件Vi的最遲開始時(shí)間l(i)，這是在不推遲整個(gè)工程完成的前提下，活動(dòng)ai最遲必須開始的時(shí)間，例如活動(dòng)a6最遲開始時(shí)間為8。即如果a6推遲3天開始或者延遲3天完成，都不會(huì)影響整個(gè)工程的完成。頭k尾jai104最遲開始時(shí)間計(jì)算方法為：l(i)=關(guān)鍵路徑長(zhǎng)度-（Vi到Vn的最長(zhǎng)路徑長(zhǎng)度）。例如：a6最遲開始時(shí)間為l(i)=18-（2+4+4）=8。兩者之差l(i)-e(i)意味著完成ai的時(shí)間余量。即如果a6推遲3天開始或者延遲3天完成，都不會(huì)影響整個(gè)工程的完成。頭k尾jai105將l(i)=e(i)的活動(dòng)叫做關(guān)鍵活動(dòng)。顯然，關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)。求關(guān)鍵路徑的算法及分析P184、185。106

最短路徑是指路徑長(zhǎng)度（即路徑上邊的權(quán)值之和或邊的條數(shù)）最小的路徑。在實(shí)際應(yīng)用中存在著許多有關(guān)有向帶權(quán)圖的最短路徑問題。例如，若用一個(gè)圖表示城市之間的運(yùn)輸網(wǎng)，如何能夠使得從一個(gè)城市到另一個(gè)城市的運(yùn)輸時(shí)間最少或代價(jià)最少呢？這就是一個(gè)求兩個(gè)城市之間的最短路徑問題。本節(jié)討論求帶權(quán)有向圖的最短路徑的兩個(gè)常用算法，且假定所有的權(quán)值都是7.6最短路徑

107

正數(shù)。一般的，求帶權(quán)有向圖的最短路徑包括兩種情況：（1）求圖中一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑；（2）求圖中每對(duì)頂點(diǎn)之間的最短路徑。1087.6.1單源最短路徑

1、單源最短路徑將路徑上的起始頂點(diǎn)稱為源點(diǎn)，路徑上的最后一個(gè)頂點(diǎn)稱為終點(diǎn)。單源最短路徑是指從一個(gè)頂點(diǎn)（源點(diǎn)）出發(fā)到其它各頂點(diǎn)的最短路徑，即給定有向網(wǎng)G和源點(diǎn)vi，求從vi到G中其它各頂點(diǎn)vj（j=1，2，…，n，j≠k）的最短路徑。

2、Dijkstra算法描述迪杰斯特拉(E.WDijkstra)提出了求單源最短路徑的一般算法——按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑。109

基本思路是：

按照從源點(diǎn)到其余每一個(gè)頂點(diǎn)的最短路徑長(zhǎng)度的遞增順序依次求出從源點(diǎn)到其它各頂點(diǎn)的最短路徑及長(zhǎng)度，每次求出從源點(diǎn)vi到一個(gè)終點(diǎn)vj的最短路徑及長(zhǎng)度后，都要以vj作為新考慮的中間點(diǎn)，用vi到vj的最短路徑和最短路徑長(zhǎng)度對(duì)vi到其它尚未最后求出最短路徑的那些終點(diǎn)的當(dāng)前最短路徑及長(zhǎng)度作必要的修改，使之成為當(dāng)前新的最短路徑和最短路徑長(zhǎng)度，當(dāng)進(jìn)行n-2次后算法結(jié)束。110

具體做法：把圖中所有頂點(diǎn)分成兩組，第一組由已確定最短路徑的頂點(diǎn)組成（設(shè)為集合S），第二組包括尚未確定最短路徑的頂點(diǎn)（設(shè)為集合V），開始時(shí)，第一組S只包括頂點(diǎn)vi，第二組包括其余的所有頂點(diǎn)，若令vi對(duì)應(yīng)的距離值為0，則第二組V中的頂點(diǎn)對(duì)應(yīng)的距離值可以按下列方式確定：若圖中有弧<vi，vj>，則將此弧的權(quán)值作為vj的距離值，否則vj的距離值為∞（或用一個(gè)很大的數(shù)MAXVAL表示），然后每次從第二組V的頂點(diǎn)中選一個(gè)其距離值為最小的頂點(diǎn)（設(shè)為vmin）加入到第一組S中，每次往第一組S中加入一個(gè)頂點(diǎn)111vmin，就要對(duì)第二組V中的各個(gè)頂點(diǎn)的距離值進(jìn)行一次修改。若以加入的頂點(diǎn)vmin做中間頂點(diǎn)，使得從vi到vj的最短路徑比未加入頂點(diǎn)vmin的路徑更短，則要修改vj的距離值，然后再繼續(xù)選取距離值最小的頂點(diǎn)加入到第一組S中，如此進(jìn)行下去，直到圖中所有頂點(diǎn)都包括在第一組S中，或不存在可加入到第一組S中的頂點(diǎn)為止。112

用dist[j]（設(shè)下標(biāo)從1開始）表示在當(dāng)前時(shí)刻所找到的從源點(diǎn)vi到終點(diǎn)vj的最短路徑長(zhǎng)度，其初始值為：dist[i]=0，若存在弧<vi，vj>，則dist[j]為其弧上的權(quán)值，若不存在弧<vi，vj>，則dist[j]=∞。這樣，最短路徑長(zhǎng)度就可通過dist數(shù)組各元素得到。若用數(shù)組pre的每個(gè)單元存放從起始頂點(diǎn)vi到以下標(biāo)為序號(hào)的頂點(diǎn)的路徑上此頂點(diǎn)的前一個(gè)頂點(diǎn)的序號(hào)，如用pre[j]表示從源點(diǎn)vi到頂點(diǎn)vj的最短路徑上vj前一個(gè)頂點(diǎn)的序號(hào)即前趨頂點(diǎn)，若從

3、Dijkstra算法實(shí)現(xiàn)113vi到vj沒有路徑可達(dá)，則用0作為vj的前一個(gè)頂點(diǎn)的序號(hào)，這樣，就可利用pre數(shù)組將最短路徑也記下來。在算法結(jié)束前，可根據(jù)pre數(shù)組找到源點(diǎn)到頂點(diǎn)vj的最短路徑上每個(gè)頂點(diǎn)的前趨頂點(diǎn)，即沿著頂點(diǎn)vj對(duì)應(yīng)的pre[j]回溯，從而得到從頂點(diǎn)vi出發(fā)到vj的最短路徑，且其最短路徑長(zhǎng)度等于dist[j]。

Dijkstra算法描述如下：114

#defineMAXVAL99999voiddijkstra(mgraphg，floatdist[]，intpre[]，inti){intj，k，p，v；floatmin；

for(j=1；j<=g->n；j++)/*數(shù)組dist和pre初始化，即置初始距離值*/{dist[j]=g->arcs[i][j]；

if(dist[j]<MAXVAL)pre[j]＝i；

elsepre[j]=0；

} pre[i]=0；dist[i]=0；/*數(shù)組dist和pre初始化*/g->arcs[i][i]=1；115

for(k=1；k<=g->n-1；k++){min=MAXVAL；/*設(shè)MAXVAL為最大數(shù)/*j=-1；

for(p=1；p<=g->n；p++) if((g->arcs[p][p]==0)&&(dist[p]<min)){j=p；min=dist[p]；

}/*if*/ if(j==-l)break；/*已沒有頂點(diǎn)可往第一組加入，則退出*/else{g->arcs[j][j]=1；

for(v=1；v<=g->n；v++)116if((g->arcs[v][v]==0)&&(min+g->arcs[j][v]<dist[v])) {dist[v]=min+g->arcs[j][v];pre[v]=j；

}}/*else*/}/*for*/}/*dijkstra*/

用Dijkstra算法求圖7.13所示的帶權(quán)有向圖G從頂點(diǎn)V1到其它各頂點(diǎn)的最短路徑，其算法執(zhí)行過程中dist數(shù)組和pre數(shù)組的變化情況如圖7.14所示。可得路徑為：V1→V3→V4→V5，路徑長(zhǎng)度為dist[5]=13。

Dijkstra算法的時(shí)間復(fù)雜度為O(n2)。117118直接路徑間接路徑1197.6.2所有頂點(diǎn)對(duì)之間的最短路徑

1、所有頂點(diǎn)對(duì)之間的最短路徑是指圖中任意兩個(gè)頂點(diǎn)vi和v