軟件技術(shù)基礎(chǔ)11章為第

圖的基本概念圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷生成樹(shù)和最小生成樹(shù)最短路徑拓?fù)渑判蜿P(guān)鍵路徑習(xí)題77.1

圖的基本概念對(duì)于圖(G)這一類(lèi)較復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，可以用兩個(gè)集合V(G)和E(G)來(lái)表示其組成，在形式上可記為G=(V,E)。其中V(G)是頂點(diǎn)(Vertex)的非空有限集合；而E(G)是邊(Edge)的有限集合，用于表示V(G)中任意兩個(gè)頂點(diǎn)之間的關(guān)系集合。根據(jù)圖中每條邊是否有方向，可將圖分為有向圖和無(wú)向圖。有向圖中的每條邊均有方向，這種有向邊又稱(chēng)為弧，通常用由兩個(gè)頂點(diǎn)組成的有序?qū)?lt;起始頂點(diǎn)，終止頂點(diǎn)>來(lái)表示。其中弧的起始頂點(diǎn)稱(chēng)為弧尾，終止頂點(diǎn)稱(chēng)為弧頭。圖7.1(a)給出了一個(gè)有向圖的示例，該圖的頂點(diǎn)集和邊集分別為V(G1)={A,

B,

C}E(G1)={<B,

A>,

<B,

C>,

<C,

A>,

<C,

B>}若圖G中的每條邊均無(wú)方向，則稱(chēng)G為無(wú)向圖，如圖7.1(b)所示。無(wú)向圖的邊可以用兩個(gè)頂點(diǎn)組成的無(wú)序?qū)Ρ硎荆洖椋?/p>

(頂點(diǎn)1，頂點(diǎn)2)。這時(shí)兩個(gè)頂點(diǎn)之間最多只存在一條邊。圖

7.1(b)中無(wú)向圖G2的頂點(diǎn)集和邊集分別為：V(G2)={

A,

B,

C

}E(G2)={(A,

B),

(B,

C),

(C,

A)}={(B,

A),

(B,

C),

(C,

A)}圖7.1

有向圖和無(wú)向圖示例設(shè)圖中頂點(diǎn)數(shù)目為n，邊或弧的數(shù)目為e。對(duì)于邊，本章討論的內(nèi)容不考慮兩種特殊情況：頂點(diǎn)到其自身的邊，以及兩個(gè)頂點(diǎn)之間重復(fù)出現(xiàn)的邊或弧，分別如圖7.2(a)、(b)所示。基于以上兩條約束，邊和頂點(diǎn)之間的關(guān)系可總結(jié)如下：對(duì)于無(wú)向圖，e滿足0≤e≤n(n–1)/2。若e=n(n–1)/2，則稱(chēng)該無(wú)向圖為完全無(wú)向圖。對(duì)于有向圖，e滿足0≤e≤n(n–1)。若e=

n(n–1)，則稱(chēng)該有向圖為完全有向圖。若e<

nlgn，則稱(chēng)該圖為稀疏圖，否則為稠密圖。圖7.2

不考慮的特殊圖例假設(shè)有兩個(gè)同類(lèi)型的圖G1=(V1,E1)和G2=(V2,E2)存在關(guān)系

V1?V2,且E1?E2,則稱(chēng)G1是G2的子圖。圖7.3

給出了G1和G2的子圖的示例。圖7.3

子圖示例在無(wú)向圖G中，若存在邊(vi,vj)∈E(G)，則稱(chēng)頂點(diǎn)vi和vj互為鄰接點(diǎn)(即相互鄰接)，稱(chēng)邊(vi,vj)關(guān)聯(lián)于頂點(diǎn)vi和vj或稱(chēng)邊(vi,vj)與頂點(diǎn)vi和vj相關(guān)聯(lián)。與某一頂點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱(chēng)為vi的度，記為D(vi)。圖7.1(b)中的頂點(diǎn)A的度為2。設(shè)G為有向圖，若邊<vi,vj>∈E(G)，則稱(chēng)頂點(diǎn)vi鄰接到vj或vj鄰接于vi，并稱(chēng)邊<vi,vj>關(guān)聯(lián)于頂點(diǎn)vi和vj或稱(chēng)邊<vi,vj>與頂點(diǎn)vi和vj相關(guān)聯(lián)。有向圖中頂點(diǎn)vi的度定義為該頂點(diǎn)的入度

和出度之和。其中，vi的入度定義為以頂點(diǎn)vi為終點(diǎn)的邊的數(shù)

目，記為ID(vi)；vi的出度定義為以頂點(diǎn)vi為起點(diǎn)的邊的數(shù)目，記為OD(vi)。在圖7.1(a)中頂點(diǎn)A的入度為2，出度為0，度為2。一個(gè)圖G中有n個(gè)頂點(diǎn)，e條邊或弧，假設(shè)每個(gè)頂點(diǎn)的度為D(vi)(1≤i≤n)，則存在以下關(guān)系：(7-1)如果圖的邊或弧具有一個(gè)與它相關(guān)的數(shù)，則這個(gè)數(shù)就稱(chēng)為該邊或弧的權(quán)，這個(gè)數(shù)常用來(lái)表示一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。帶權(quán)的圖被稱(chēng)為網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)為網(wǎng)。圖7.4給出了一個(gè)有向網(wǎng)絡(luò)示例。ni=1iD(v

)21e

=圖7.4

有向網(wǎng)絡(luò)示例在一個(gè)圖中，若存在頂點(diǎn)序列(v1,

v2, …,

vn－1,vn)，使得從頂點(diǎn)v1出發(fā)可到達(dá)頂點(diǎn)vn，則稱(chēng)該頂點(diǎn)序列為從v1到vn的一條路徑。路徑的長(zhǎng)度即為路徑上邊或弧的數(shù)目。但在帶權(quán)圖中，路徑長(zhǎng)度則取沿路徑各邊的權(quán)之和。起點(diǎn)和終點(diǎn)相同的路徑稱(chēng)為回路或環(huán)。若路徑中的頂點(diǎn)不重復(fù)出現(xiàn)，則稱(chēng)該路徑為簡(jiǎn)單路徑。僅起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑被稱(chēng)為簡(jiǎn)單回路或者簡(jiǎn)單環(huán)。例如在圖7.1(b)中，(A,B,C)就是一條簡(jiǎn)單路徑，路徑長(zhǎng)度為2；而(A,B,C,A)則是一個(gè)簡(jiǎn)單環(huán)，路經(jīng)長(zhǎng)度為3。對(duì)于有向圖7.1(a)，其路徑也是有向的，例如(B,C,B)是一個(gè)有向的簡(jiǎn)單環(huán)，路徑長(zhǎng)度為2；而(A,B,C)就不是一條路徑。在有權(quán)圖7.4中，簡(jiǎn)單環(huán)(B,C,B)的路徑長(zhǎng)度則為6。如果有向圖中存在一個(gè)頂點(diǎn)v，從該頂點(diǎn)出發(fā)可到達(dá)圖中其它所有的頂點(diǎn)，則稱(chēng)該有向圖為有根圖，v稱(chēng)為該圖的根。對(duì)于無(wú)向圖G，若頂點(diǎn)vi和vj

(i≠j)有路徑相通，則稱(chēng)vi和vj是連通的。如果G中的任意兩個(gè)頂點(diǎn)都連通，則稱(chēng)G是連通圖，否則為非連通圖。圖7.1(b)就是一個(gè)連通圖實(shí)例。在無(wú)向圖G中的極大連通子圖稱(chēng)為G的連通分量。對(duì)于連通圖，連通分量就是其自身；對(duì)于非連通圖，可以存在多個(gè)連通分量。圖7.5給出了一個(gè)無(wú)向圖和它的兩個(gè)連通分量。圖7.5

無(wú)向圖及其連通分量對(duì)于有向圖G，若從vi到vj(i≠j)、從vj到vi都存在路徑，則稱(chēng)vi和vj是強(qiáng)連通的。如果G中的任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，則稱(chēng)該圖為強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱(chēng)做有向圖的強(qiáng)連通分量。例如圖7.1(a)中的有向圖不是一個(gè)強(qiáng)連通圖，而是有兩個(gè)極大強(qiáng)連通分量。圖的結(jié)構(gòu)比較復(fù)雜，任意兩個(gè)頂點(diǎn)之間都可能存在聯(lián)系，因此無(wú)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系。前面已經(jīng)介紹過(guò)，圖這種數(shù)據(jù)結(jié)構(gòu)包括兩種信息，即各頂點(diǎn)本身的信息和邊的信息。所以，借助一個(gè)二維數(shù)組或多重鏈表可以很自然的表示圖。圖的存儲(chǔ)方法很多，常用的方法有鄰接矩陣、鄰接表、十字鏈表、多重鏈表等。這里僅介紹鄰接矩陣存儲(chǔ)方法和鄰接表存儲(chǔ)方法。7.2

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

