數(shù)據(jù)結(jié)構(gòu)第三版李春葆第8章 圖

8.1圖的基本概念第8章圖8.2圖的存儲結(jié)構(gòu)8.3圖的遍歷8.4生成樹和最小生成樹8.5最短路徑8.6拓?fù)渑判虮菊滦〗Y(jié)8.7AOE網(wǎng)與關(guān)鍵路徑8.1圖的基本概念8.1.1圖的定義

圖(Graph)G由兩個(gè)集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點(diǎn)的有限集合,記為V(G),E是連接V中兩個(gè)不同頂點(diǎn)(頂點(diǎn)對)的邊的有限集合,記為E(G)。和離散數(shù)學(xué)中采用的方法相同，通過頂點(diǎn)集和邊集來表示一個(gè)圖的邏輯結(jié)構(gòu)，實(shí)際上就是二元組表示。在圖G中,如果代表邊的頂點(diǎn)對是無序的,則稱G為無向圖,無向圖中代表邊的無序頂點(diǎn)對通常用圓括號括起來,用以表示一條無向邊。如果表示邊的頂點(diǎn)對是有序的,則稱G為有向圖,在有向圖中代表邊的頂點(diǎn)對通常用尖括號括起來。8.1.2圖的基本術(shù)語

1.端點(diǎn)和鄰接點(diǎn)在一個(gè)無向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個(gè)端點(diǎn),并稱它們互為鄰接點(diǎn)。在一個(gè)有向圖中,若存在一條邊<vi,vj>,則稱此邊是頂點(diǎn)vi的一條出邊,同時(shí)也是頂點(diǎn)vj的一條入邊；稱vi和vj分別為此邊的起始端點(diǎn)(簡稱為起點(diǎn))和終止端點(diǎn)(簡稱終點(diǎn))；稱vi和vj互為鄰接點(diǎn)。13024(a)13024(b)

2.頂點(diǎn)的度、入度和出度在無向圖中,頂點(diǎn)所具有的邊的數(shù)目稱為該頂點(diǎn)的度。在有向圖中,以頂點(diǎn)vi為終點(diǎn)的入邊的數(shù)目,稱為該頂點(diǎn)的入度。以頂點(diǎn)vi為始點(diǎn)的出邊的數(shù)目,稱為該頂點(diǎn)的出度。一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。若一個(gè)圖中有n個(gè)頂點(diǎn)和e條邊,每個(gè)頂點(diǎn)的度為di(1≤i≤n),則有：13024(a)13024(b)

3.完全圖若無向圖中的每兩個(gè)頂點(diǎn)之間都存在著一條邊,有向圖中的每兩個(gè)頂點(diǎn)之間都存在著方向相反的兩條邊,則稱此圖為完全圖。顯然,完全無向圖包含有條邊,完全有向圖包含有n(n-1)條邊。例如,圖(a)所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全無向圖,共有6條邊。圖(b)所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全有向圖,共有12條邊。

(b)10231023(a)

4.稠密圖、稀疏圖當(dāng)一個(gè)圖接近完全圖時(shí),則稱為稠密圖。相反,當(dāng)一個(gè)圖含有較少的邊數(shù)(即當(dāng)e<<n(n-1))時(shí),則稱為稀疏圖。

5.子圖設(shè)有兩個(gè)圖G=(V,E)和G’=(V’,E’),若V’是V的子集,即V’V,且E’是E的子集,即E’E,則稱G’是G的子圖。例如圖(b)是圖(a)的子圖,而圖(c)不是圖(a)的子圖。(a)1302413024(b)13024(c)6.路徑和路徑長度在一個(gè)圖G=(V,E)中,從頂點(diǎn)vi到頂點(diǎn)vj的一條路徑是一個(gè)頂點(diǎn)序列(vi,vi1,vi2,…,vim,vj),若此圖G是無向圖,則邊(vi,vi1),(vi1,vi2),…,(vim-1,vim),(vim,vj)屬于E(G)；若此圖是有向圖,則<vi,vi1>,<vi1,vi2>,…,<vim-1,vim>,<vim,vj>屬于E(G)。

路徑長度是指一條路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除開始點(diǎn)和結(jié)束點(diǎn)可以相同外,其余頂點(diǎn)均不相同,則稱此路徑為簡單路徑。例如,有圖中,(v0,v2,v1)就是一條簡單路徑,其長度為2。1023

7.回路或環(huán)若一條路徑上的開始點(diǎn)與結(jié)束點(diǎn)為同一個(gè)頂點(diǎn),則此路徑被稱為回路或環(huán)。開始點(diǎn)與結(jié)束點(diǎn)相同的簡單路徑被稱為簡單回路或簡單環(huán)。例如,右圖中,(v0,v2,v1,v0)就是一條簡單回路,其長度為3。1023

8.連通、連通圖和連通分量在無向圖G中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱vi和vj是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通,則稱G為連通圖,否則稱為非連通圖。無向圖G中的極大連通子圖稱為G的連通分量。顯然,任何連通圖的連通分量只有一個(gè),即本身,而非連通圖有多個(gè)連通分量。1023102(b)(a)3

9.強(qiáng)連通圖和強(qiáng)連通分量在有向圖G中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱從vi到vj是連通的。若圖G中的任意兩個(gè)頂點(diǎn)vi和vj都連通,即從vi到vj和從vj到vi都存在路徑,則稱圖G是強(qiáng)連通圖。例如,右邊兩個(gè)圖都是強(qiáng)連通圖。有向圖G中的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。顯然,強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量,即本身,非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。1023102(b)(a)10.權(quán)和網(wǎng)圖中每一條邊都可以附有一個(gè)對應(yīng)的數(shù)值,這種與邊相關(guān)的數(shù)值稱為權(quán)。權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或花費(fèi)的代價(jià)。邊上帶有權(quán)的圖稱為帶權(quán)圖,也稱作網(wǎng)。

例8.1

有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多需要多少條邊？最少需要多少條邊？

