圖的基本概念

1第7章圖7.1圖的基本概念7.2圖的存儲結(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é)點和終端結(jié)點外，每個結(jié)點只有唯一的直接前趨和直接后繼，結(jié)點之間存在一對一的線性關(guān)系；在樹形結(jié)構(gòu)中，結(jié)點之間存在一對多的層次關(guān)系，除根結(jié)點外，每個結(jié)點只能有一個直接前趨（即雙親），但每個結(jié)點允許有零或多7.1圖的基本概念3個直接后繼（即孩子），即每一層上的結(jié)點可以與它下面一層中的多個結(jié)點相關(guān)，但是只能和它上面一層的一個結(jié)點（雙親結(jié)點）相關(guān)。而在圖結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是一種多對多的網(wǎng)狀關(guān)系，任意兩個數(shù)據(jù)元素之間都可能相關(guān)。4

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

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

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

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

1圖的定義6

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

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

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

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

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

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

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

5度、入度和出度16

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

6路徑與回路17

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

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

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

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

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

22

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

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

A[i，j]＝

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

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

在有向圖中，頂點Vi的出度是鄰接矩陣A中第i行非零元素個數(shù)之和，而頂點Vi的入度是鄰接矩陣A中第i列非零元素個數(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/*最大頂點數(shù)*/typedefcharvertextype;/*頂點數(shù)據(jù)類型，此處設(shè)為char類型*/typedeffloatadjtype；/*權(quán)值類型*/typedefstruct{vertextypevex[MAXNUM];/*用一維數(shù)組表示頂點*/ adjtypearcs[MAXNUM][MAXNUM]；/*鄰接矩陣用二維數(shù)組表示*/ intn，e；/*圖的當(dāng)前頂點數(shù)和弧或邊數(shù)*/}*mgraph;

28voidcreatgraph(mgraphg) /*

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

scanf(“%d%d”，&g->n，&g->e)；/*輸入圖的頂點數(shù)和邊數(shù)*/for(i=1；i<=g->n；i++)scanf(“%c”，&g->vex[i])；/*構(gòu)造頂點向量*/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é)點結(jié)構(gòu)

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

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

#defineM50typedefstructnode{intadjvex；/*鄰接點域*/structnode*link；/*指針域*/}edgenode；

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

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

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

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

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

for(i=1；i<=n；i++){scanf(“%c”，&ch)；/*讀入頂點信息*/ag[i].vexdata=ch；/*設(shè)頂點為字符型*/ag[i].firstarc=NULL；/*將每個鏈表初始化為空*/}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é)點j插入到第i個鏈表*/p=(edgenode*)malloc(sizeof(edgenode))；

p->adjvex=i；

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

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

}}/*creatlist*/39

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

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

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

7.2.4鄰接多重表44

而圖或網(wǎng)中每一個頂點的結(jié)點結(jié)構(gòu)由數(shù)據(jù)域(data)和指針域(firstarc)組成，數(shù)據(jù)域存放與該頂點有關(guān)的信息，指針域指示依附于該頂點的第一條邊。其結(jié)點結(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ǔ)知識：題集7.1。48

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

7.3圖的遍歷49

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

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

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

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

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

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

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

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

voidblt(vexnodeag[]，intn)/*對圖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)是所有頂點都未被訪問過，在圖G中任選一個頂點v0為初始出發(fā)點，則廣度優(yōu)先搜索遍歷的基本思想是：首先訪問頂點v0，并將其標(biāo)記為已被訪問過，接著依次訪問v0的所有未被訪問過的鄰接點vl、v2、…、vd，然后，再依次訪問vl、v2、…、vd的所有未被訪問過的鄰接點，依此類推，直到圖中所有被訪問過的頂點的7.3.2廣度優(yōu)先搜索遍歷56

鄰接點都被訪問過為止；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問過的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。例如，圖7.7中圖G，從v1出發(fā)得到的廣度優(yōu)先搜索遍歷頂點序列為: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；/*剛訪問過的頂點序號入隊列*/while(f<=r)/*當(dāng)隊列不空時*/{v=q[f++]；/*訪問過的頂點（序號）出隊列*/p=ag[v].firstarc；/*p指向v的第一個鄰接點*/while(p!＝NULL)/*依次搜索v的鄰接點*/{v=p->adjvexif(flag[v]==0)58

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

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

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

6465

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

1、普里姆（Prim）算法

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

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

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

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

設(shè)立一個輔助數(shù)組closedge用以記錄每一次選擇的從U到V-U中具有最小權(quán)值的邊。設(shè)closedge數(shù)組下標(biāo)從1開始，數(shù)組中的元素closedge[i]對應(yīng)于序號為i的頂點vi，它包含adjvex和lowcost域。若頂點vi已在生成樹U中，則置closedge[i].lowcost=0；若頂點vi不在生成樹中，則用closedge[i].lowcost存放vi與生成樹中的頂點構(gòu)成的最小代價邊的權(quán)值，而用closedge[i].adjvex存放該最小邊所關(guān)聯(lián)的已在生成樹上的另一個頂點的序號。假設(shè)無向連通網(wǎng)以鄰接矩陣g存儲，從序號為k的頂點vk開始構(gòu)造最小生成樹，則輔助數(shù)組的初始2、普里姆（Prim）算法實現(xiàn)70情況為：closedge[k].lowcost=0，closedge[i].lowcost=g[k][i]，losedge[i].adjvex=k然后從數(shù)組中選出某一個j，若它滿足closedge[j].lowcost不等于0且是最小的值，則將vj添加到生成樹中，并修改closedge數(shù)組中的值，如此不斷進(jìn)行下去，直到全部的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)值及對應(yīng)的頂點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給出了從頂點V1出發(fā)算法實現(xiàn)過程中輔助數(shù)組中各分量的值。普里姆算法的時間復(fù)雜度是O（n2），它適用于求邊稠密的網(wǎng)的最小生成樹。74757.4.3克魯斯卡爾算法

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

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

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

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

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

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

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

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

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

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

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

intin；/*入度域*/edgenode*firstarc；/*指針域指向鏈表中第一個結(jié)點*/}vexnode；typedefvexnodeadjlist；/*adjlist為鄰接表類型*/AOV網(wǎng)的鄰接表的表結(jié)點和表頭結(jié)點的類型定義如下：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*/

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

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

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

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

99

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

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

100

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

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

101

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

102

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

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

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

107

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

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

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

基本思路是：

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

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

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

3、Dijkstra算法實現(xiàn)113vi到vj沒有路徑可達(dá)，則用0作為vj的前一個頂點的序號，這樣，就可利用pre數(shù)組將最短路徑也記下來。在算法結(jié)束前，可根據(jù)pre數(shù)組找到源點到頂點vj的最短路徑上每個頂點的前趨頂點，即沿著頂點vj對應(yīng)的pre[j]回溯，從而得到從頂點vi出發(fā)到vj的最短路徑，且其最短路徑長度等于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；/*已沒有頂點可往第一組加入，則退出*/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從頂點V1到其它各頂點的最短路徑，其算法執(zhí)行過程中dist數(shù)組和pre數(shù)組的變化情況如圖7.14所示?？傻寐窂綖椋篤1→V3→V4→V5，路徑長度為dist[5]=13。

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

1、所有頂點對之間的最短路徑是指圖中任意兩個頂點vi和v