鄰接矩陣在鄰接矩陣存儲(chǔ)方法中，圖中各個(gè)結(jié)點(diǎn)的數(shù)據(jù)信息存放在一個(gè)一維數(shù)組中，而圖中邊的信息，也即各頂點(diǎn)之間的關(guān)系用一個(gè)二維數(shù)組(又稱(chēng)為鄰接矩陣)來(lái)表示。設(shè)圖G有n個(gè)頂點(diǎn)，那么可取這個(gè)一維數(shù)組的長(zhǎng)度為n，鄰接矩陣的大小為n×n。圖的數(shù)據(jù)類(lèi)型可說(shuō)明如下：//圖的頂點(diǎn)數(shù)//圖的邊數(shù)//頂點(diǎn)的數(shù)據(jù)類(lèi)型//頂點(diǎn)權(quán)值的數(shù)據(jù)類(lèi)型//頂點(diǎn)數(shù)組//鄰接矩陣#define

n#define

etypedef

char

vextype;typedeffloat

adjtype;typedef

struct{

vextype

vexs[n];adjtype

arcs[n][n];}graph;矩陣中的元素arcs[i][j]表示頂點(diǎn)i與頂點(diǎn)j之間的關(guān)系，并按以下規(guī)則取值：(7-2)i

ji

j1,

若(vi

,v

j

)或<vi

,v

j

>?

E(G)arcs[i][j]=0,

若(v,v)或<v

,v>ˇ

E(G)0≤i,

j≤n-1對(duì)于無(wú)向圖的鄰接矩陣，其行或列中的非零元素個(gè)數(shù)等于對(duì)應(yīng)的頂點(diǎn)的度。由于無(wú)向圖的邊的特點(diǎn)，可知無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，因此在存儲(chǔ)時(shí)可以只保存矩陣的下三角或上三角的元素。在有向圖中，每行非零元素的個(gè)數(shù)對(duì)應(yīng)于該頂點(diǎn)的出度，而每列非零元素的個(gè)數(shù)則對(duì)應(yīng)于該頂點(diǎn)的入度。例如，圖7.6(a)和(b)的鄰接矩陣G1.arcs

和G2.arcs

分別為：1G

.arcs=

0

1

0

10

1

1

020

1

0

0

0

0

0

01

0

1 1

1

0

1 1

G

.arcs=

0

0

0

10

0

0

0

很容易把圖的鄰接矩陣推廣到網(wǎng)絡(luò)。網(wǎng)絡(luò)的鄰接矩陣元素R[i,j]可定義為R[i,j]=Wij

,

若(vi

,vj

)或<vi

,vj

>?

E(G)0或￥

,否則0≤i,

j≤n-1(7-3)例如，圖7.4

中網(wǎng)絡(luò)的鄰接矩陣可表示為0

0

0A[i,j]=

5

0

4

3

2

0圖7.6

無(wú)向圖G1和有向圖G2示例下面給出無(wú)向網(wǎng)絡(luò)鄰接矩陣建立的算法7.1。算法7.1void{

int無(wú)向網(wǎng)絡(luò)鄰接矩陣建立的算法。

CreateAdjArray(graph

*G)//建立無(wú)向網(wǎng)絡(luò)的鄰接矩陣

i,j,k;//讀入頂點(diǎn)信息，建立頂點(diǎn)表//鄰接矩陣初始化float

w;for(

i=0;

i<n;

i++

)G->vexs[i]=getchar(

);for(

i=0;

i<n;

i++

)for(j=0;

j<n;

j++)G->arcs[i][j]=0;for(

k=0;

k<e;

k++

){

scanf

(

"

%d%d%f

",

&i,

&j,

&w);G->arcs[i][j]=w;//讀入邊(vi,vj)上的權(quán)w//鄰接矩陣寫(xiě)入}G->arcs[j][i]=w;}//

CreateAdjArray對(duì)于無(wú)向圖，算法7.1中的G－>arcs[i][j]只取值0或1，那么修改變量w

的類(lèi)型并使輸入值為1

即可。對(duì)于有向圖或有向網(wǎng)絡(luò)，則需要去除鄰接矩陣寫(xiě)入的兩個(gè)語(yǔ)句中的后一個(gè)語(yǔ)句，并相應(yīng)修改變量w。算法7.1

的執(zhí)行時(shí)間是O(n+n2+e)。一般情況下，e<<n2，所以算法的時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(n2)。當(dāng)鄰接矩陣是一個(gè)稀疏矩陣時(shí)，顯然，存儲(chǔ)空間浪費(fèi)現(xiàn)象較嚴(yán)重。7.2.2

鄰接表鄰接表(Adjacency

List)是一種結(jié)合順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的

存儲(chǔ)方法。其中順序存儲(chǔ)部分稱(chēng)為頂點(diǎn)表，用于保存頂點(diǎn)信息；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)即鄰接鏈表，用于存儲(chǔ)圖中邊的信息。當(dāng)圖中的頂點(diǎn)很多而邊很少時(shí)，可以用鏈?zhǔn)浇Y(jié)構(gòu)取代稀疏的鄰接矩陣，從而節(jié)省存儲(chǔ)空間。頂點(diǎn)表是一個(gè)具有兩個(gè)域的結(jié)構(gòu)體數(shù)組，其中一個(gè)域稱(chēng)為頂點(diǎn)域(vertex)，用來(lái)存放頂點(diǎn)本身的數(shù)據(jù)信息；另一個(gè)域稱(chēng)為指針域(link)，用于指示依附于該頂點(diǎn)的邊所組成的單鏈表的表頭結(jié)點(diǎn)。頂點(diǎn)vi

的鄰接鏈表是由鄰接于vi

的所有頂點(diǎn)鏈接成的單鏈表。鄰接鏈表中的每個(gè)結(jié)點(diǎn)由鄰接點(diǎn)域和鏈域構(gòu)成。鄰接點(diǎn)域(adjvex)用于存放與vi

相鄰接的頂點(diǎn)vj

的序號(hào)j或者是頂點(diǎn)vj

在頂點(diǎn)表中所處單元的下標(biāo)；鏈域(next)用于指向鄰接鏈表中的下一結(jié)點(diǎn)。下面給出鄰接鏈表和頂點(diǎn)表中的結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型：typedeftypedefcharstructvextype;node{

intstructadjvex;node

*next;//定義頂點(diǎn)數(shù)據(jù)信息類(lèi)型//鄰接鏈表結(jié)點(diǎn)的結(jié)構(gòu)體類(lèi)型//鄰接點(diǎn)域//鏈域//

若要表示邊上的權(quán)，則應(yīng)增加一個(gè)權(quán)值域}

edgenode;typedef{

vextypestructvertex;//頂點(diǎn)表結(jié)點(diǎn)的結(jié)構(gòu)體類(lèi)型//頂點(diǎn)域//邊表頭指針域edgenode

*link;}

vexnode;vexnode

ga[n];//頂點(diǎn)表無(wú)向圖的鄰接鏈表又稱(chēng)為邊表。這是因?yàn)檫叡碇械拿總€(gè)結(jié)點(diǎn)都對(duì)應(yīng)于與頂點(diǎn)vi

相關(guān)聯(lián)的一條邊，而邊表的長(zhǎng)度就是頂點(diǎn)vi

的度。在有向圖中，vi

的鄰接鏈表中結(jié)點(diǎn)的個(gè)數(shù)則對(duì)應(yīng)于vi

的出度，因此有向圖的鄰接鏈表也稱(chēng)為出邊表，也可以建立一個(gè)有向圖的逆鄰接鏈表，即入邊表，vi

的入邊表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于以vi

為終點(diǎn)的一條邊。圖7.7

所示分別為圖7.6(a)的邊表(圖7.7(a))，以及圖7.6(b)的出邊表(圖7.7(b)和入邊表(圖7.7(c))，其中表示該域?yàn)榭铡D7.7

鄰接表和逆鄰接表示例無(wú)向圖鄰接表的建立如算法7.2

所示。算法7.2void{int無(wú)向網(wǎng)絡(luò)的鄰接表建立算法。CreateAdjList(vexnode G[

])

//建立無(wú)向圖的鄰接表i,

j,

k;//讀入頂點(diǎn)信息和邊表頭指針初始化//邊表頭指針初始化edgenode

*s;for(

i=0;

i<n;

i++){

G[i].

vertex=getchar(

);G[i].

link=NULL;}//建立邊表//讀入邊(vi,vj)的頂點(diǎn)序號(hào)//生成鄰接點(diǎn)序號(hào)為j

的邊表結(jié)點(diǎn)*s//將*s

插入頂點(diǎn)vi

的邊表頭部//生成鄰接點(diǎn)序號(hào)為i

的邊表結(jié)點(diǎn)*s//將*s

插入頂點(diǎn)vj

的邊表頭部}for(

k=0;

k<e;

k++){

scanf

("%d%d",

&i,

&j

);s=(edgenode*)malloc(

sizeof(edgenode));s－>adjvex=j;s－>next=G[i].

link;G[i].link=s;s=(edgenode*)malloc(sizeof

(edgenode));s－>adjvex=i;s－>next=G[j].

link;G[j].

link=s;}//