答：有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有n(n-1)條邊(構(gòu)成一個(gè)有向完全圖的情況)；最少有n條邊(n個(gè)頂點(diǎn)依次首尾相接構(gòu)成一個(gè)環(huán)的情況)。

8.2圖的存儲結(jié)構(gòu)

8.2.1鄰接矩陣存儲方法

鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n(n＞0)個(gè)頂點(diǎn)的圖,頂點(diǎn)的順序依次為(v0,v1,…,vn-1),則G的鄰接矩陣A是n階方陣,其定義如下：

(1)如果G是無向圖,則：

A[i][j]=1:若(vi,vj)∈E(G)0:其他

(2)如果G是有向圖,則：

A[i][j]=1:若<vi,vj>∈E(G)0:其他(3)如果G是帶權(quán)無向圖,則：

A[i][j]=wij:若vi≠vj且(vi,vj)∈E(G)∞:其他(4)如果G是帶權(quán)有向圖,則：

A[i][j]=wij:若vi≠vj且<vi,vj>∈E(G)∞:其他思考題：對于有n個(gè)頂點(diǎn)e條邊的無向圖，鄰接矩陣表示時(shí)有多少個(gè)元素，多少個(gè)非0元素？對于有n個(gè)頂點(diǎn)e條邊的有向圖，鄰接矩陣表示時(shí)有多少個(gè)元素，多少個(gè)非0元素？鄰接矩陣的特點(diǎn)如下：

(1)圖的鄰接矩陣表示是唯一的。

(2)無向圖的鄰接矩陣一定是一個(gè)對稱矩陣。因此,按照壓縮存儲的思想,在具體存放鄰接矩陣時(shí)只需存放上(或下)三角形陣的元素即可。

(3)不帶權(quán)的有向圖的鄰接矩陣一般來說是一個(gè)稀疏矩陣,因此,當(dāng)圖的頂點(diǎn)較多時(shí),可以采用三元組表的方法存儲鄰接矩陣。

(4)對于無向圖,鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)vi的度。

(5)對于有向圖,鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)vi的出度(或入度)。

(6)用鄰接矩陣方法存儲圖,很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。但是,要確定圖中有多少條邊,則必須按行、按列對每個(gè)元素進(jìn)行檢測,所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲圖的局限性。鄰接矩陣的數(shù)據(jù)類型定義如下：#defineMAXV<最大頂點(diǎn)個(gè)數(shù)> typedef

struct

{intno; //頂點(diǎn)編號

InfoTypeinfo; //頂點(diǎn)其他信息}VertexType; //頂點(diǎn)類型typedef

struct //圖的定義{intedges[MAXV][MAXV]; //鄰接矩陣

int

n,e; //頂點(diǎn)數(shù),弧數(shù)

VertexType

vexs[MAXV]; //存放頂點(diǎn)信息}MGraph;8.2.2鄰接表存儲方法圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲方法。在鄰接表中,對圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表,第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊(對有向圖是以頂點(diǎn)vi為尾的弧)。每個(gè)單鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)。表結(jié)點(diǎn)表頭結(jié)點(diǎn)advexnextarcinfodatafirstarc

其中,表結(jié)點(diǎn)由三個(gè)域組成,adjvex指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置,nextarc指示下一條邊或弧的結(jié)點(diǎn),info存儲與邊或弧相關(guān)的信息,如權(quán)值等。表頭結(jié)點(diǎn)由兩個(gè)域組成,data存儲頂點(diǎn)vi的名稱或其他信息,firstarc指向鏈表中第一個(gè)結(jié)點(diǎn)。思考題：對于有n個(gè)頂點(diǎn)e條邊的無向圖，鄰接表表示時(shí)有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？對于有n個(gè)頂點(diǎn)e條邊的有向圖，鄰接表表示時(shí)有多少個(gè)表頭結(jié)點(diǎn)，多少個(gè)表結(jié)點(diǎn)？鄰接表的特點(diǎn)如下：

(1)鄰接表表示不唯一。這是因?yàn)樵诿總€(gè)頂點(diǎn)對應(yīng)的單鏈表中,各邊結(jié)點(diǎn)的鏈接次序可以是任意的,取決于建立鄰接表的算法以及邊的輸入次序。

(2)對于有n個(gè)頂點(diǎn)和e條邊的無向圖,其鄰接表有n個(gè)頂點(diǎn)結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)。顯然,在總的邊數(shù)小于n(n-1)/2的情況下,鄰接表比鄰接矩陣要節(jié)省空間。

(3)對于無向圖,鄰接表的頂點(diǎn)vi對應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目正好是頂點(diǎn)vi的度。

(4)對于有向圖,鄰接表的頂點(diǎn)vi對應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目僅僅是vi的出度。其入度為鄰接表中所有adjvex域值為i的邊結(jié)點(diǎn)數(shù)目。鄰接表存儲結(jié)構(gòu)的定義如下：typedef

struct

ANode //弧的結(jié)點(diǎn)結(jié)構(gòu)類型{int

adjvex; //該弧的終點(diǎn)位置

struct

ANode*nextarc; //指向下一條弧的指針

InfoTypeinfo; //該弧的相關(guān)信息}ArcNode;typedef

struct

Vnode //鄰接表頭結(jié)點(diǎn)的類型{Vertexdata; //頂點(diǎn)信息

ArcNode*firstarc; //指向第一條弧}VNode;typedef

VNode

AdjList[MAXV];//AdjList是鄰接表類型typedef

struct

{AdjList

adjlist; //鄰接表

intn,e; //圖中頂點(diǎn)數(shù)n和邊數(shù)e}ALGraph; //圖的類型

例8.2

給定一個(gè)具有n個(gè)結(jié)點(diǎn)的無向圖的鄰接矩陣和鄰接表。

(1)設(shè)計(jì)一個(gè)將鄰接矩陣轉(zhuǎn)換為鄰接表的算法；

(2)設(shè)計(jì)一個(gè)將鄰接表轉(zhuǎn)換為鄰接矩陣的算法；

(3)分析上述兩個(gè)算法的時(shí)間復(fù)雜度。解：(1)在鄰接矩陣上查找值不為0的元素,找到這樣的元素后創(chuàng)建一個(gè)表結(jié)點(diǎn)并在鄰接表對應(yīng)的單鏈表中采用前插法插入該結(jié)點(diǎn)。算法如下：voidMatToList(MGraph

g,ALGraph*&G)//將鄰接矩陣g轉(zhuǎn)換成鄰接表G{inti,j,n=g.vexnum;ArcNode*p; //n為頂點(diǎn)數(shù)

G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)//給所有頭結(jié)點(diǎn)的指針域置初值