CreateAdjList對(duì)于有向圖鄰接表的建立，只需去除算法7.2中生成鄰接點(diǎn)序號(hào)為i的邊表結(jié)點(diǎn)*s，并將*s插入頂點(diǎn)vj邊表頭部的那一段語(yǔ)句組即可。如要建立網(wǎng)絡(luò)的鄰接表，則需在邊表的每個(gè)結(jié)點(diǎn)中增加一個(gè)數(shù)據(jù)域以存儲(chǔ)邊上的權(quán)值。算法7.2的時(shí)間復(fù)雜度是O(n+e)。鄰接矩陣和鄰接表都是最常用的圖的存儲(chǔ)結(jié)構(gòu)。在具體應(yīng)用中選取存儲(chǔ)方法時(shí)，應(yīng)主要考慮算法本身的特點(diǎn)和空間的存儲(chǔ)密度。下面具體分析和比較它們的優(yōu)缺點(diǎn)：(1)由于鄰接鏈表中結(jié)點(diǎn)的鏈接次序取決于鄰接表的建立算法和邊的輸入次序，因此圖的鄰接表表示是不唯一的；圖的鄰接矩陣表示則是唯一的。要判定(vi,vj)或<vi,vj>是否是圖中的一條邊，在鄰接矩陣表示中只需隨機(jī)讀取矩陣單元(i,j)的元素值是否為零即可；在鄰接表中，需要掃描vi

對(duì)應(yīng)的鄰接鏈表，在最壞情況下需要的掃描時(shí)間為O(n)。計(jì)算圖中邊的數(shù)目時(shí)，對(duì)于鄰接矩陣必須對(duì)整個(gè)矩陣進(jìn)行掃描后才能確定，其時(shí)間耗費(fèi)為O(n2)，與e

的大小無(wú)關(guān)；在鄰接表中只需統(tǒng)計(jì)每個(gè)邊表中的結(jié)點(diǎn)個(gè)數(shù)便可確定，時(shí)間耗費(fèi)僅為O(n+e)，當(dāng)e<<n2

時(shí)，節(jié)省的計(jì)算時(shí)間非?？捎^。圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)訪問(wèn)圖中的每一個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次。圖的遍歷算法是求解圖的連通性、

拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。圖的遍歷與樹(shù)的遍歷在思路上是類(lèi)似的，但是其過(guò)程要復(fù)雜得多。由于圖中的任一頂點(diǎn)都可能與其它頂點(diǎn)相鄰接，因此在訪問(wèn)某個(gè)頂點(diǎn)之后有可能沿著某條路徑又回到該頂點(diǎn)上。為了避免對(duì)同一頂點(diǎn)的重復(fù)訪問(wèn)，可以設(shè)置一個(gè)輔助數(shù)組

visited[n]，用于標(biāo)記訪問(wèn)過(guò)的頂點(diǎn)。數(shù)組visited[n]初值可設(shè)為

0。一旦頂點(diǎn)vi被訪問(wèn)，則設(shè)置visited[i]值為1。圖的遍歷路徑通常分為深度優(yōu)先搜索和廣度優(yōu)先搜索。本節(jié)以無(wú)向圖為例進(jìn)行討論，并且假定遍歷過(guò)程中訪問(wèn)頂點(diǎn)的操作只是簡(jiǎn)單的輸出頂點(diǎn)。這些方法也適用于有向圖的情況。7.3

圖的遍歷7.3.1

深度優(yōu)先搜索遍歷圖的深度優(yōu)先搜索(Depth-FirstSearch)遍歷類(lèi)似于樹(shù)的先序遍歷，是樹(shù)的先序遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)都未被訪問(wèn)，則深度優(yōu)先搜索方法的步驟是：選取圖中某一頂點(diǎn)vi

為出發(fā)點(diǎn)，訪問(wèn)并標(biāo)記該頂點(diǎn)。以vi

為當(dāng)前頂點(diǎn)，依次搜索vi

的每個(gè)鄰接點(diǎn)vj，若vj

已被訪問(wèn)過(guò)，則搜索vi

的下一個(gè)鄰接點(diǎn)，否則訪問(wèn)和標(biāo)記鄰接點(diǎn)vj。以vj

為當(dāng)前頂點(diǎn)，重復(fù)步驟(2)，直到圖中和vi

有路徑相通的頂點(diǎn)都被訪問(wèn)為止。(4)若圖中尚有頂點(diǎn)未被訪問(wèn)過(guò)(非連通的情況下)，則可任取圖中的一個(gè)未被訪問(wèn)的頂點(diǎn)作為出發(fā)點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)。與樹(shù)的深度優(yōu)先搜索類(lèi)似，這種方法在訪問(wèn)了頂點(diǎn)vi

以及vi

的一個(gè)鄰接點(diǎn)vj

之后，馬上又訪問(wèn)vj

的一個(gè)鄰接點(diǎn)，依次類(lèi)推，搜索朝著縱深方向進(jìn)行，所以稱(chēng)為深度優(yōu)先搜索遍歷。圖

7.8(a)給出了一個(gè)深度優(yōu)先搜索遍歷的示例，其中虛線表示搜索路線。相應(yīng)的頂點(diǎn)遍歷序列為A,B,C,D,E。圖7.8

圖的遍歷過(guò)程示例顯然，這種搜索方法具有遞歸的性質(zhì)。選擇鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，則圖的深度優(yōu)先搜索遍歷如算法7.3所示。算法7.3圖的深度優(yōu)先搜索遍歷DFSA。int

visited[n]; //visited

為全局變量，初值設(shè)為0，n

為頂點(diǎn)數(shù)graphG;//G

為全局變量，用鄰接矩陣表示void{

intDFSA(int

i)j;//從vi

出發(fā)深度優(yōu)先搜索圖Gprintf("node:%c\n",G.vexs[i]);

//訪問(wèn)出發(fā)點(diǎn)vivisited[i]=1;for(j=0;

j<n;j++)//標(biāo)記vi

已被訪問(wèn)//依次搜索vi

的鄰接點(diǎn)if((G.arcs[i][j]==1)&&(visited[j]==0))DFSA(j); //若鄰接點(diǎn)vj未被訪問(wèn)過(guò)，則從vj出發(fā)進(jìn)行深度優(yōu)先搜索遍歷} //

DFSA下面根據(jù)算法7.3詳細(xì)討論圖7.8(a)的深度優(yōu)先搜索遍歷過(guò)程。為保證DFS序列的唯一性，按順序?qū)㈨旤c(diǎn)A、B、C、D、E的數(shù)組下標(biāo)設(shè)置為0～4，并以頂點(diǎn)A為出發(fā)點(diǎn)。調(diào)用DFSA(0)，將visited[0]置為1，表示頂點(diǎn)A已被訪問(wèn)過(guò)。按順序首先選擇A的未被訪問(wèn)的鄰接點(diǎn)B，進(jìn)行深度優(yōu)先搜索遍歷；調(diào)用DFSA(1)訪問(wèn)頂點(diǎn)B，將visited[1]置為1。按順序

選擇B的第一個(gè)未被訪問(wèn)的鄰接點(diǎn)C，進(jìn)行深度優(yōu)先搜索遍歷。調(diào)用DFSA(2)訪問(wèn)頂點(diǎn)C，將visited[2]置為1。由于頂點(diǎn)C的所有鄰接點(diǎn)均已被標(biāo)記即訪問(wèn)過(guò)，因而結(jié)束DFSA(2)的調(diào)用并退回到上一層調(diào)用即DFSA(1)中。按順序選擇頂點(diǎn)B的下一個(gè)未被訪問(wèn)的鄰接點(diǎn)D，接著從D出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。調(diào)用DFSA(3)訪問(wèn)頂點(diǎn)D，將visited[3]置為1；此時(shí)頂點(diǎn)D的未被訪問(wèn)過(guò)的頂點(diǎn)只有E，因此以頂點(diǎn)E為出發(fā)點(diǎn)進(jìn)行深度優(yōu)先搜索遍歷。(5)調(diào)用DFSA(4)訪問(wèn)頂點(diǎn)E，將visited[4]置為1；此時(shí)所有頂點(diǎn)均已被訪問(wèn)過(guò)，這表明圖中與頂點(diǎn)A相通的頂點(diǎn)都已被訪問(wèn)。因而開(kāi)始出棧，首先退回到上一層調(diào)用即DFSA(3)中，然后是DFSA(1)，最后是DFSA(0)，遍歷過(guò)程結(jié)束。所得到的

DFS序列為A、B、C、D、E。在算法7.3中，每個(gè)頂點(diǎn)vi僅被標(biāo)記一次，因此至多調(diào)用函數(shù)DFSA(i)一次，每次調(diào)用中for循環(huán)要運(yùn)行n次，所以算法的時(shí)間復(fù)雜度為O(n2)。由于是遞歸調(diào)用，需要使用長(zhǎng)度為n的輔助數(shù)組以及一個(gè)長(zhǎng)度為n–1的工作棧，因此算法的空間復(fù)雜度為O(n)。按照深度優(yōu)先搜索遍歷順序所得到的頂點(diǎn)序列稱(chēng)為該圖的深度優(yōu)先搜索遍歷序列，簡(jiǎn)稱(chēng)為DFS序列。DFS序列取決于算法、圖的存儲(chǔ)結(jié)構(gòu)和初始出發(fā)點(diǎn)，因此一個(gè)圖的DFS序列并不唯一。以鄰接表為存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先搜索遍歷如算法7.4所示?？梢?jiàn)，只需將算法7.3中對(duì)vi的鄰接點(diǎn)修改為對(duì)鄰接表的操作即可。同樣，由于圖的鄰接表表示不唯一，因而以鄰接表為存儲(chǔ)結(jié)構(gòu)的DFS序列也不唯一。DFSL算法需要對(duì)n個(gè)頂點(diǎn)的所有邊表結(jié)點(diǎn)掃描一遍，而邊表結(jié)點(diǎn)的數(shù)目為2e，所以算法的時(shí)間復(fù)雜度為O(n+2e)，空間復(fù)雜度為O(n)。算法7.4圖的深度優(yōu)先搜索遍歷DFSL。DFSL(int

i)

//圖Ga

用鄰接表表示，以vi

為出發(fā)點(diǎn)void{

edgenode

*p;printf("node:%c\n",

Ga[i].

vertex);visited[i]=1;//訪問(wèn)頂點(diǎn)vi//標(biāo)記vi已被訪問(wèn)//依次搜索vi

的鄰接點(diǎn)for(p=Ga[i].link;

p!=NULL;

p=p－>next;)if(visited[p－>adjvex]==0)DFSL(p－>adjvex);}//選擇未被訪問(wèn)的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷//

DFSL7.3.2

廣度優(yōu)先搜索遍歷圖的廣度優(yōu)先搜索(Breadth-first

Search)遍歷類(lèi)似于樹(shù)的按層次遍歷。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)都未被訪問(wèn)，這種方法的思路是：從圖中某一頂點(diǎn)vi

出發(fā)，先訪問(wèn)vi，然后訪問(wèn)vi

的所有鄰接點(diǎn)vj。當(dāng)所有的vj

都被訪問(wèn)之后，再訪問(wèn)vj

的鄰接點(diǎn)vk，依此類(lèi)推，直到圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)過(guò)。此時(shí)，與初始出發(fā)點(diǎn)vi

有路徑相通的頂點(diǎn)都將被訪問(wèn)。若圖是非連通的，則另選擇一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為出發(fā)點(diǎn)，重復(fù)以上過(guò)程，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。這種遍歷方法的特點(diǎn)是，“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”也

先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”，因此具有先進(jìn)先出的特性。所以，可以使用一個(gè)隊(duì)列來(lái)保存已訪問(wèn)過(guò)的頂點(diǎn)，以確定對(duì)訪

問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)的訪問(wèn)次序。這里仍需使用一個(gè)輔助數(shù)組

visited[n]來(lái)標(biāo)記頂點(diǎn)的訪問(wèn)情況，以避免對(duì)某一個(gè)頂點(diǎn)的重復(fù)

訪問(wèn)。下面分別給出以鄰接矩陣和鄰接表為存儲(chǔ)結(jié)構(gòu)時(shí)的廣度優(yōu)先搜索遍歷算法BFSA和BFSL，分別如算法7.5和算法7.6所示。算法7.5圖的廣度優(yōu)先搜索遍歷BFSA。void{intBFSA(int

k)

//圖G

用鄰接矩陣表示，以vk

為出發(fā)點(diǎn)i,

j;SETNULL(Q);printf("%c\n",

G.vexs[k]);visited[k]=1;ENQUEUE(Q,

k);while(

!EMPTY(Q)

)//Q

置為空隊(duì)//訪問(wèn)出發(fā)點(diǎn)vk//標(biāo)記vk

已被訪問(wèn)//訪問(wèn)過(guò)的頂點(diǎn)序號(hào)入隊(duì)//隊(duì)列非空時(shí)執(zhí)行下列操作//隊(duì)頭頂點(diǎn)序號(hào)出隊(duì){

i=DEQUEUE(Q);for(

j=0;

j<n;

j++)if

(

(

g.arcs[i][j]=

=1)&&(

visited[j]!=1

)

)//訪問(wèn)與vi

鄰接的未曾被訪問(wèn)的頂點(diǎn)vj//置頂點(diǎn)vj

的標(biāo)志為1//訪問(wèn)過(guò)的頂點(diǎn)序號(hào)入隊(duì){

printf("%c\n",

G.vexs[j]);visited[j]=1;ENQUEUE(Q,

j);}}}//

BFSA算法

7.6

圖的廣度優(yōu)先搜索遍歷

BFSL。void

BFSL(int

k) //圖G

用鄰接表表示，以vk

為出發(fā)點(diǎn){int

i;edgenode

*p;SETNULL(Q);printf("%c\n",

Ga[k].vertex);visited[k]=1;ENQUEUE(Q,

k);//置空隊(duì)//訪問(wèn)出發(fā)點(diǎn)vk//標(biāo)記vk

已被訪問(wèn)//頂點(diǎn)vk

序號(hào)入隊(duì)while(

!EMPTY(Q)

){i=DEQUEUE(Q);

//隊(duì)頭頂點(diǎn)序號(hào)出隊(duì)for(p=Ga[i].link;p!=NULL;p=p－>next)//取vi

的邊表頭指針，依次搜索vi

的鄰接點(diǎn)if

(visited[p－>adjvex]==0) //vi的鄰接點(diǎn)未曾被訪問(wèn){printf("%c\n",Ga[p－>adjvex].vertex);visited[p->adjvex]=1;ENQUEUE(Q,

p－>adjvex);//置頂點(diǎn)的訪問(wèn)標(biāo)志為1//訪問(wèn)過(guò)的頂點(diǎn)序號(hào)入隊(duì)}}}

//

BFSL圖7.8(b)給出了以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)時(shí)的圖廣度優(yōu)先搜索遍歷示例。按圖的廣度優(yōu)先搜索遍歷順序得到的頂點(diǎn)序列稱(chēng)為該圖的廣度優(yōu)先搜索遍歷序列，簡(jiǎn)稱(chēng)為BFS序列。一個(gè)圖的

BFS序列也不是唯一的，它取決于算法、圖的存儲(chǔ)結(jié)構(gòu)和初始出發(fā)點(diǎn)。以鄰接表作為存儲(chǔ)結(jié)構(gòu)得到的BFS序列還與鄰接表中邊表結(jié)點(diǎn)的鏈接次序有關(guān)。下面僅以鄰接矩陣為例，討論圖7.8(b)的廣度優(yōu)先搜索遍歷過(guò)程。假設(shè)頂點(diǎn)A、B、C、D、E分別對(duì)應(yīng)數(shù)組visited的下標(biāo)0～4，從頂點(diǎn)A出發(fā)的BFSA算法過(guò)程如下：(1)調(diào)用BFSA(0)，頂點(diǎn)A首先被訪問(wèn)；將visited[0]置1，并將頂點(diǎn)A的序號(hào)0入隊(duì)；然后，當(dāng)隊(duì)列不為空時(shí)執(zhí)行出隊(duì)操作，得到頂點(diǎn)序號(hào)0，通過(guò)搜索頂點(diǎn)A的鄰接點(diǎn)得到未被訪問(wèn)的頂點(diǎn)是B和E，所訪問(wèn)的第二、三個(gè)頂點(diǎn)是B和E，將

visited[1]、visited[4]置1，并將其對(duì)應(yīng)的序號(hào)1、4入隊(duì)。此時(shí)出隊(duì)的頂點(diǎn)序號(hào)是1，搜索到B的三個(gè)鄰接點(diǎn)A、C、D中有頂點(diǎn)C、D未被訪問(wèn)，因此C和D分別是第四、五個(gè)被訪

問(wèn)的頂點(diǎn)，置訪問(wèn)標(biāo)志為1，并將其序號(hào)2、3入隊(duì)。此時(shí)出隊(duì)的頂點(diǎn)序號(hào)是4，對(duì)應(yīng)頂點(diǎn)E的兩個(gè)鄰接點(diǎn)A和D已訪問(wèn)過(guò)，故不執(zhí)行入隊(duì)操作。接著出隊(duì)的頂點(diǎn)序號(hào)是2，搜索到C的一個(gè)鄰接點(diǎn)B已訪問(wèn)過(guò)，故無(wú)頂點(diǎn)序號(hào)入隊(duì)。(5)

最后出隊(duì)的頂點(diǎn)序號(hào)是3，搜索可知，D的兩個(gè)鄰接點(diǎn)

B和E都已訪問(wèn)過(guò)，故無(wú)頂點(diǎn)序號(hào)入隊(duì)。此時(shí)隊(duì)列已為空，搜

索過(guò)程結(jié)束。根據(jù)訪問(wèn)的順序得到的BFS序列是A、B、E、C、D。分析可知，對(duì)于有n個(gè)頂點(diǎn)和e條邊的連通圖，BFSA算法的while循環(huán)和for循環(huán)都需執(zhí)行n次，所以BFSA算法的時(shí)間復(fù)雜度為O(n2)；BFSL算法的while循環(huán)要執(zhí)行n次，而for循環(huán)的執(zhí)行次數(shù)等于邊表結(jié)點(diǎn)的總個(gè)數(shù)2e，因此BFSL算法的時(shí)間復(fù)雜度為O(n+2e)。BFSA算法和BFSL算法都使用了一個(gè)長(zhǎng)度均為n的隊(duì)列和輔助標(biāo)志數(shù)組，因此空間復(fù)雜度都為O(n)。7.4.1