G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++) //檢查鄰接矩陣中每個(gè)元素

for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0) {p=(ArcNode*)malloc(sizeof(ArcNode));//創(chuàng)建結(jié)點(diǎn)*p p->adjvex=j; p->nextarc=G->adjlist[i].firstarc;//將*p鏈到鏈表后

G->adjlist[i].firstarc=p; }G->n=n;G->e=g.e;}

(2)在鄰接表上查找相鄰結(jié)點(diǎn),找到后修改相應(yīng)鄰接矩陣元素的值。算法如下：

voidListToMat(ALGraph*G,MGraph&g){inti,j,n=G->n;ArcNode*p;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL) {g.edges[i][p->adjvex]=1; p=p->nextarc; }}

g.n=n;g.e=G->e;}

(3)算法1的時(shí)間復(fù)雜度均為O(n2)。算法2的時(shí)間復(fù)雜度為O(n+e),其中e為圖的邊數(shù)。8.3圖的遍歷8.3.1圖的遍歷的概念從給定圖中任意指定的頂點(diǎn)(稱為初始點(diǎn))出發(fā),按照某種搜索方法沿著圖的邊訪問圖中的所有頂點(diǎn),使每個(gè)頂點(diǎn)僅被訪問一次,這個(gè)過程稱為圖的遍歷。如果給定圖是連通的無向圖或者是強(qiáng)連通的有向圖,則遍歷過程一次就能完成,并可按訪問的先后順序得到由該圖所有頂點(diǎn)組成的一個(gè)序列。根據(jù)搜索方法的不同,圖的遍歷方法有兩種：一種叫做深度優(yōu)先搜索法(DFS)；另一種叫做廣度優(yōu)先搜索法(BFS)。深度優(yōu)先搜索遍歷的過程是：（1）從圖中某個(gè)初始頂點(diǎn)v出發(fā),首先訪問初始頂點(diǎn)v。（2）選擇一個(gè)與頂點(diǎn)v相鄰且沒被訪問過的頂點(diǎn)w為初始頂點(diǎn),再從w出發(fā)進(jìn)行深度優(yōu)先搜索,直到圖中與當(dāng)前頂點(diǎn)v鄰接的所有頂點(diǎn)都被訪問過為止。以鄰接表為存儲結(jié)構(gòu)的深度優(yōu)先搜索遍歷算法如下(其中,v是初始頂點(diǎn)編號,visited[]是一個(gè)全局?jǐn)?shù)組,初始時(shí)所有元素均為0表示所有頂點(diǎn)尚未訪問過)：8.3.2深度優(yōu)先搜索遍歷體現(xiàn)出先進(jìn)先出的特點(diǎn)：用棧或遞歸方式實(shí)現(xiàn)。voidDFS(ALGraph*G,intv){ArcNode*p;intw;

visited[v]=1; //置已訪問標(biāo)記

printf("%d",v); //輸出被訪問頂點(diǎn)的編號

p=G->adjlist[v].firstarc; //p指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)

while(p!=NULL){w=p->adjvex; if(visited[w]==0)

DFS(G,w); //若w頂點(diǎn)未訪問,遞歸訪問它

p=p->nextarc; //p指向頂點(diǎn)v的下一條弧的弧頭結(jié)點(diǎn)

}}思考題：為什么visited數(shù)組需要設(shè)置為全局變量？DFS序列：21034思考題：用棧求解迷宮問題，有DFS算法有什么關(guān)聯(lián)？廣度優(yōu)先搜索遍歷的過程是：（1）訪問初始點(diǎn)v,接著訪問v的所有未被訪問過的鄰接點(diǎn)v1,v2,…,vt。（2）按照v1,v2,…,vt的次序,訪問每一個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)。（3）依次類推,直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問過為止。體現(xiàn)先進(jìn)先出的特點(diǎn)，用隊(duì)列實(shí)現(xiàn)。以鄰接表為存儲結(jié)構(gòu),用廣度優(yōu)先搜索遍歷圖時(shí),需要使用一個(gè)隊(duì)列,以類似于按層次遍歷二叉樹遍歷圖。對應(yīng)的算法如下(其中,v是初始頂點(diǎn)編號)：8.3.3廣度優(yōu)先搜索遍歷voidBFS(ALGraph*G,intv){ArcNode*p;intw,i;

intqueue[MAXV],front=0,rear=0; //定義循環(huán)隊(duì)列

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

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

printf("%2d",v); //輸出被訪問頂點(diǎn)的編號

visited[v]=1; //置已訪問標(biāo)記

rear=(rear+1)%MAXV;

queue[rear]=v; //v進(jìn)隊(duì)思考題：為什么visited數(shù)組不需要設(shè)置為全局變量？

while(front!=rear) //若隊(duì)列不空時(shí)循環(huán)

{front=(front+1)%MAXV; w=queue[front]; //出隊(duì)并賦給w p=G->adjlist[w].firstarc; //找w的第一個(gè)的鄰接點(diǎn)

while(p!=NULL) { if(visited[p->adjvex]==0) {printf(“%2d”,p->adjvex);//訪問之

visited[p->adjvex]=1; rear=(rear+1)%MAXV; //該頂點(diǎn)進(jìn)隊(duì)

queue[rear]=p->adjvex;}p=p->nextarc; //找下一個(gè)鄰接頂點(diǎn)

} }

printf("\n");}例如,以上圖的鄰接表為例調(diào)用BFS()函數(shù),假設(shè)初始頂點(diǎn)編號v=2,給出調(diào)用BFS()的執(zhí)行過程。BFS序列：21340思考題：用隊(duì)列求解迷宮問題，有BFS算法有什么關(guān)聯(lián)？8.3.4非連通圖的遍歷對于無向圖來說,若無向圖是連通圖,則一次遍歷能夠訪問到圖中的所有頂點(diǎn)；但若無向圖是非連通圖,則只能訪問到初始點(diǎn)所在連通分量中的所有頂點(diǎn),其他連通分量中的頂點(diǎn)是不可能訪問到的。為此需要從其他每個(gè)連通分量中選擇初始點(diǎn),分別進(jìn)行遍歷,才能夠訪問到圖中的所有頂點(diǎn)；對于有向圖來說,若從初始點(diǎn)到圖中的每個(gè)頂點(diǎn)都有路徑,則能夠訪問到圖中的所有頂點(diǎn)；否則不能訪問到所有頂點(diǎn),為此同樣需要再選初始點(diǎn),繼續(xù)進(jìn)行遍歷,直到圖中的所有頂點(diǎn)都被訪問過為止。采用深度優(yōu)先搜索遍歷非連通無向圖的算法如下：DFS1(ALGraph*G){

inti;for(i=0;i<G->n;i++)//遍歷所有未訪問過的頂點(diǎn)

if(visited[i]==0)

DFS(G,i);}采用廣度優(yōu)先搜索遍歷非連通無向圖的算法如下：BFS1(ALGraph*G){inti;for(i=0;i<G->n;i++)//遍歷所有未訪問過的頂點(diǎn)

if(visited[i]==0)

BFS(G,i);}8.3.5圖遍歷的應(yīng)用