基本概念我們知道，利用圖的遍歷算法可以求解圖的連通性問(wèn)題。例如對(duì)無(wú)向連通圖G進(jìn)行遍歷，可以選擇G的任意頂點(diǎn)作為出發(fā)點(diǎn)，進(jìn)行一次深度優(yōu)先搜索或廣度優(yōu)先搜索就可以訪問(wèn)到G中的所有頂點(diǎn)。如果對(duì)無(wú)向非連通圖進(jìn)行遍歷，則需要對(duì)其每一個(gè)連通分量分別選擇某個(gè)頂點(diǎn)作為出發(fā)點(diǎn)進(jìn)行遍歷。7.4

生成樹(shù)和最小生成樹(shù)現(xiàn)在引入生成樹(shù)的概念。以無(wú)向連通圖G為例，把遍歷過(guò)程中順序訪問(wèn)的兩個(gè)頂點(diǎn)之間的路徑記錄下來(lái)，這樣G中的n個(gè)頂點(diǎn)以及由出發(fā)點(diǎn)依次訪問(wèn)其余n-1個(gè)頂點(diǎn)所經(jīng)過(guò)的n-1條邊就構(gòu)成了G的極小連通子圖，也就是G的一棵生成樹(shù)，出發(fā)頂點(diǎn)是生成樹(shù)的根。所謂極小，是指該子圖具有連通所需的最小邊數(shù)，若去掉一條邊，該子圖就變成了非連通圖；若任意增加一條邊，該子圖就有回路產(chǎn)生。通常，我們將深度優(yōu)先搜索得到的生成樹(shù)稱(chēng)為深度優(yōu)先搜索生成樹(shù)，簡(jiǎn)稱(chēng)為DFS生成樹(shù)，而將廣度優(yōu)先搜索得到的生成樹(shù)稱(chēng)為廣度優(yōu)先搜索生成樹(shù)，簡(jiǎn)稱(chēng)為BFS生成樹(shù)。圖7.9給出了對(duì)圖7.8進(jìn)行遍歷產(chǎn)生生成樹(shù)的示例。圖7.9

圖的生成樹(shù)示例在圖論中，樹(shù)可以看做是一個(gè)無(wú)回路存在的連通圖。連通圖G的生成樹(shù)就可以定義為一個(gè)包含了G的所有頂點(diǎn)的樹(shù)。由樹(shù)的性質(zhì)也可知，一個(gè)連通圖G具有n個(gè)頂點(diǎn)，其生成樹(shù)最多有n-1條邊。該生成樹(shù)也是G的一個(gè)極小連通子圖。顯然，連通圖的生成樹(shù)并不唯一，這取決于選擇的遍歷方法和出發(fā)頂點(diǎn)。對(duì)于非連通圖，遍歷其每個(gè)連通分量則可生成對(duì)應(yīng)的生成樹(shù)，這些生成樹(shù)構(gòu)成了非連通圖的生成森林。下面給出最小生成樹(shù)(Minimum

Spanning

Tree)的概念。給定一個(gè)連通網(wǎng)絡(luò)，要求構(gòu)造具有最小代價(jià)的生成樹(shù)時(shí)，也即使生成樹(shù)各邊的權(quán)值總和達(dá)到最小。把生成樹(shù)各邊的權(quán)值總和定義為生成樹(shù)的權(quán)，那么具有最小權(quán)值的生成樹(shù)就構(gòu)成了連通網(wǎng)絡(luò)的最小生成樹(shù)，最小生成樹(shù)可簡(jiǎn)記為MST。最小生成樹(shù)的構(gòu)造具有重要的實(shí)際應(yīng)用價(jià)值。例如，要在

n個(gè)城市之間建立通信網(wǎng)絡(luò)，而在不同城市之間建立通信線路時(shí)需要一定的花費(fèi)，可以作為網(wǎng)絡(luò)邊的權(quán)值。使用最少的經(jīng)費(fèi)來(lái)建立相應(yīng)的通信網(wǎng)絡(luò)，這一問(wèn)題就轉(zhuǎn)化為構(gòu)造最小生成樹(shù)的問(wèn)題。構(gòu)造最小生成樹(shù)，也就是在給定n個(gè)頂點(diǎn)所對(duì)應(yīng)的權(quán)矩陣(代價(jià)矩陣)的條件下，給出代價(jià)最小的生成樹(shù)。構(gòu)造最小生成樹(shù)的算法有多種，其中大多數(shù)算法都利用了最小生成樹(shù)的一個(gè)性質(zhì)，簡(jiǎn)稱(chēng)MST性質(zhì)：假設(shè)G=(V,E)是一個(gè)連通網(wǎng)絡(luò)，U是V中的一個(gè)真子集，若存在頂點(diǎn)u?

U和頂點(diǎn)v?V-U的邊(u,v)是一條具有最小權(quán)值的邊，則必存在G的一棵最小生成樹(shù)包括這條邊(u,

v)。MST性質(zhì)可用反證法加以證明：假設(shè)網(wǎng)絡(luò)G中的任何一棵最小生成樹(shù)T都不包含(u,v)，其中u?U

和v?

V–U。在最小生成樹(shù)T中，必然存在一條邊(u′,v′)(其中u′?U

和v′?

V-U)連接兩個(gè)頂點(diǎn)集U和V-U。當(dāng)(u,

v)加入到T中時(shí)，T中必然存在一條包含了(u,

v)的回路。如果刪除

(u′,v′)并保留(u,

v),

則得到另一棵生成樹(shù)T′。因(u,

v)的權(quán)小于

(u′,v′)的權(quán)，故T′的權(quán)小于T的權(quán)，這與假設(shè)矛盾。下面介紹利用MTS性質(zhì)構(gòu)造最小生成樹(shù)的兩種常用算法：Prim(普里姆)算法和Kruskal(克魯斯卡爾)算法。7.4.2 Prim

算法假設(shè)G(V,E)是有n

個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)，用T=(U,TE)表示要構(gòu)造的最小生成樹(shù)，其中U

為頂點(diǎn)集合，TE

為邊的集合。Prim算法的具體步驟描述如下：初始化：令U={}，TE={}。從V

中取出一個(gè)頂點(diǎn)u0

放入生成樹(shù)的頂點(diǎn)集U

中，作為第一個(gè)頂點(diǎn)，此時(shí)T=({u0},{

})；從

u?U，v?

V–U

的邊(u,

v)中找一條代價(jià)最小的邊(u*,v*)，將其放入

TE

中，并將

v*放入

U

中。(3)重復(fù)步驟(2)，直至U=V為止。此時(shí)集合TE中必有n–1條邊，T即為所要構(gòu)造的最小生成樹(shù)。Prim算法的關(guān)鍵是第(2)步，即如何找到連接U和V–U的最短邊(代價(jià)最小邊)。假設(shè)生成樹(shù)T中已有k個(gè)頂點(diǎn)，則U和V-U中可能存在的邊數(shù)最多為k(n-k)條。簡(jiǎn)單的窮搜索法會(huì)具有較大的復(fù)雜度。分析可以發(fā)現(xiàn)，在尋找最小代價(jià)邊的過(guò)程中，有些操作具有重復(fù)性。我們可以將前一次尋找所得到的最小代價(jià)邊存儲(chǔ)起來(lái)，然后與新找到的邊進(jìn)行比較，如果新找到的邊比原來(lái)已找到的邊短，則用新找到的邊代替原有的邊，否則保持不變。為此設(shè)立以下的邊的存儲(chǔ)結(jié)構(gòu)：typedef

struct{

intfromvex,

endvex;float

length;//邊的起點(diǎn)和終點(diǎn)//邊的權(quán)值}

edge;edge

T[n-1];float

dist[n][n];//最小生成樹(shù)//連通網(wǎng)絡(luò)的帶權(quán)鄰接矩陣以圖7.10

為例，Prim

算法的工作過(guò)程以及數(shù)組T

的變化如圖7.11

所示。初始狀態(tài)設(shè)為U={0}，TE={}，相應(yīng)的T

數(shù)組如圖7.11(a)所示。Prim

算法的實(shí)質(zhì)就是尋找最小生成樹(shù)的n-1

條邊。首先找到最小代價(jià)邊(0,2)，將其與第0

條邊交換并更新T

數(shù)組，表示加入新頂點(diǎn)2；之后需要更新U

和V-U

之間的最小代價(jià)邊，得到圖7.11(b)；對(duì)圖7.11(b)進(jìn)行搜索可以得到最小代價(jià)邊

(2,4)，將其與第1

條邊交換并更新T

數(shù)組，得到圖7.11(c)。依次操作，即可得到其余的3

條邊(2,1),(4,3)和(3,5)。上述過(guò)程的具體細(xì)節(jié)如算法7.7

所示。圖7.10

一個(gè)網(wǎng)絡(luò)示例算法

7.7

最小生成樹(shù)的

Prim

算法。void Prim

(int

i) //i

表示最小生成樹(shù)所選取的第一個(gè)頂點(diǎn)下標(biāo){

int

j,

k,

m,

v,

min,max=100000;float

d;edge

e;v=i; //將選定頂點(diǎn)送入中間變量

vfor(

j=0;

j<=n－2;

j++) //構(gòu)造第一個(gè)頂點(diǎn){

T[j].fromvex=v;if(j>=v) {T[j].endvex=j+1;

T[j].length=dist[v][j+1];

}else

{T[j].endvex=j; T[j].length=dist[v][j];

}}//求第k

條邊f(xié)or(

k=0;

k<n－1;

k++){

min=max;for(j=k;

j<n－1;

j++)//找出最短的邊并將最短邊的下標(biāo)記錄在m

中if

(T[j].length<min

)

{

min=T[j].length;

m=j;

}//將最短的邊交換到T[k]單元//v

中存放新找到的最短邊在V－U

中的頂點(diǎn)//修改所存儲(chǔ)的最小邊集e=T[m];

T[m]=T[k];

T[k]=e;v=T[k].endvex;for(

j=k+1;

j<n－1;

j++){

d=dist[v][T[j].endvex];if(d<T[j].length)

{

T[j].length=d;

T[j].fromvex=v;

}}} //

Prim圖7.11

Prim算法的工作過(guò)程算法

7.7

中構(gòu)造第一個(gè)頂點(diǎn)所需的時(shí)間是

O(n)，求

k條邊的時(shí)間大約為n-2

n-2k=0

j=kn-2

n-2k=0

j=kn-2j=k

+1O(1)

+

O(1)

?

2O(1)其中O(1)表示某一正常數(shù)C，所以上述公式的時(shí)間復(fù)雜度是O(n2)?？梢?jiàn)，Prim