例8.3

假設(shè)圖G采用鄰接表存儲，設(shè)計(jì)一個(gè)算法，判斷無向圖G是否連通。若連通則返回1；否則返回0。

解：采用遍歷方式判斷無向圖G是否連通。這里用深度優(yōu)先遍歷方法，先給visited[]數(shù)組（為全局變量）置初值0，然后從0頂點(diǎn)開始遍歷該圖。在一次遍歷之后，若所有頂點(diǎn)i的visited[i]均為1，則該圖是連通的；否則不連通。對應(yīng)的算法如下：int

Connect(ALGraph*G)//判斷無向圖G的連通性{int

i,flag=1;for(i=0;i<G->n;i++) //visited數(shù)組置初值

visited[i]=0;DFS(G,0);

//調(diào)用DSF算法,從頂點(diǎn)0開始深度優(yōu)先遍歷

for(i=0;i<G->n;i++)if(visited[i]==0){flag=0; break; }returnflag;}

例8.4

假設(shè)圖G采用鄰接表存儲，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的長度為l的所有簡單路徑。

解：所謂簡單路徑是指路徑上的頂點(diǎn)不重復(fù)。利用回溯的深度優(yōu)先搜索方法。從頂點(diǎn)u開始，進(jìn)行深度優(yōu)先搜索，在搜索過程中，需要把當(dāng)前的搜索線路記錄下來。為此設(shè)立一個(gè)數(shù)組path保存走過的路徑，用d記錄走過的路徑長度。若當(dāng)前掃描到的結(jié)點(diǎn)u等于v且路徑長度為l時(shí)，表示找到了一條路徑，則輸出路徑path。對應(yīng)的算法如下：voidPathAll(ALGraph*G,int

u,int

v,int

l,int

path[],intd)//d是到當(dāng)前為止已走過的路徑長度，調(diào)用時(shí)初值為-1{

int

m,i;ArcNode*p;

visited[u]=1;d++; //路徑長度增1

path[d]=u; //將當(dāng)前頂點(diǎn)添加到路徑中

if(u==v&&d==l) //輸出一條路徑

{printf("");for(i=0;i<=d;i++)printf("%d",path[i]);

printf("\n");}p=G->adjlist[u].firstarc;//p指向u的第一條弧的弧頭結(jié)點(diǎn)

while(p!=NULL){m=p->adjvex; //m為u的鄰接頂點(diǎn)

if(visited[m]==0) //若頂點(diǎn)未標(biāo)記訪問,則遞歸訪問之

PathAll(G,m,v,l,path,d); p=p->nextarc //找u的下一個(gè)鄰接頂點(diǎn)

}

visited[u]=0;

//恢復(fù)環(huán)境}voidmain(){int

path[MAXV],u=1,v=4,d=3,i,j;

MGraphg;

ALGraph*G;

g.n=5;g.e=6;

intA[MAXV][MAXV]={{0,1,0,1,0},{1,0,1,0,0}, {0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}}; for(i=0;i<g.n;i++) //建立圖8.1(a)的鄰接矩陣

for(j=0;j<g.n;j++)

g.edges[i][j]=A[i][j];

MatToList(g,G);for(i=0;i<g.n;i++)visited[i]=0;

printf("圖G:\n");DispAdj(G); //輸出鄰接表

printf("從%d到%d的所有長度為%d路徑:\n",u,v,d);PathAll(G,u,v,d,path,-1);

printf("\n");}教材中藍(lán)字有誤。程序執(zhí)行結(jié)果如下：圖G:0:131:022:1343:0244:23從1到4的所有長度為3路徑:1034123413240

例8.5

假設(shè)圖G采用鄰接表存儲，設(shè)計(jì)一個(gè)算法，求圖中通過某頂點(diǎn)k的所有簡單回路（若存在）。并輸出如下圖所示的有向圖的鄰接表和通過頂點(diǎn)0的所有回路。01423int

visited[MAXV]； //全局變量voidDFSPath(ALGraph*G,int

u,int

v,int

path[],intd)//d是到當(dāng)前為止已走過的路徑長度，調(diào)用時(shí)初值為-1{int

m,i;ArcNode*p;

visited[u]=1;d++;path[d]=u;p=G->adjlist[u].firstarc;//p指向頂點(diǎn)u的第一條邊