算法的復(fù)雜度與網(wǎng)的邊數(shù)無(wú)關(guān)，適合邊稠密網(wǎng)絡(luò)的最小生成樹(shù)。7.4.3 Kruskal

算法Kruskal

算法是從另一途徑來(lái)求網(wǎng)絡(luò)的最小生成樹(shù)。設(shè)

G=(V,E)是一個(gè)有n

個(gè)頂點(diǎn)的連通圖，則令最小生成樹(shù)的初始狀態(tài)為只有n

個(gè)頂點(diǎn)而無(wú)任何邊的非連通圖T=(V,{})，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。依次選擇E

中的最小代價(jià)邊，若該邊依附于T

中兩個(gè)不同的連通分量，則將此邊加入TE

中；否則，舍去此邊而選擇下一條代價(jià)最小的邊。依此類(lèi)推，直到

T

中所有頂點(diǎn)都在同一連通分量上為止。這時(shí)的T

就是G

的一棵最小生成樹(shù)。利用Kruskal

算法對(duì)圖7.10

所示的網(wǎng)絡(luò)構(gòu)造最小生成樹(shù)的過(guò)程如圖7.12

所示。在圖7.12(c)中，依次選擇的前3條邊分別是(2,

4)、(0,

2)和

(1,2)。注意到，第4條最小代價(jià)邊選擇的是(3,4)，而不是(1,4)。這是因?yàn)?1,

4)的頂點(diǎn)在同一個(gè)分量上，故舍去這條邊而選擇下一條代價(jià)最小的邊。第5條最小代價(jià)邊選擇的是(3,

5)。圖7.12

Kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程在Kruskal

算法中，每次選擇最小代價(jià)邊時(shí)都需要掃描所有邊中的最短邊。若用鄰接矩陣實(shí)現(xiàn)，則需要掃描整個(gè)鄰接矩陣，致使算法復(fù)雜度太高；而使用鄰接表時(shí)，由于每條邊都被連接兩次，從而使得尋找最短邊的計(jì)算時(shí)間加倍。所以，我們采用以下的存儲(chǔ)結(jié)構(gòu)來(lái)對(duì)圖中的邊進(jìn)行表示：typedef

struct//邊的起點(diǎn)和終點(diǎn)//邊的權(quán)值//該邊是否已選擇過(guò)的標(biāo)志信息{

int

fromvex,

endvex;float

length;int

sign;}

edge;edge

T[e]; //e為圖中的邊數(shù)int

G[n];//判斷該邊的兩個(gè)頂點(diǎn)是不是在同一個(gè)分量上的數(shù)組，n

為頂點(diǎn)數(shù)這里數(shù)組G

存放頂點(diǎn)的連通信息，用于判斷所選擇的邊所對(duì)應(yīng)的兩個(gè)頂點(diǎn)是否在同一個(gè)分量上，具體描述如算法7.8

所示。算法7.8void最小生成樹(shù)的Kruskal

算法。Kruskal(int

n,

int

e)//n

表示圖中的頂點(diǎn)數(shù)目，e

表示圖中的邊數(shù)目{

int

i,

j,k,

l,

min

;

tfor

(

i=0;

i<=n－1;

i++)

G[i]=i;for

(

i=0;

i<=e－1;

i++)//數(shù)組G

置初值//輸入邊信息{

scanf

("

%d%d%f

",

&T[i].

fromvex，&T[i].endvex,

&T[i].

length);T[i].sign=0;}//尋找最短邊j=0;while(j<n－1){

min=1000;for

(

i=0;

i<=e－1;

i++)if(

T[i].sign=

=0)if(

T[i].length<min

){k=T[i].fromvex;l=T[i].endvex;T[i].sigh=1;}

if(G[k]==G[l])

T[i].sign=2;

//在同一分量上舍去

else{j++;for(t=0;t<n;t++)

//將最短邊的兩個(gè)頂點(diǎn)并入同一分量if(G[t]==G[l])G[t]=G[k];}}} //

Kruskal一般情況下，Kruskal算法的時(shí)間復(fù)雜度約為O(elge)，僅與網(wǎng)中的邊數(shù)有關(guān)，因此適合于邊稀疏網(wǎng)絡(luò)的最小生成樹(shù)，這一點(diǎn)與Prim算法相反。實(shí)際上，我們還可以在Kruskal算法之前先對(duì)邊進(jìn)行排序，這樣Kruskal算法的復(fù)雜度可降為O(e)。在計(jì)算機(jī)中可以用圖的結(jié)構(gòu)來(lái)表示一個(gè)實(shí)際的交通網(wǎng)絡(luò)，其中頂點(diǎn)作為城市，邊可以作為城市之間的交通聯(lián)系。由于城市之間的交通存在多條路徑且往往具有方向性，因此有向網(wǎng)絡(luò)結(jié)構(gòu)是較好的選擇，而在無(wú)向網(wǎng)絡(luò)中的情況與此類(lèi)似。在交通網(wǎng)絡(luò)中，最常見(jiàn)的問(wèn)題有兩個(gè)：一是從城市A是否可以到達(dá)城市B；二是如何選擇最小代價(jià)的路線。這里最小代價(jià)是指花費(fèi)最小、時(shí)間上最快，或者是二者的綜合考慮。這兩個(gè)問(wèn)題可以歸結(jié)為圖論中的最短路徑問(wèn)題。路徑上的第一個(gè)頂點(diǎn)稱(chēng)為源點(diǎn)(Source)，最后一個(gè)頂點(diǎn)稱(chēng)為終點(diǎn)(Destination)，路徑長(zhǎng)度則是指路徑上各條邊的權(quán)值之和。下面討論兩種最常見(jiàn)的最短路徑問(wèn)題。7.5

最短路徑7.5.1

從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑單源點(diǎn)的最短路徑問(wèn)題可以描述為：對(duì)于給定的有向網(wǎng)絡(luò)G=(V,E)及源點(diǎn)v，求從v到G中其它各頂點(diǎn)的最短路徑，假設(shè)各邊上的權(quán)值大于或等于0。單源點(diǎn)的最短路徑問(wèn)題可以用迪杰斯特拉(Dijkstra)提出的最短路徑算法來(lái)解決。迪杰斯特拉最短路徑算法的思路源自迪杰斯特拉對(duì)大量的

單源點(diǎn)最短路徑的頂點(diǎn)構(gòu)成集合和路徑長(zhǎng)度之間關(guān)系的研究：

若按長(zhǎng)度遞增的次序來(lái)產(chǎn)生源點(diǎn)到其余頂點(diǎn)的最短路徑，則當(dāng)

前正要生成的最短路徑除終點(diǎn)外，其余頂點(diǎn)的最短路徑已生成。換句話說(shuō)，假設(shè)A為源點(diǎn)，U為已求得的最短路徑的終點(diǎn)的集合(初態(tài)時(shí)為空集)，則下一條最短路徑(設(shè)其終點(diǎn)為X)或者是弧(A,X)，或者是中間只經(jīng)過(guò)U集合中的頂點(diǎn)，最后到達(dá)X的路徑。這條最短路徑上不可能存在U集合之外的頂點(diǎn)，讀者可以用反證法加以證明。為驗(yàn)證以上觀點(diǎn)，圖7.13所示為有向網(wǎng)絡(luò)G以及以頂點(diǎn)A為源點(diǎn)的最短路徑集合?？梢园l(fā)現(xiàn)，在查找終點(diǎn)為E、D、F的最短路徑時(shí)，其中間頂點(diǎn)均是已求得的最短路徑終點(diǎn)的集合。圖7.13

有向網(wǎng)絡(luò)G以及源點(diǎn)為A的最短路徑根據(jù)以上思路，可以按路徑長(zhǎng)度遞增次序來(lái)產(chǎn)生源點(diǎn)到各頂點(diǎn)的最短路徑。對(duì)有向連通網(wǎng)絡(luò)G=(V,E)，假設(shè)頂點(diǎn)個(gè)數(shù)為n，以u(píng)0作為源點(diǎn)，算法步驟描述如下：從V

中取出源點(diǎn)u0

放入最短路徑頂點(diǎn)集合U

中，此時(shí)最短路徑網(wǎng)絡(luò)S=({u0},{})；從

u?U

和

v?V

-U

中找到一條最小代價(jià)邊(u*, v*)，將其加入到S

中去，更新S=({u0,v*},

{(u0,v*)})。每往U

中增加一個(gè)頂點(diǎn)，就要對(duì)V-U

中各頂點(diǎn)的權(quán)值進(jìn)行一次修正：若加進(jìn)v*作為中間頂點(diǎn)，使得從u0

到其他屬于V-U的頂點(diǎn)vi

的路徑不加v*時(shí)最短，則修改u0

到vi

的權(quán)值，即以(u0,v*)的權(quán)值加上(v*,

vi

)的權(quán)值來(lái)代替原(u0,vi

)的權(quán)值，否則不修改u0到vi

的權(quán)值。(4)從權(quán)值修正后的V-U中選擇最短的邊加入S中，如此反復(fù)，直到U=V為止。算法7.9所示為用C語(yǔ)言描述的Dijkstra算法。其中有向網(wǎng)絡(luò)用鄰接矩陣dist[n][n]表示；數(shù)組D[n]用于保存源點(diǎn)到其他頂點(diǎn)的最短距離；數(shù)組p[i]用于記錄最短路徑中頂點(diǎn)i的前趨頂點(diǎn)；數(shù)組s[n]用于標(biāo)識(shí)最短路徑的生成情況，s[i]=1表示源點(diǎn)到頂點(diǎn)i的最短路徑已產(chǎn)生，而s[i]=0表示最短路徑還未產(chǎn)生。算法

7.9

Dijkstra

最短路徑算法。float

D[n];int p[n],

s[n];void Dijkstra(int

v,

float

dist[][])//求源點(diǎn)v

到其余頂點(diǎn)的最短路徑及長(zhǎng)度//max

中的值用以表示dist

矩陣中的值￥{ int

i,

j,

k,

v1,

min,

max=10000,

pre;v1=v;for(

i=0;

i<n;

i++)//各數(shù)組進(jìn)行初始化p[i]=

v1+1;{

D[i]=dist[v1][i];if(

D[i]

!=

max

)else

p[i]=0;s[i]=0;}

//endfors[v1]=1;for(

i=0;

i<n-1;

i++)//將源點(diǎn)送U//求源點(diǎn)到其余頂點(diǎn)的最短距離//min>max,

以保證值為￥

的頂點(diǎn)也能加入U(xiǎn){

min=10001;for(

j=0;

j<n-1;

j++)if((!s[j])&&(D[j]<min))//找出到源點(diǎn)具有最短距離的邊{

min=D[j];

k=j;}s[k]=1; //將找到的頂點(diǎn)k

送入U(xiǎn)for(j=0;j<n;

j++)if

(

(!s[j])&&(D[j]>D[k]+dist[k][j])

)//調(diào)整V-U

中各頂點(diǎn)的距離值//k

是j

的前趨{

D[j]=D[k]+dist[k][j];

p[j]=k+1;}}//所有頂點(diǎn)已擴(kuò)充到U