while(p!=NULL){m=p->adjvex; //m為頂點(diǎn)u的相鄰點(diǎn)

if(m==v&&d>0) //找到一個(gè)回路，輸出之

{printf(""); for(i=0;i<=d;i++)

printf("%d",path[i]);

printf("%d\n",v); } if(visited[m]==0) //m未訪問,則遞歸訪問之

DFSPath(G,m,v,path,d); p=p->nextarc; //找u的下一個(gè)鄰接頂點(diǎn)

}

visited[u]=0; //恢復(fù)環(huán)境：使該頂點(diǎn)可重新使用}voidFindCyclePath(ALGraph*G,intk)//輸出經(jīng)過頂點(diǎn)k的所有回路{int

path[MAXV];

printf("經(jīng)過頂點(diǎn)%d的所有回路\n",k);DFSPath(G,k,k,path,-1);}8.4生成樹和最小生成樹8.4.1生成樹的概念一個(gè)連通圖的生成樹是一個(gè)極小連通子圖,它含有圖中全部頂點(diǎn),但只有構(gòu)成一棵樹的(n-1)條邊。命題：如果在一棵生成樹上添加一條邊,必定構(gòu)成一個(gè)環(huán)。因?yàn)檫@條邊使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。一棵有n個(gè)頂點(diǎn)的生成樹(連通無回路圖)有且僅有(n-1)條邊,如果一個(gè)圖有n個(gè)頂點(diǎn)和小于(n-1)條邊,則是非連通圖。如果它多于(n-1)條邊,則一定有回路。但是,有(n-1)條邊的圖不一定都是生成樹。

對于一個(gè)帶權(quán)(假定每條邊上的權(quán)均為大于零的實(shí)數(shù))連通無向圖G中的不同生成樹,其每棵樹的所有邊上的權(quán)值之和也可能不同；圖的所有生成樹中具有邊上的權(quán)值之和最小的樹稱為圖的最小生成樹。按照生成樹的定義,n個(gè)頂點(diǎn)的連通圖的生成樹有n個(gè)頂點(diǎn)、n-1條邊。因此,構(gòu)造最小生成樹的準(zhǔn)則有三條：

(1)必須只使用該圖中的邊來構(gòu)造最小生成樹；

(2)必須使用且僅使用n-1條邊來連接圖中的n個(gè)頂點(diǎn)；

(3)不能使用產(chǎn)生回路的邊。8.4.2無向圖的連通分量和生成樹在對無向圖進(jìn)行遍歷時(shí),對于連通圖,僅需調(diào)用遍歷過程(DFS或BFS)一次,從圖中任一頂點(diǎn)出發(fā),便可以遍歷圖中的各個(gè)頂點(diǎn)。對非連通圖,則需多次調(diào)用遍歷過程,每次調(diào)用得到的頂點(diǎn)集連同相關(guān)的邊就構(gòu)成圖的一個(gè)連通分量。設(shè)G=(V,E)為連通圖,則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí),必定將E(G)分成兩個(gè)集合T和B,其中T是遍歷圖過程中走過的邊的集合,B是剩余的邊的集合：T∩B=Φ,T∪B=E(G)。顯然,G'=(V,T)是G的極小連通子圖,即G'是G的一棵生成樹。由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。這樣的生成樹是由遍歷時(shí)訪問過的n個(gè)頂點(diǎn)和遍歷時(shí)經(jīng)歷的n-1條邊組成。對于非連通圖,每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過的邊一起構(gòu)成一棵生成樹,各個(gè)連通分量的生成樹組成非連通圖的生成森林。8.4.4普里姆算法

普里姆(Prim)算法是一種構(gòu)造性算法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖,T=(U,TE)是G的最小生成樹,其中U是T的頂點(diǎn)集,TE是T的邊集,則由G構(gòu)造最小生成樹T的步驟如下：

(1)初始化U={v}。v到其他頂點(diǎn)的所有邊為候選邊；

(2)重復(fù)以下步驟n-1次,使得其他n-1個(gè)頂點(diǎn)被加入到U中：①從候選邊中挑選權(quán)值最小的邊輸出,設(shè)該邊在V-U中的頂點(diǎn)是k,將v加入U(xiǎn)中,刪除和k關(guān)聯(lián)的邊；②考察當(dāng)前V-U中的所有頂點(diǎn)vi,修改候選邊：若(vi,vk)的權(quán)值小于原來和vk關(guān)聯(lián)的候選邊,則用(v,vi)取代后者作為候選邊。普里姆算法過程：vkUV－UkiUV－Uv普里姆算法求解最小生成樹的過程01234651951418271682131270432165148531621

012

34

56closestlowcost19∞18∞14∞0000000001648412483337213325500UV-U(i,closest[i])i∈U，closest[i]∈V－U候選邊：普里姆(Prim)算法如下：#defineINF32767//INF表示∞voidPrim(int

cost[][MAXV],int

n,intv){int

lowcost[MAXV],min;

intclosest[MAXV],i,j,k;for(i=0;i<n;i++)//給lowcost[]和closest[]置初值

{lowcost[i]=cost[v][i];

closest[i]=v; }

for(i=1;i<n;i++)//找出n-1個(gè)頂點(diǎn)

{min=INF; for(j=0;j<n;j++) //在(V-U)中找出離U最近的頂點(diǎn)k if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}

printf("邊(%d,%d)權(quán)為:%d\n",closest[k],k,min);

lowcost[k]=0;//標(biāo)記k已經(jīng)加入U(xiǎn) for(j=0;j<n;j++)//修改數(shù)組lowcost和closestif(cost[k][j]!=0&&cost[k][j]<lowcost[j]){lowcost[j]=cost[k][j];closest[j]=k;}}}

Prim()算法中有兩重for循環(huán),所以時(shí)間復(fù)雜度為O(n2)。8.4.5克魯斯卡爾算法

克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹的方法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖,T=(U,TE)是G的最小生成樹。

(1)置U的初值等于V(即包含有G中的全部頂點(diǎn)),TE的初值為空集(即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量)。

(2)將圖G中的邊按權(quán)值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止?？唆斔箍査惴ㄇ蠼庾钚∩蓸涞倪^程035214516354652025314NOViVjW1021235231434254503561257235801692461045660033110000為了簡便,在實(shí)現(xiàn)克魯斯卡爾算法Kruskal()時(shí),參數(shù)E存放圖G中的所有邊,假設(shè)它們是按權(quán)值從小到大的順序排列的。n為圖G的頂點(diǎn)個(gè)數(shù),e為圖G的邊數(shù)。

typedef

struct

{ intu;//邊的起始頂點(diǎn)

intv;//邊的終止頂點(diǎn)

intw;//邊的權(quán)值

}Edge;voidKruskal(Edge

E[],int

n,inte){inti,j,m1,m2,sn1,sn2,k;int

vset[MAXV];for(i=0;i<n;i++)vset[i]=i; //初始化輔助數(shù)組

k=1;//k表示當(dāng)前構(gòu)造最小生成樹的第幾條邊,初值為1j=0;//E中邊的下標(biāo),初值為0while(k<n)//生成的邊數(shù)小于n時(shí)循環(huán)

{m1=E[j].u;m2=E[j].v; //取一條邊的頭尾頂點(diǎn)

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

if(sn1!=sn2) //屬不同的集合->最小生成樹的一條邊

{printf("(%d,%d):%d\n",m1,m2,E[j].w); k++; //生成邊數(shù)增1 for(i=0;i<n;i++) //兩個(gè)集合統(tǒng)一編號

if(vset[i]==sn2) //集合編號為sn2的改為sn1

vset[i]=sn1; } j++; //掃描下一條邊

}}

采用并查集求解（改進(jìn)克魯斯卡爾算法）：voidKruskal(MGraphg){

inti,j,k,u1,v1,sn1,sn2;

UFSTree

t[MaxSize];EdgeE[MaxSize];k=1; //e數(shù)組的下標(biāo)從1開始計(jì)

for(i=0;i<g.n;i++) //由g產(chǎn)生的邊集E for(j=0;j<g.n;j++) if(g.edges[i][j]!=0&&g.edges[i][j]!=INF) { E[k].u=i;E[k].v=j;

E[k].w=g.edges[i][j]; k++; }

HeapSort(E,g.e); //采用堆排序?qū)數(shù)組按權(quán)值遞增排序

MAKE_SET(t,g.n); //初始化并查集樹tk=1; //k表示當(dāng)前構(gòu)造生成樹的第幾條邊,初值為1j=1; //E中邊的下標(biāo),初值為1while(k<g.n) //生成的邊數(shù)小于n時(shí)循環(huán)

{u1=E[j].u;v1=E[j].v; //取一條邊的頭尾頂點(diǎn)編號u1和v2sn1=FIND_SET(t,u1);sn2=FIND_SET(t,v1);//分別得到兩個(gè)頂點(diǎn)所屬的集合編號

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

{printf("(%d,%d):%d\n",u1,v1,E[j].w); k++; //生成邊數(shù)增1 UNION(t,u1,v1); //將u1和v1兩個(gè)頂點(diǎn)合并

}j++; //掃描下一條邊

}}如果給定的帶權(quán)連通無向圖G有e條邊,n個(gè)頂點(diǎn)，采用堆排序(在第10章中介紹)對邊按權(quán)值遞增排序，那么用改進(jìn)克魯斯卡爾算法構(gòu)造最小生成樹的時(shí)間復(fù)雜度降為O(elog2e)。由于它與n無關(guān)，只與e有關(guān)，所以克魯斯卡爾算法適合于稀疏圖。思考題有n臺計(jì)算機(jī)，已知它們的位置，現(xiàn)連成一個(gè)網(wǎng)絡(luò)，采用什么算法求解所花最少網(wǎng)線。8.5最短路徑8.5.1路徑的概念

在一個(gè)無權(quán)的圖中,若從一頂點(diǎn)到另一頂點(diǎn)存在著一條路徑,則稱該路徑長度為該路徑上所經(jīng)過的邊的數(shù)目,它等于該路徑上的頂點(diǎn)數(shù)減1。由于從一頂點(diǎn)到另一頂點(diǎn)可能存在著多條路徑,每條路徑上所經(jīng)過的邊數(shù)可能不同,即路徑長度不同,我們把路徑長度最短(即經(jīng)過的邊數(shù)最少)的那條路徑叫做最短路徑,其路徑長度叫做最短路徑長度或最短距離。對于帶權(quán)的圖,考慮路徑上各邊上的權(quán)值,則通常把一條路徑上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長度或稱帶權(quán)路徑長度。從源點(diǎn)到終點(diǎn)可能不止一條路徑,把帶權(quán)路徑長度最短的那條路徑稱為最短路徑,其路徑長度(權(quán)值之和)稱為最短路徑長度或者最短距離。8.5.2從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑

問題：給定一個(gè)帶權(quán)有向圖G與源點(diǎn)v,求從v到G中其他頂點(diǎn)的最短路徑,并限定各邊上的權(quán)值大于或等于0。

采用狄克斯特拉(Dijkstra)算法求解基本思想是：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖,把圖中頂點(diǎn)集合V分成兩組：第一組為已求出最短路徑的頂點(diǎn)集合(用S表示,初始時(shí)S中只有一個(gè)源點(diǎn),以后每求得一條最短路徑v,…vk,就將vk加入到集合S中,直到全部頂點(diǎn)都加入到S中,算法就結(jié)束了)

第二組為其余未確定最短路徑的頂點(diǎn)集合(用U表示)。按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中,總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外,每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離,S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度,U中的頂點(diǎn)的距離從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。

(1)初始時(shí),S只包含源點(diǎn),即S={v},v的距離為0。U包含除v外的其他頂點(diǎn),U中頂點(diǎn)u距離為邊上的權(quán)(若v與u有邊<v,u>)或∞(若u不是v的出邊鄰接點(diǎn))。

(2)從U中選取一個(gè)距離v最小的頂點(diǎn)k,把k加入S中(該選定的距離就是v到k的最短路徑長度)。

(3)以k為新考慮的中間點(diǎn),修改U中各頂點(diǎn)的距離：若從源點(diǎn)v到頂點(diǎn)u(u∈U)的距離(經(jīng)過頂點(diǎn)k)比原來距離(不經(jīng)過頂點(diǎn)k)短,則修改頂點(diǎn)u的距離值,修改后的距離值的頂點(diǎn)k的距離加上邊<k,u>上的權(quán)。

(4)重復(fù)步驟(2)和(3)直到所有頂點(diǎn)都包含在S中。狄克斯特拉算法的過程頂點(diǎn)V到j(luò)的最小距離＝MIN(cvk+wkj,cvj)

S U dist[]path[]01234560123456{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,0,0,0,-1,-1,-1}{0,1}{2,3,4,5,6}{0,4,5,6,11,∞,∞}{0,0,1,0,1,-1,-1}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,0,1,0,5,2,5}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}438164256147660123456distpath00466∞∞∞00000401155969101711525101641656201狄克斯特拉算法如下(n為圖G的頂點(diǎn)數(shù),v0為源點(diǎn)編號)：voidDijkstra(int

cost[][MAXV],int

n,intv0){intdist[MAXV],path[MAXV];

int

s[MAXV];int

mindis,i,j,u;for(i=0;i<n;i++){dist[i]=cost[v0][i]; //距離初始化

s[i]=0; //s[]置空

if(cost[v0][i]<INF) //路徑初始化

path[i]=v0; else path[i]=-1;}s[v0]=1;path[v0]=0; //源點(diǎn)編號v0放入s中

for(i=0;i<n;i++)//循環(huán)直到所有頂點(diǎn)的最短路徑都求出

{mindis=INF; u=-1; for(j=0;j<n;j++)//選取不在s中且具有最小距離的頂點(diǎn)u if(s[j]==0&&dist[j]<mindis) {u=j;mindis=dist[j]; } s[u]=1;//頂點(diǎn)u加入s中

for(j=0;j<n;j++)//修改不在s中的頂點(diǎn)的距離

if(s[j]==0) if(cost[u][j]<INF&&dist[u]+cost[u][j]<dist[j]) {dist[j]=dist[u]+cost[u][j];path[j]=u;}}Dispath(dist,path,s,n,v0); //輸出最短路徑}09年考研題

1.帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假設(shè)從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法：（1）設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；（2）選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v；（3）重復(fù)步驟（2），直到u是目標(biāo)頂點(diǎn)時(shí)為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。思考題求單源最短路徑問題是否可以采用求最小生成樹的方法求解？8.5.3每對頂點(diǎn)之間的最短路徑

問題：對于一個(gè)各邊權(quán)值均大于零的有向圖,對每一對頂點(diǎn)vi≠vj,求出vi與vj之間的最短路徑和最短路徑長度?？梢酝ㄟ^以每個(gè)頂點(diǎn)作為源點(diǎn)循環(huán)求出每對頂點(diǎn)之間的最短路徑。除此之外,弗洛伊德(Floyd)算法也可用于求兩頂點(diǎn)之間最短路徑。假設(shè)有向圖G=(V,E)采用鄰接矩陣cost存儲,另外設(shè)置一個(gè)二維數(shù)組A用于存放當(dāng)前頂點(diǎn)之間的最短路徑長度,分量A[i][j]表示當(dāng)前頂點(diǎn)vi到頂點(diǎn)vj的最短路徑長度。弗洛伊德算法的基本思想是遞推產(chǎn)生一個(gè)矩陣序列A0,A1,…,Ak,…,An,其中Ak[i][j]表示從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號不大于k的最短路徑長度。

初始時(shí),有A-1[i][j]=cost[i][j]。當(dāng)求從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號不大于k+1的最短路徑長度時(shí),要分兩種情況考慮：一種情況是該路徑不經(jīng)過頂點(diǎn)編號為k+1的頂點(diǎn),此時(shí)該路徑長度與從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號不大于k的最短路徑長度相同；另一種情況是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑上經(jīng)過編號為k+1的頂點(diǎn)。Ak+1[i,j]=MIN(Ak[i,j],Ak[i,k+1]+Ak[k+1,j])那么,該路徑可分為兩段:(1)從頂點(diǎn)vi到頂點(diǎn)vk+1的最短路徑;(2)從頂點(diǎn)vk+1到頂點(diǎn)vj的最短路徑。此時(shí)最短路徑長度等于這兩段路徑長度之和。這兩種情況中的較小值,就是所要求的從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號不大于k+1的最短路徑。弗洛伊德思想可用如下的表達(dá)式來描述：

A-1[i][j]=cost[i][j]Ak+1[i][j]=MIN{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤k≤n-1)

采用弗洛伊德算法求解過程012353273124

考慮頂點(diǎn)v0,A0[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v0的最短路徑。

v2-v0-v1：不改變。

v2-v0-v3：不改變。

v3-v2-v0-v1：不改變。012353273124

考慮頂點(diǎn)v1,A1[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v1的最短路徑。

v0-v1-v2,路徑長度為9,將A[0][2]改為9。

path[0][2]改為1。

012353273124考慮頂點(diǎn)v2,A2[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v2的最短路徑。

v3-v2-v0,長度為4,將A[3][0]改為4；

v3-v2-v1,長度為4,將A[3][1]改為4。

v1-v2-v0,長度為7,將A[1][0]改為7。將path[3][0]、path[3][1]和path[1][0]均改為2。因此,有：

012353273124考慮頂點(diǎn)v3,A3[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v3的最短路徑。

v0-v3-v2：長度為8,A[0][2]改為8；

v1-v3-v2-v0,長度為6,A[1][0]改為6；

v1-v3-v2,長度為3,A[1][2]改為3。將path[0][2]、path[1][0]后path[1][2]均改為3。012353273124從0到0路徑為：0,0 路徑長度為：0從0到1路徑為：0,1 路徑長度為：5從0到2路徑為：0,3,2 路徑長度為：8從0到3路徑為：0,3 路徑長度為：7從1到0路徑為：1,3,2,0 路徑長度為：6從1到1路徑為：1,1 路徑長度為：0從1到2路徑為：1,3,2 路徑長度為：3從1到3路徑為：1,3 路徑長度為：2A=Path=從2到0路徑為：2,0 路徑長度為：3從2到1路徑為：2,1 路徑長度為：3從2到2路徑為：2,2 路徑長度為：0從2到3路徑為：2,3 路徑長度為：2從3到0路徑為：3,2,0 路徑長度為：4從3到1路徑為：3,2,1 路徑長度為：4從3到2路徑為：3,2 路徑長度為：1從3到3路徑為：3,3 路徑長度為：0弗洛伊德算法如下：voidFloyd(int

cost[][MAXV],intn){int

A[MAXV][MAXV],path[MAXV][MAXV];inti,j,k;for(i=0;i<n;i++) for(j=0;j<n;j++){A[i][j]=cost[i][j]; path[i][j]=-1;}for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(A[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;}

Dispath(A,path,n);//輸出最短路徑}時(shí)間復(fù)雜度為O(n3)8.6拓?fù)渑判?/p>

設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖,V中頂點(diǎn)序列v1,v2,…,vn稱為一個(gè)拓?fù)湫蛄?當(dāng)且僅當(dāng)該頂點(diǎn)序列滿足下列條件：

若<vi,vj>是圖中的邊(即從頂點(diǎn)vi到vj有一條路徑),則在序列中頂點(diǎn)vi必須排在頂點(diǎn)vj之前。在一個(gè)有向圖中找一個(gè)拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。課程代號課程名稱先修課程C1高等數(shù)學(xué)無C2程序設(shè)計(jì)無C3離散數(shù)學(xué)C1C4數(shù)據(jù)結(jié)構(gòu)C2,C3C5編譯原理C2,C4C6操作系統(tǒng)C4,C7C7計(jì)算機(jī)組成原理C2

例如,計(jì)算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè),假設(shè)這些課程的名稱與相應(yīng)代號有如下關(guān)系：課程之間的先后關(guān)系可用有向圖表示

對這個(gè)有向圖進(jìn)行拓?fù)渑判蚩傻玫揭粋€(gè)拓?fù)湫蛄校篊1-C3-C2-C4-C7-C6-C5。也可得到另一個(gè)拓?fù)湫蛄校篊2-C7-C1-C3-C4-C5-C6,還可以得到其他的拓?fù)湫蛄小W(xué)生按照任何一個(gè)拓?fù)湫蛄卸伎梢皂樞虻剡M(jìn)行課程學(xué)習(xí)。