中for(

i=0;

i<n;i++){ printf("

%f

%d

",

D[i],

i)pre=p[i];while

((pre!=0)&&(pre!=v+1)){ printf

("<-%d",pre-1);

pre=p[pre-1];}printf("

<-%d

",

v);}

//endfor} //

Dijkstra對(duì)圖7.13中的有向網(wǎng)絡(luò)G執(zhí)行Dijkstra算法，以A點(diǎn)為源點(diǎn)時(shí)的數(shù)組D[n]、p[n]和s[n]的更新?tīng)顩r如表7.1

所示。表7.1Dijkstra

算法動(dòng)態(tài)執(zhí)行情況循環(huán)UkD[0]~

[5]p[0]

~[5]s[0]~[5]初始化{A}—034Inf12Inf1

1

1

0

1

01

0

0

0

0

01{A,B}1034inf8Inf1

1

1

0

2

01

1

0

0

0

02{A,B,C}2034108Inf1

1

1

3

2

01

1

1

0

0

03{A,B,C,E}4034108281

1

1

3

2

51

1

1

0

1

04{A,B,C,E,D}3034108281

1

1

3

2

51

1

1

1

1

05{A,B,C,E,D,F}5034108281

1

1

3

2

51

1

1

1

1

1相應(yīng)的打印輸出結(jié)果為00?031?042?0103?2?084?1?0285?4?1?0容易分析Dijkstra

算法的時(shí)間復(fù)雜度為O(n2)，占用的輔助空間是O(n)。人們可能只希望找到源點(diǎn)到某個(gè)頂點(diǎn)的最短路徑，但這個(gè)問(wèn)題的時(shí)間復(fù)雜度也是O(n2)。7.5.2

每對(duì)頂點(diǎn)之間的最短路徑為求解這一問(wèn)題，可以把有向網(wǎng)絡(luò)的每個(gè)頂點(diǎn)依次作為源點(diǎn)并執(zhí)行Dijkstra

算法，從而求得每一對(duì)頂點(diǎn)之間的最短路徑。在這種方法中，Dijkstra

算法需要重復(fù)執(zhí)行n

次，因此總的時(shí)間復(fù)雜度為O(n3)。弗洛伊德(Floyd)于

1962

年提出了解決這一問(wèn)題的另一種算法。該算法的時(shí)間復(fù)雜度也是

O(n3)，但形式比較簡(jiǎn)單，易于理解。本節(jié)主要介紹這種算法。Floyd

算法是根據(jù)有向網(wǎng)絡(luò)的鄰接矩陣

dist[n][n]來(lái)求頂點(diǎn)vi

到頂點(diǎn)

vj

的最短路徑，其基本思路是：假設(shè)

vi

和

vj

之間存在一條路徑，但這并不一定是最短路徑，尚需進(jìn)行

n次試探。首先嘗試在

vi

和

vj

之間增加一個(gè)中間頂點(diǎn)

v0。若增加

v0

后的路徑(vi,

v0,

vj)

比(vi,vj)短，則以新的路徑代替原路徑，并且修改

dist[i][j]的值為新路徑的權(quán)值；若增加

v0

后的路徑比(vi,

vj)更長(zhǎng)，則維持

dist[i][j]不變。然后在修改后的

dist矩陣中，另選一個(gè)頂點(diǎn)

v1

作為中間頂點(diǎn)，重復(fù)以上操作，直到除

vi

和

vj外的其余頂點(diǎn)都做過(guò)中間頂點(diǎn)為止。鄰接矩陣

dist[n][n]的更新是

Floyd

算法的重點(diǎn)。依次以頂點(diǎn)

v1,

…,vn

為中間頂點(diǎn)實(shí)施以上操作時(shí)，將遞推地產(chǎn)生出一個(gè)矩陣序列D(k)[n][n](k=0,

1,

2,

…,n)。其中

D(0)[n][n]即初始鄰接矩陣

dist[n][n]，表示每一對(duì)頂點(diǎn)之間的直接路徑的權(quán)值；D(k)[n][n](1?

k<n)則表示中間頂點(diǎn)的序號(hào)不大于

k

的最短路徑長(zhǎng)度。顯然，D(n)[n][n]就是每一對(duì)頂點(diǎn)之間的最短路徑長(zhǎng)度。為了記錄每一對(duì)頂點(diǎn)之間最短路徑所經(jīng)過(guò)的具體路徑，需另設(shè)一個(gè)path

矩陣，其每個(gè)元素path[i][j]所保存的值是頂點(diǎn)vi

到頂點(diǎn)vj

時(shí)vj的前趨頂點(diǎn)。類(lèi)似的，path(0)給出了每一對(duì)頂點(diǎn)之間的直接路徑，而

path(n)給出了每一對(duì)頂點(diǎn)之間的最短路徑。算法7.10

所示為用C

語(yǔ)言描述的Floyd

算法。算法

7.10

Floyd

最短路徑算法。int

path[n][n]; //路徑矩陣

void

Floyd(float

D[][n],dist[][n])//D

是路徑長(zhǎng)度矩陣,dist

是有向網(wǎng)絡(luò)G的帶權(quán)鄰接矩陣//設(shè)置D