(1)從有向圖中選擇一個(gè)沒有前驅(qū)(即入度為0)的頂點(diǎn)并且輸出它。

(2)從網(wǎng)中刪去該頂點(diǎn),并且刪去從該頂點(diǎn)發(fā)出的全部有向邊。

(3)重復(fù)上述兩步,直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點(diǎn)為止。拓?fù)渑判虿襟E

為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?對于給定的有向圖,采用鄰接表作為存儲結(jié)構(gòu),為每個(gè)頂點(diǎn)設(shè)立一個(gè)鏈表,每個(gè)鏈表有一個(gè)表頭結(jié)點(diǎn),這些表頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組,表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域count。即將鄰接表定義中的VNode類型修改如下：

typedef

struct //表頭結(jié)點(diǎn)類型

{Vertexdata;//頂點(diǎn)信息

intcount;//存放頂點(diǎn)入度

ArcNode*firstarc;//指向第一條弧

}VNode;voidTopSort(VNode

adj[],intn){int

i,j;intSt[MAXV],top=-1;//棧St的指針為top

ArcNode*p;for(i=0;i<n;i++)if(adj[i].count==0) //入度為0的頂點(diǎn)入棧

{top++;St[top]=i;}while(top>-1) //棧不為空時(shí)循環(huán)

{i=St[top];top--; //出棧

printf("%d",i);p=adj[i].firstarc;while(p!=NULL){j=p->adjvex;adj[j].count--;if(adj[j].count==0) {top++;St[top]=j;}p=p->nextarc;//找下一個(gè)相鄰頂點(diǎn)

}}}8.7AOE網(wǎng)與關(guān)鍵路徑若用前面介紹過的帶權(quán)有向圖(DAG)描述工程的預(yù)計(jì)進(jìn)度,以頂點(diǎn)表示事件,有向邊表示活動,邊e的權(quán)c(e)表示完成活動e所需的時(shí)間(比如天數(shù)),或者說活動e持續(xù)時(shí)間。圖中入度為0的頂點(diǎn)表示工程的開始事件(如開工儀式),出度為0的頂點(diǎn)表示工程結(jié)束事件。則稱這樣的有向圖為AOE網(wǎng)(ActivityOnEdge)。7

整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑，具有最大長度的路徑叫關(guān)鍵路徑。abcdefghk6452118244例如:

“關(guān)鍵活動”指的是：該弧上的權(quán)值增加將使有向圖上的最長路徑的長度增加。注意：在一個(gè)AOE網(wǎng)中，可以有不止一條的關(guān)鍵路徑。源點(diǎn)匯點(diǎn)6174幾個(gè)定義：

(1)事件v的最早可發(fā)生時(shí)間：假設(shè)事件x是源點(diǎn),事件y為匯點(diǎn),并規(guī)定事件x的發(fā)生時(shí)間為0。定義圖中任一事件v的最早(eventearly)可發(fā)生時(shí)間ve(v)等于x到v所有路徑長度的最大值,即：ve(v)=

上式中的MAX是對x到v的所有路徑p取最大值,c(p)表示路徑p的長度(路徑上邊長之和),即：c(p)=

完成整個(gè)工程所需的最少時(shí)間,等于事件y的最早可發(fā)生時(shí)間ve(y)。

(2)事件v的最遲可發(fā)生時(shí)間：定義在不影響整個(gè)工程進(jìn)度的前提下,事件v必須發(fā)生的時(shí)間稱為v的最遲(eventlate)可發(fā)生時(shí)間,記作vl(v)。vl(v)應(yīng)等于ve(y)與v到y(tǒng)的最長路徑長度之差(y是匯點(diǎn)),即：vl(v)=ve(y)-

(3)