和path的初值{ int

i,

j,

k,

next,max=10000;for

(i=0;

i<n;

i++)for

(j=0;

j<n;

j++){ if

(dist[i][j]!=Max)

path[i][j]=i+1; //i

是j

的前趨else

path[i][j]=0;D[i][j]=dist[i][j];}

//endfor//以

0,

1,

…,

n-1

為中間頂點(diǎn)做

n

次for

(k=0;

k<n;

k++)

for

(i=0;

i<n;

i++)for

(j=0;

j<n;j++)if

(D[i][j]>(D[i][k]+D[k][j])){ D[i][j]=D[i][k]+D[k][j];

//修改路徑長(zhǎng)度path[i][j]=path[k][j];

//修改路徑}

//endforfor

(i=0;

i<n;

i++)

//輸出所有頂點(diǎn)對(duì)i,j

之間最短路徑的長(zhǎng)度和路徑for

(j=0;

j<n;

j++){ printf

(

"

%f%d

",

D[i][j],

j);pre=path[i][j];while

((pre!=0)&&(pre!=i+1)){ printf

("<-%d

",

pre-1);pre=path[i][pre-1];}

//endwhileprintf

("<-%d\n

",

i);}

//endfor}

//

Floyd仍以圖7.13中的有向網(wǎng)絡(luò)為例，執(zhí)行算法7.10時(shí)矩陣D和path的更新如表7.2

所示。表7.2Floyd

算法對(duì)圖7.13

中有向網(wǎng)絡(luò)的執(zhí)行過(guò)程(k＝0,3

時(shí)無(wú)更新)k初始矩陣0(無(wú)更新)1034inf12inf034inf12inf034inf8infinf09Inf5Infinf09inf5infinf09inf5infDinfinfinfinf0inf60infInfInfinfinfinfinfinf0inf60infinfinfinfinfinfinfinf0inf60infinfinfinfinfinf711020infinf711020infinf711020inf5infinfInf0inf5infinfInf0inf514inf100111010111010111020022020022020022020path000030340000000030340000000030340000005555005555005555060006060006062026k245034108inf0341082803410828inf09155infinf0915525inf0915525Dinfinfinfinf0inf60infInfinfinfinfinfinfinf0inf60infInfinfinfinfinfinfinf0inf60infinfinfinfinfinf711020infinf711020inf25711020inf51420100inf51421100inf51421100111320111325111325022320022325022325path000030340000000030340000000030340000005555005555065555063026062526062526我們用頂點(diǎn)表示某個(gè)活動(dòng)，頂點(diǎn)之間的有向邊表示活動(dòng)之間的先后關(guān)系，這樣，無(wú)論是工程、生產(chǎn)或?qū)I(yè)課程的學(xué)習(xí)，都可以用一個(gè)有向圖來(lái)表示，并稱(chēng)其為頂點(diǎn)表示活動(dòng)網(wǎng)絡(luò)

(Activity

On

Vertex

network，簡(jiǎn)稱(chēng)AOV網(wǎng))。AOV網(wǎng)中的頂點(diǎn)也可帶有權(quán)值，表示完成一項(xiàng)活動(dòng)所需的時(shí)間，AOV網(wǎng)中的有向邊表示了活動(dòng)之間的制約關(guān)系。7.6

拓?fù)渑判蜻@些活動(dòng)可以表示一個(gè)工程中的子工程、一個(gè)產(chǎn)品生產(chǎn)中的部件生產(chǎn)或課程學(xué)習(xí)中的一門(mén)課程，因此一般要按一定次序進(jìn)行。當(dāng)限制各個(gè)活動(dòng)只能串行進(jìn)行時(shí)，如果可以將

AOV網(wǎng)中的所有頂點(diǎn)排列成一個(gè)線性序列

vi1,

vi2,

…,vin，并且這個(gè)序列同時(shí)滿足關(guān)系：若在

AOV網(wǎng)中從頂點(diǎn)

vi到頂點(diǎn)

vj存在一條路徑，則在線性序列中

vi必在

vj之前，那么，這個(gè)線性序列就稱(chēng)為拓?fù)湫蛄小?duì)

AOV網(wǎng)構(gòu)造拓?fù)湫蛄械牟僮鞣Q(chēng)為拓?fù)渑判?。AOV

網(wǎng)的拓?fù)湫蛄薪o出了各個(gè)活動(dòng)按序完成的一種可行方案。拓?fù)渑判驊?yīng)用十分廣泛。例如，軟件專(zhuān)業(yè)的學(xué)生必須完成一系列的課程學(xué)習(xí)才能畢業(yè)，其中一些課程是基礎(chǔ)課，無(wú)須先修其他課程便可學(xué)習(xí)；而另一些課程則必須在學(xué)完其他的基礎(chǔ)先修課后才能進(jìn)行學(xué)習(xí)。這些課程和課程之間的關(guān)系如表7.3所示，其AOV網(wǎng)表示如圖7.14所示。這里有向邊<Ci

,Cj>表示了課程Ci

是課程Cj

的先修課程。表7.3軟件專(zhuān)業(yè)的課程設(shè)置課程編號(hào)課程名稱(chēng)先修課程課程編號(hào)課程名稱(chēng)先修課程C1程序設(shè)計(jì)基礎(chǔ)無(wú)C7編譯原理C3,

C5C2離散數(shù)學(xué)C1C8操作系統(tǒng)C3,

C6C3數(shù)據(jù)結(jié)構(gòu)C1,

C2C9高等數(shù)學(xué)無(wú)C4匯編語(yǔ)言C1C10線性代數(shù)C9C5語(yǔ)言的設(shè)計(jì)和分析C3,

C4C11普通物理C9C6計(jì)算機(jī)原理C11C12數(shù)值分析C1,

C9,

C10圖7.14

表示課程先后關(guān)系的AOV網(wǎng)AOV網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)檫@意味著某些活動(dòng)是以自己為先決條件，這顯然是荒謬的。例如，AOV網(wǎng)中存在環(huán)，對(duì)于程序的數(shù)據(jù)流圖則意味著程序存在一個(gè)死循環(huán)。要判斷一個(gè)AOV網(wǎng)中是否存在有向環(huán)，可以先構(gòu)造其拓?fù)湫蛄?，如果拓?fù)湫蛄兄胁](méi)有包含網(wǎng)中所有的頂點(diǎn)，則該AOV網(wǎng)必定存在有向環(huán)。反之，任何一個(gè)無(wú)環(huán)的AOV網(wǎng)中的所有頂點(diǎn)都可排列在一個(gè)拓?fù)湫蛄?。拓?fù)渑判虻幕静僮魅缦拢簭木W(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)并且輸出它。從網(wǎng)中刪除此頂點(diǎn)及所有由它發(fā)出的邊。重復(fù)上述兩步，直到網(wǎng)中沒(méi)有入度為0的頂點(diǎn)為止。

以上操作的結(jié)果有兩種：網(wǎng)中無(wú)有向環(huán)，則網(wǎng)中的全部頂點(diǎn)被輸出到拓?fù)湫蛄兄?；網(wǎng)中存在有向環(huán)，頂點(diǎn)未被全部輸出，剩余頂點(diǎn)的入度均不為0。第二種情況下的拓?fù)渑判蚴遣粫?huì)成

功的。對(duì)圖7.14所示的AOV網(wǎng)進(jìn)行拓?fù)渑判?，可以得到一種拓?fù)湫蛄蠧1,C2

,C4,C9,C3,C10,C11,C12,C6,C5,C7,C8，具體過(guò)程如圖7.15所示。注意到，在選擇入度為0

的頂點(diǎn)時(shí)可能會(huì)有多個(gè)選擇，因此可以產(chǎn)生多種拓?fù)湫蛄?。任何一種拓?fù)湫蛄卸伎梢员ＷC在學(xué)習(xí)任一門(mén)課程時(shí)，這門(mén)課程的先修課程已經(jīng)學(xué)過(guò)。圖7.15

AOV網(wǎng)拓?fù)渑判蜻^(guò)程拓?fù)渑判蚍椒ǖ挠?jì)算機(jī)實(shí)現(xiàn)，可以采用鄰接矩陣表示有向圖，但是拓?fù)渑判虻男什桓?，我們下面只討論用鄰接表存?chǔ)有向圖的拓?fù)渑判蛩惴ā榱吮阌诳疾烀總€(gè)頂點(diǎn)的入度，可以在排序算法中增加一個(gè)局部向量indegree[n]來(lái)保存各頂點(diǎn)當(dāng)前的入度，同時(shí)為避免每次選擇入度為0的頂點(diǎn)時(shí)掃描整個(gè)

indegree向量，設(shè)置一個(gè)棧S暫存當(dāng)前所有入度為0的頂點(diǎn)。因此，在進(jìn)行拓?fù)渑判蛑?，掃描indegree向量，將入度為零的頂點(diǎn)序號(hào)存入棧。在拓?fù)渑判蜻^(guò)程中，每次選入度為零的頂點(diǎn)時(shí)，只需做出棧操作即可。算法中刪除入度為0的頂點(diǎn)及其所有出邊的操作只需檢查出棧的頂點(diǎn)i的出邊表，把每條弧<i,j>的終點(diǎn)j所對(duì)應(yīng)的入度indegree[j]減1(相當(dāng)于刪除此出邊)，若indegree[j]變?yōu)?，則將j入棧。拓?fù)渑判虻乃惴ㄈ缢惴?.11所示。算法

7.11

拓?fù)渑判蛩惴?鄰接表)。void

TopoSort(vexnode

g[]) //AOV

網(wǎng)的鄰接表g{

int

indegree[n];Stack

S;int

i,

j,

count=0;edgenode

*p;//入度向量//入度為0

的棧//c