IT計(jì)算機(jī)課件第08章-圖

第8章圖

＞圖的基本概念

＞圖的基本運(yùn)算

A圖的基本存儲(chǔ)結(jié)構(gòu)

＞圖的遍歷

A生成樹與最小生成樹

A最短路徑

A拓?fù)渑判?/p>

＞關(guān)鍵路徑

8.1圖的基本概念

一、圖的定義

圖是由一個(gè)非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間

多對(duì)多關(guān)系的邊(或弧)集合組成的一種數(shù)據(jù)結(jié)構(gòu),

它可以形式化地表示為：

圖=(V,E)

其中V={X|X￡某個(gè)數(shù)據(jù)對(duì)象集},它是頂點(diǎn)的有窮

非空集合；E={(x,y)|x,yeV}^E={<x,y>|x,

ywV且P(x,y)},它是頂點(diǎn)之間關(guān)系的有窮集合,

也叫做邊集合，P(x,y)表示從x到y(tǒng)的一條單向

通路。

圖的應(yīng)用舉例

例1交通圖（公路、鐵路）

頂點(diǎn)：地點(diǎn)

邊：連接地點(diǎn)的公路

交通圖中的有單行道雙行道，分別用有向邊、無向邊表示;

例2電路圖

頂點(diǎn)：元件

邊：連接元件之間的線路

例3通訊線路圖

頂點(diǎn)：地點(diǎn)

邊：地點(diǎn)間的連線

例4各種流程圖

如產(chǎn)品的生產(chǎn)流程圖

頂點(diǎn)：工序

邊；客道工序之間的順序關(guān)系

通常，也將圖G的頂點(diǎn)集和邊集分別記為V(G)

和E(G)oE(G)可以是空集，若E(G)為空，

則圖G只有頂點(diǎn)而沒有邊。

若圖G中的每條邊都是有方向的，則稱G為有向

圖。在有向圖中，一條有向邊是由兩個(gè)頂點(diǎn)組成的有

序?qū)?，點(diǎn)序?qū)νǔＳ眉饫ㄌ?hào)表示。例如，有序?qū)Vp

多＞表示一條由M到』的意向邊。有向邊又稱為弧，水

的始點(diǎn)稱為弧尾，弧的終點(diǎn)稱為弧頭。若圖G中的每

條邊都是沒有方向的，則稱G為無向圖。無向圖中的

邊均是頂點(diǎn)的無序?qū)?，無序?qū)νǔＳ脠A括號(hào)表示。

JO圖8-1

(VJ)----<￡)(￡)------殲:有序?qū)?lt;Vj,Vj>：一工

/用以為Vi起點(diǎn)、以Vj為終點(diǎn)

/51的有向線段表示，稱為有向

4)(y^)-----(O邊或弧；

(a)有向圖Gi(b)無向圖G2

圖8.1(a)表示的是有向圖G1，該圖的頂點(diǎn)集和

邊集分別為：

v

V(G1)={rv2,v3,v4}

E(G])={vvi，v2>,<vrv3>,<v2,v4>,<v3,v2>}

例：圖8"

-------<2)(vi>--------(^2)

/V：無序?qū)?Vi，Vj)：

/<用連接頂點(diǎn)v「Vj的線段

?/■表示，稱為無向邊；

WWW----W.

(a)有向圖Gi(b)無向圖G2

圖8.1(b)表示的是無向圖G2，該圖的頂點(diǎn)集和

邊集分別為：

V(G2)={vrv2,v3,v4,v5}

E(G2)={(v(,v2),(v1,v3),(v1,v4),

(v2,v3),(v2,v5),(v4,v5)}

在以后的討論中，我們約定：

(1)一條邊中涉及的兩個(gè)頂點(diǎn)必須不相同,即：

若(Vj,Vj)或vv「』＞是E(G)中的一條邊，則要

求中Vj；

(2)一'對(duì)頂點(diǎn)間不能有相同方向的兩條有向邊；

(3)一對(duì)頂點(diǎn)間不能有兩條無向邊，即只討論簡(jiǎn)

單的圖。

二、完全圖

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

數(shù)目，按照上述規(guī)定，容易得到下述結(jié)論：對(duì)于一

個(gè)具有n個(gè)頂點(diǎn)的無向圖，其邊數(shù)e小于等于n(n-1)

/2,邊數(shù)恰好等于n(n-1)/2的無向圖稱為無向完

全圖；對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的有向圖，其邊數(shù)e小

于等于n(n-1),邊數(shù)恰好等于n(n-1)的有向圖

稱為有向完全圖。也就是說完全圖具有最多的邊數(shù)，

任意一對(duì)頂點(diǎn)間均有邊相連。

例：圖8?2

(a)無向完全圖G3(b)有向完全圖G4

圖8.2所示的G3與分別是具有4個(gè)頂點(diǎn)的無向

完全圖和有向完全圖。圖G3共有4個(gè)頂點(diǎn)6條邊；圖

共有4個(gè)頂點(diǎn)12條邊。

若“，Vj)是一條無向邊，則稱頂點(diǎn)Vj和Vj互為

鄰接點(diǎn)。

若VVj,'＞是一條有向邊，則稱Vj鄰接到Vj,￥口

接于Vj,并寐有向邊VVj,Vj＞關(guān)聯(lián)于Vj與v『或稱看向

邊VVj,Vj＞與頂點(diǎn)Vj和Vj相美聯(lián)。

三、度、入度、出度

在圖中，一個(gè)頂點(diǎn)的度就是與該頂點(diǎn)相關(guān)聯(lián)的

邊的數(shù)目，頂點(diǎn)v的度記為D(v)。例如在圖8.2

(a)所示的無向圖G3中，各頂點(diǎn)的度均為3。

若G為有向圖，則把以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目

稱為頂點(diǎn)v的入度，記為ID(v);把以頂點(diǎn)v為始

點(diǎn)的邊的數(shù)目稱為v的出度，記為OD(v),有向

圖中頂點(diǎn)的度數(shù)等于頂點(diǎn)的入度與出度之和，即D

(v)=ID(v)+0D(v)0

無論有向圖還是無向圖，圖中的每條邊均關(guān)聯(lián)于兩

個(gè)頂點(diǎn)，因此，頂點(diǎn)數(shù)n、邊數(shù)e和度數(shù)之間有如下

關(guān)系：

（式8-1）

四、子圖

給定兩個(gè)圖Gj和G『其中G產(chǎn)(M，EJ，Gp

(V『EJ,若滿足則稱Gj是Gj的

子團(tuán)。

子圖示例

(b)有向圖G4的部分子圖

五、路徑

無向圖G中若存在著一個(gè)頂點(diǎn)序列v、v；、V；、???、

55

vm\U,且(V,V；)、(V。v2)、…、(vm,U)

均屬于E(G),則稱該頂點(diǎn)序列為頂點(diǎn)v到頂點(diǎn)u的

一條路徑，相應(yīng)地，頂點(diǎn)序列II、vm\Vm」'、??.、v；、

V是頂點(diǎn)U到頂點(diǎn)V的一條路徑。

如果G是有向圖?路徑也是有向的，它由E(G)

J

中的有向邊vv,v；＞、＜v/,vg＞、....＜vm,u＞組

成。路徑長(zhǎng)度是該路徑上邊或弧的數(shù)目。

如果一條路徑上除了起點(diǎn)V和終點(diǎn)U相同外，其余

頂點(diǎn)均不相同，則稱此路徑為一條簡(jiǎn)單路徑。起點(diǎn)和

終點(diǎn)相同(v=u)的簡(jiǎn)單路徑稱為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。

六、連通圖與強(qiáng)連通圖

在無向圖G中，若從頂點(diǎn)寸到頂點(diǎn)Vj有路徑，貝U

稱』與凡是連通的。若V(G)中任意兩人不同的頂

點(diǎn)看和區(qū)都連通(即有路徑)，則稱G為連通圖。例

如，圖8.1(b)所示的無向圖G2、圖8.2(a)所示

的無向圖G3是都是連通圖。

無向圖G的極大連通子圖稱為G的連通分量。

根據(jù)連通分量的定義，可知任何連通圖的連通分量

是其自身，非連通的無向圖有多個(gè)連通分量。

例：非連通圖及其連通分量示例

????

(a)非連通圖(b)O。的兩個(gè)連通分量H1I和H2/

在有向圖G中，若對(duì)于V(G)中任意兩個(gè)不同的

頂點(diǎn)Vj和V『都存在從Vj到Vj以及從Vj到Vj的路徑，則稱

G是強(qiáng)連通圖。

有向圖的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。

根據(jù)強(qiáng)連通圖的定義，可知強(qiáng)連通圖的唯一強(qiáng)連通

分量是其自身，而非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連分

量。例如，圖8.2(b)所示的有向圖G4是一個(gè)具有

4個(gè)頂點(diǎn)的強(qiáng)連通圖，圖8.5(a)所示的有向圖Ge

不是強(qiáng)連通圖(V2、V3.V4沒有到達(dá)的路徑)，

它的兩個(gè)強(qiáng)連通分量與如圖所示。

O4+8.5(b)

(a)非強(qiáng)連通圖Ge(b)G6的兩個(gè)強(qiáng)連通分量H3和H4

七、網(wǎng)絡(luò)

有時(shí)在圖的每條邊上附上相關(guān)的數(shù)值，這種與

圖的邊相關(guān)的數(shù)值叫權(quán)。

權(quán)可以表示兩個(gè)頂點(diǎn)之間的距離、耗費(fèi)等具有

某種意義的數(shù)。若將圖的每條邊都賦上一個(gè)權(quán)，則

稱這種帶權(quán)圖為網(wǎng)絡(luò)。

(a)無向網(wǎng)絡(luò)G7(b)有向網(wǎng)絡(luò)Gg

作業(yè)：

8.1對(duì)于無向圖8.29,試給出

(1)圖中每個(gè)頂點(diǎn)的度；

(2)該圖的鄰接矩陣；

(4)該圖的連通分量。

圖8.29無向圖

8.2給定有向圖&30,試給出

(1)頂點(diǎn)D的入度與出度；

(2)該圖的出邊表與入邊表；

(3)該圖的強(qiáng)連通分量。

圖8.30有向圖

8.2圖的基本運(yùn)算

圖是一種復(fù)雜數(shù)據(jù)結(jié)構(gòu)，由圖的定義及圖的一組基

本操作構(gòu)成了圖的抽象數(shù)據(jù)類型。

ADTGraph{

數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱

為頂點(diǎn)集。

數(shù)據(jù)關(guān)系R:

R={<v,w>|v,weVJLP(v,w),P(v,w)定義

了邊(或弧)(v,w)的信息}

圖的基本操作如下:

(1)creatgraph(&g)創(chuàng)建一個(gè)圖的存儲(chǔ)結(jié)構(gòu)。

(2)insertvertex(&g,v)在圖g中增加一個(gè)頂

占v

八、、VO

(3)deletevertex(&g,v)在圖g中刪除頂點(diǎn)v及

所有和頂點(diǎn)v相關(guān)聯(lián)的邊或弧。

(4)insertedge(&g,v,u)在圖g中增加一條從

頂點(diǎn)v到頂點(diǎn)u的邊或弧。

(5)deleteedge(&g,v,u)在圖g中刪除一■條從

頂點(diǎn)v到頂點(diǎn)u的邊或弧。

(6)trave(g)遍歷圖g。

(7)locatevertex(g,v)求頂點(diǎn)v在圖g中的位

序。

(8)fiirstvertex(g,v)求圖g中頂點(diǎn)v的第一個(gè)

鄰接點(diǎn)。

(9)degree(g,v)求圖g中頂點(diǎn)v的度數(shù)。

(10)nextvertex(g,v,w)求圖g中與頂點(diǎn)v相

鄰接的頂點(diǎn)w的下一個(gè)鄰接點(diǎn)。即求圖g中頂點(diǎn)v的

某個(gè)鄰接點(diǎn),它的存儲(chǔ)順序排在鄰接點(diǎn)w的存儲(chǔ)位

置之后。

}ADTGraph

8.3圖的基本存儲(chǔ)結(jié)構(gòu)

831鄰接矩陣及其實(shí)現(xiàn)

一、非網(wǎng)絡(luò)的鄰接矩陣

給定圖G=(V,E),其中V(G)={v0,

vi?Vn_J,G的鄰接矩陣(AdacencyMatrix)是

具有如下在質(zhì)的n階方陣：

「1,女口果或者

A團(tuán)力=<

［。，否則

無向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩

陣可能是不對(duì)稱的。

圖的鄰接矩陣示例

r0111、

1010

A1=A2=

1101

i1010;

圖8.7無向圖G9及有向圖Gw的鄰接矩陣表示

用鄰接矩陣表示圖，很容易判定任意兩個(gè)頂點(diǎn)

之間是否有邊相連，并求得各個(gè)頂點(diǎn)的度數(shù)。對(duì)于

無向圖，頂點(diǎn)V的度數(shù)是鄰接矩陣中第i行或第i列值

為1的元素個(gè)數(shù)，即：

D(Vj)=區(qū)4區(qū)力=區(qū)4，口…(8-2)

7=07=0

對(duì)于有向圖，鄰接矩陣中第i行值為1的元素個(gè)

數(shù)為頂點(diǎn)Y的出度，第i列值為1的元素的個(gè)數(shù)為頂

點(diǎn)Vj的入度，即：

77—177—1

0D(vj=24，?，力；ID(Vj)=》4力］.?.(8-3)

7=°7=0

二、網(wǎng)絡(luò)的鄰接矩陣

當(dāng)G=(V,E)是一個(gè)網(wǎng)絡(luò)時(shí)，G的鄰接矩陣是具

有如下性質(zhì)的n階方陣：

rWy當(dāng)(v〃vj或〈吊，Vj>eE(G)

A[i,j尸<0當(dāng)(％,vj或vy,>E(G)JLi=j

00

、當(dāng)(Vj)或vvj9Vj>E(G)JLiWj

其中TV。表示邊上的權(quán)值；°°表示一個(gè)計(jì)算機(jī)允

許的、大于所有邊上權(quán)值的數(shù)。

網(wǎng)絡(luò)的鄰接矩陣示例

r0563478

0OO501

560OOOO

0OO45

34OO025

l64OO0)

I78OO250j

(a)G7的鄰接矩陣(b)G&的鄰接矩陣

圖8.8網(wǎng)絡(luò)鄰接矩陣示例

鄰接矩陣存儲(chǔ)結(jié)構(gòu)

文件名:mgraph.h

#defineFINITY5000/*此處用5000代表無窮大*/

#definem20/*最大頂點(diǎn)數(shù)*/

typedefcharvertextype;/*頂點(diǎn)值類型*/

typedefintedgetype;/*權(quán)值類型*/

typedefstruct{

vertextypevexs[m];/*頂點(diǎn)信息域*/

edgetypeedges[m][m];/*鄰接矩陣*/

intn,e;/*圖中頂點(diǎn)總數(shù)與邊數(shù)7

}mgraph;/*鄰接矩陣表示的圖類型*/

/*********************************************************/

/*圖的鄰接矩陣創(chuàng)建算法*/

/*文件名：cjjjz.c函數(shù)名：creatmgraph1()*/

/*********************************************************/

#include<stdio.h>

#include"mgraph.h1'

voidcreatmgraph1(mgraph*g)

{inti,j,k,w;/*建立有向網(wǎng)絡(luò)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)*/

printf(npleaseinputnande:\n");

scanf(,'%d%d,',&g->n,&g->e);/*輸入圖的頂點(diǎn)數(shù)與邊數(shù)*/

getchar();/*取消輸入的換行符7

printf(Hpleaseinputvexs:\n");

for(i=0;i<g->n;i++)/*輸入圖中的頂點(diǎn)值*/

g->vexs[i]=getchar();

for(i=0;i<g->n;i++)/*初始化鄰接矩陣*/

for(j=0;j<g->n;j++)

if(i==j)g->edges[i]0]=O;

elseg->edges[i]O]=FINITY;

printf(npleaseinputedges:\n");

for(k=0;k<g->e;k++)/*輸入網(wǎng)絡(luò)中的邊*/

{scanf(H%d%d%d",&i,&j,&w);

g->edges[i]O]=w;

/*若是建立無向網(wǎng)，只需在此力口入語句g->edges皿i]=w;即可*/

說明:

A當(dāng)建立有向網(wǎng)時(shí)，邊信息以三元組（i,j,w）的形

式輸入，i、j分別表示兩頂點(diǎn)的序號(hào)，w表示邊上的權(quán)。

對(duì)于每一條:俞人的邊信息（i,j,w）,只需將g?

>edges[i][j]賦值為w。

A算法8.5中用到的creatmgraph2（）是用于建立無向網(wǎng)

絡(luò)的函數(shù)，它與creatmgraph1（）向區(qū)別足于對(duì)每一條

輸入的邊信息（i,j,w）,需自時(shí)將g->edges[i][j]和

g->edges[j][i]賦值為w。

?當(dāng)建立非網(wǎng)絡(luò)的存儲(chǔ)結(jié)構(gòu)時(shí)，所有的邊信息只需按

二元組（i,j）的形式輸入。

832鄰接表及其實(shí)現(xiàn)

用鄰接矩陣表示法存儲(chǔ)圖，占用的存儲(chǔ)單元個(gè)

數(shù)只與圖中頂點(diǎn)的個(gè)數(shù)有關(guān)，而與邊的數(shù)目無關(guān)。

一個(gè)含有n個(gè)頂點(diǎn)的圖,如果其邊數(shù)比rP少得多,

那么它的鄰接矩陣就會(huì)有很多空元素，浪費(fèi)了存儲(chǔ)

空間。

■無向圖的鄰接表

對(duì)于圖G中的每個(gè)頂點(diǎn)看,該方法把所有鄰接于Y

的頂點(diǎn)』鏈成一個(gè)帶頭結(jié)點(diǎn)的單鏈表，這個(gè)單鏈表就

稱為頂上』的鄰接表。單鏈表中的每個(gè)結(jié)點(diǎn)至少包含

兩個(gè)域，一個(gè)為鄰接點(diǎn)域（adjvex），它指示與頂點(diǎn)看

鄰接的頂點(diǎn)在圖中的位序，另一個(gè)為鏈域（next），

它指示與頂點(diǎn)Y鄰接的下一個(gè)結(jié)點(diǎn)。

在無向圖的鄰接表中，頂點(diǎn)Vj的度為第i個(gè)鏈表中

結(jié)點(diǎn)的個(gè)數(shù)；而在有向圖的出邊表中，第i個(gè)鏈表中

的結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)寸的出度；為了求入度，必須對(duì)整

個(gè)鄰接表掃描一遍，所有鏈表中其鄰接點(diǎn)域的值為i

Gm的出邊表

鄰接表的存儲(chǔ)結(jié)構(gòu)

/****************************************************I

/*鄰接表存儲(chǔ)結(jié)構(gòu)文件名：adjgraph.h*/

/****************************************************!

#definem20/*預(yù)定義圖的最大頂點(diǎn)數(shù)7

typedefchardatatype;/*頂點(diǎn)信息數(shù)據(jù)類型*/

typedefstructnode{

intadjvex;

structnode*next;

}edgenode;

typedefstructvnode{/*頭結(jié)點(diǎn)類型*/

datatypevertex;/*頂點(diǎn)信息*/

edgenode*firstedge;/*鄰接鏈表頭指針*/

Jvertexnode;

typedefstruct{/*鄰接表類型*/

vertexnodeadjlist[m];/*存放頭結(jié)點(diǎn)的順序表7

intn,e;/*圖的頂點(diǎn)數(shù)與邊數(shù)*/

Jadjgraph;

/********************************************************/

/*無向圖的鄰接表創(chuàng)建算法*/

/*文件名jljb.c函數(shù)名：createadjgraph()*/

/********************************************************/

voidcreateadjgraph(adjgraph*g)

{int

edgenode*s;

printf(nPleaseinputnande:\nn);

,

scanf("%d%d',&g->nJ&g->e);/*輸入頂點(diǎn)數(shù)與邊數(shù)*/

getchar();

printf(HPleaseinput%dvertex:n,g->n);

for(i=0;i<g->n;i++)

{scanf(tt%c,,,&g->adjlist[i].vertex);/*讀入頂點(diǎn)信息7

g->adjlist[i].firstedge=NULL;/*邊表置為空表7

)

printf("Pleaseinput%dedges:",g->e);

for(k=0;k<g->e;k++)/*循環(huán)e次建立邊表*/

{scanf("%d%d,',&i,&j);/*輸入無序?qū)?i,j)*/

s=(edgenode*)malloc(sizeof(edgenode));

s->adjvex=j;/*鄰接點(diǎn)序號(hào)為j*/

s->next=g->adjlist[i].firstedge;

g->adjlist[i].firstedge=s;/*將新結(jié)點(diǎn)*s插入頂點(diǎn)y

的邊表頭部*/

s=(edgenode*)malloc(sizeof(edgenode));

s->adjvex=i;/*鄰接點(diǎn)序號(hào)為i*/

s->next=g->adjlist[j].firstedge;

g->adjlist[j].firstedge=s;

/*將新結(jié)點(diǎn)*s插入頂點(diǎn)用的邊表頭部7

)

)

算法8.2建立無向圖的鄰接表算法

說明：一個(gè)圖的鄰接矩陣表示是唯一的，但其鄰接表

表示不唯一，這是因?yàn)樵卩徑颖斫Y(jié)構(gòu)中，各邊表結(jié)點(diǎn)

的鏈接次序取決于建立鄰接表的算法以及邊的輸入次

序。

例：若需建立下圖所示的無向圖鄰接表存儲(chǔ)結(jié)構(gòu),則

在執(zhí)行程序jljb.c時(shí)如果輸入的信息為：

45

ABCD

0102031223

則將建立如下的鄰接表存儲(chǔ)結(jié)構(gòu)。

A3-->2-->1

B2->0

C3-->1-->0

D2->0

8.3.3鄰接多重表

■在鄰接多重表中，每一條邊只有一個(gè)邊結(jié)點(diǎn)。為有關(guān)

邊的處理提供了方便。

一邊結(jié)點(diǎn)的結(jié)構(gòu)

markvexzlink：veXf\inkj

其中，mark是記錄是否處理過的標(biāo)記；vexi和

vexj是依附于該邊的兩頂點(diǎn)位置。Iniki域是鏈接指針,

指向下一條依附于頂點(diǎn)vexi的邊；Iinkj也是鏈接指針,

指向下一條依附于頂點(diǎn)vexj的邊。需要時(shí)還可設(shè)置一

個(gè)存放與該邊相關(guān)的權(quán)值的域COSto

-頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)

vertexFirstedge

存儲(chǔ)頂點(diǎn)信息的結(jié)點(diǎn)表以順序表方式組織，每

一個(gè)頂點(diǎn)結(jié)點(diǎn)有兩個(gè)數(shù)據(jù)成員：其中，vertex存放

與該頂點(diǎn)相關(guān)的信息，firstedge是指示第一條依

附于該頂點(diǎn)的邊的指針。

在鄰接多重表中，所有依附于同一個(gè)頂點(diǎn)的邊

都鏈接在同一個(gè)單鏈表中。

從頂點(diǎn)i出發(fā)，可以循鏈找到所有依附于該頂

點(diǎn)的邊，也可以找到它的所有鄰接頂點(diǎn)。

無向網(wǎng)絡(luò)的鄰接多重表示例

其中邊表結(jié)點(diǎn)增加了一個(gè)存儲(chǔ)權(quán)值的數(shù)據(jù)域。

8.4圖的遍歷

圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問圖中所有頂點(diǎn),

并且每個(gè)頂點(diǎn)僅訪問一欠―在風(fēng)夾部分頂點(diǎn)后，

口圖的遍歷與呆證每

上一般

一個(gè)頂點(diǎn)只被訪問七述）■的遍歷有什么不匹）

用一個(gè)輔助數(shù)組為謫京衛(wèi)前;

visiJnMFT當(dāng)頂點(diǎn)vi未

被訪問,visit。］僅為0;°當(dāng)M已被訪問,則visit。］值為1。

有兩種遍歷方法（它們對(duì)無向圖，有向圖都適用）

>深度優(yōu)先遍歷

>廣度優(yōu)先遍歷

841深度優(yōu)先遍歷

從圖辯萊頌京婢度G=(V,E),首先將V中每一個(gè)頂

桿幅福靛喊z被訪問，然后，選取一個(gè)源點(diǎn)VEV,將v

標(biāo)記為，已破法泡

次撥宗v的叩有鄰祛點(diǎn)w:若w不等歷同過督7一則則似以加為

盛的春夏蜃繼續(xù)進(jìn)行深度優(yōu)先遍歷，如果從v出發(fā)有

路的頂點(diǎn)都已被訪問過，則從v的搜索過程結(jié)束。此

時(shí)，如果圖中還有未被訪問過的頂點(diǎn)(該圖有多個(gè)連

通分量或強(qiáng)連通分量)，則再任選一個(gè)未被訪問過的

頂點(diǎn)，并從這個(gè)頂點(diǎn)開始做新的搜索。上述過程一直

進(jìn)行到V中所有頂點(diǎn)都已被訪問過為止。

例

深度優(yōu)先遍歷過程:

序列1：?

V0,V1,V3,V7,V4,V2,V5,V6

V7

由于沒有規(guī)定

訪問鄰接點(diǎn)的順序，

深度優(yōu)先序列不是唯一的

序列2：

V0,V1,V4,V7,V3,V2,V5,V6

但是，當(dāng)采用鄰接表存儲(chǔ)結(jié)構(gòu)并且存儲(chǔ)結(jié)構(gòu)已確

定的情況下,遍歷的結(jié)果將是確定的O

:CQ->c1->C3->C4-,C5->c?

采用鄰接表存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先遍歷算法實(shí)現(xiàn)：

/*********************************************************/

/*圖的深度優(yōu)先遍歷算法*/

/*文件名：dfs.c函數(shù)名：dfs()、dfstraverse。*/

/*********************************************************/

intvisited[m];

voiddfs(adjgraphg,inti)

{/*以％為出發(fā)點(diǎn)深度優(yōu)先遍歷頂點(diǎn)看所在的連通分量*/

edgenode*p;

printf("visitvertex:%c\n”,g.adjlist[i].vertex);/*訪問頂點(diǎn)i*/

visited[i]=1;

p=g.adjlist[i].firstedge;

while(p)/*從p的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索*/

{if(!visited[p->adjvex])

dfs(g,p->adjvex);/*遞歸*/

p=p->next;

)

)

voiddfstraverse(adjgraphg)

{/*深度優(yōu)先遍歷圖g7

inti;

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

visited[i]=O;/*初始化標(biāo)志數(shù)組*/

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

if(!visited[i])/*%未訪問過*/

dfs(g,i);

)

算法8.3圖的深度優(yōu)先遍歷算法（鄰接表表示法）

算法分析：

對(duì)于具有n個(gè)頂點(diǎn)和e條邊的無向圖或有向圖，遍

歷算法dfstraverse對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次dfs。

從dfstraverse中調(diào)用dfs或dfs內(nèi)部遞歸調(diào)用自己的最

大次數(shù)為no當(dāng)訪問某頂點(diǎn)v時(shí)，dfs的時(shí)間主要耗費(fèi)

在從該頂點(diǎn)出發(fā)搜索它的所有鄰接點(diǎn)上。用鄰接表表

示圖時(shí)，需搜索第i個(gè)邊表上的所有結(jié)點(diǎn)，因此，對(duì)所

有n個(gè)頂點(diǎn)訪問，在鄰接表上需將邊表中所有0(e)

個(gè)結(jié)點(diǎn)檢查一遍。所以，dfstraverse算法的時(shí)間復(fù)雜

度為O(n+e)o

842廣度優(yōu)先遍歷

圖中某未訪問過的頂點(diǎn)M出發(fā)：

1）訪問頂點(diǎn)、M；

2）訪問Vj的所有未被訪問的鄰接點(diǎn)叫,w2,...wk;

3）依次從這些鄰接點(diǎn)出發(fā)，訪問它們的所有未被訪問

的鄰接點(diǎn);依此類推，直到圖中所有訪問過的頂點(diǎn)的

鄰接點(diǎn)都被訪問；

求圖G的以Vo起點(diǎn)的的廣度??

優(yōu)先序列....

V0,V1,V2,V3,V4,V5,V6,V7?

c

從Co出發(fā)的BFS序列為:

cc

CQ—>C1一>C2—>C3—>一>

c

cc

由于沒有規(guī)定

訪問鄰接點(diǎn)的順序，

廣度優(yōu)先序列不是唯一的

廣度優(yōu)先算法：

從圖中某頂點(diǎn)vi出發(fā)：

1）訪問頂點(diǎn)vi;（容易實(shí)現(xiàn)）

2）訪問vi的所有未被訪問的鄰接點(diǎn),w2,...wk;

3）依次從這些鄰接點(diǎn)（在步驟2）訪問的頂點(diǎn)）出

發(fā)，訪問它們的所有未被訪問的鄰接點(diǎn);依此類推，

直到圖中所有訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問；

為實(shí)現(xiàn)3）,需要保存在步騁。、出公間的頂點(diǎn)，而

且訪問這些頂點(diǎn)鄰》在廣度優(yōu)先遍歷算法中，

其鄰接點(diǎn)先被說需設(shè)置一隊(duì)列Q,

保存已訪問的頂點(diǎn)，

并控制遍歷頂點(diǎn)的順序。

QUEUE

數(shù)據(jù)結(jié)構(gòu)：

1）全局標(biāo)志數(shù)組

intvisited[m];/*全局標(biāo)志向量*/

2）鄰接表存儲(chǔ)結(jié)構(gòu)

/******************************************************/

/*圖的廣度優(yōu)先遍歷算法7

/*程序名bfs.c函數(shù)名bfs()、bfstraverse()*/

/******************************************************/

voidbfs(adjgraphg,inti)

{intj;/*從頂點(diǎn)i出發(fā)廣度優(yōu)先遍歷頂點(diǎn)i所在的連通分量*/

edgenode*p;

intqueue[20],head,tail;"FIFO隊(duì)列*/

head=-1;tail=-1;/*初始化空隊(duì)列7

printf(”％c,',g.adjlist[i].vertex);/*訪問源點(diǎn)v*/

visited[i]=1;

queue[++tail]=i;/*被訪問結(jié)點(diǎn)進(jìn)隊(duì)*/

while(tail>head)/*當(dāng)隊(duì)列非空時(shí)，執(zhí)行下列循環(huán)體*/

{j=queue[++head];/*出隊(duì)*/

p=g.adjlistO].firstedge;

while(p)/*廣度優(yōu)先搜索鄰接表*/

{if(visited[p->adjvex]==O)

{printf(H%c",g.adjlist[p->adjvex].vertex);

queue[++tail]=p->adjvex;

visited[p->adjvex]=1;

)

p=p->next;

)

})

intbfstraverse(adjgraphg,datatypev)

{inti,count=0;/*廣度優(yōu)先遍歷圖g*/

for(i=0;i<g.n;i++)visited[i]=O;/*初始化標(biāo)志數(shù)組7

i=loc(g,v);/*尋找頂點(diǎn)v在鄰接表中的位序7

if(i!=-1)

{count++;/*連通分量個(gè)數(shù)加1*/

bfs(g,i);

)

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

if(!visited[i])/%未訪問過*/

{printf(”\n”);

count++;/*連通分量個(gè)數(shù)加1*/

bfs(g,i);/*從頂點(diǎn)i出發(fā)廣度優(yōu)先遍歷圖g*/

)

returncount;/*返回?zé)o向圖g中連通分量的個(gè)數(shù)7

算法8.4圖的廣度優(yōu)先遍歷算法(鄰接表表示法)

算法的時(shí)間復(fù)雜度與深度優(yōu)先算法相同O

作業(yè)：

8.4圖8.31是某個(gè)無向圖的鄰接表，請(qǐng)

(1)畫出此圖；

(2)寫出從頂點(diǎn)A開始的DFS遍歷結(jié)果。

(3)寫出從頂點(diǎn)A開始的BFS遍歷結(jié)果。

8.5生成樹與最小生成樹

對(duì)于一個(gè)無向的連通圖6=(V,E),設(shè)G'是

它的一個(gè)子圖，如果G，中包含了G中所有的頂點(diǎn)

(即V(G')=V(G))且G'是無回路的連通圖，

則稱G，為G一棵的生成樹。

深度優(yōu)先生成樹：按深度優(yōu)先遍歷生成的生成樹

廣度優(yōu)先生成樹：按廣度優(yōu)先遍歷生成的生成樹

有向圖的生成樹

851最小生成樹的定義

若有一個(gè)連通的無向圖G,有n個(gè)頂點(diǎn)，并且

它的邊是有權(quán)值的。在G上構(gòu)造生成樹G',使這n?1

條邊的權(quán)值之和在所有的生成樹中最小。

要在n個(gè)城市間建立交通

網(wǎng)，要考慮的問題如何在保

證n點(diǎn)連通的前題下最節(jié)省

經(jīng)費(fèi)？

上述問題即要使得生成樹各用(T)=W-

邊權(quán)值之各最小，即：

構(gòu)造最小生成樹的準(zhǔn)則：

A必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；

A必須使用且僅使用nT條邊來聯(lián)接網(wǎng)絡(luò)中的n個(gè)頂點(diǎn);

A不能使用產(chǎn)生回路的邊。

MST性質(zhì)：

假設(shè)G=（V,E）是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的

一個(gè)非空真子集，若（u,v）是滿足UEU,vwV.U的

邊（稱這種邊為兩棲邊）且（u,V）在所有的兩棲

邊中具有最小的權(quán)值（此時(shí)，稱（II,V）為最小兩

棲邊），則必存在一棵包含邊（u,V）的最小生成

樹。

必存在另一條邊（U：V'）,其中U'eU,V'eV

(Prim)算法和(Kruskal)算法是兩個(gè)利用MST性質(zhì)

構(gòu)造最小生成樹的算法。

8.5.2最小生成樹的普里姆算法

■普里姆算法的基本思想：

從連通網(wǎng)絡(luò)}中的某一頂點(diǎn)出

G={V,Eu0

發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(Uo,v),將

其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。

以后每一'步從一個(gè)頂點(diǎn)在U中，而另一'個(gè)頂點(diǎn)不

在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂

點(diǎn)加入到集合U中。如此繼續(xù)下去，直到網(wǎng)絡(luò)中的所

有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。

Prim算法的基本步驟如下：

(1)初始化:U={u。},TREE={}；

(2)如果U=V(G),則輸出最小生成樹T,并結(jié)

束算法；

(3)在所有兩棲邊中找一條權(quán)最小的邊(u,v)

(若候選兩棲邊中的最小邊不止一條，可任選其中

的一條)，將邊(u,v)加入到邊集TREE中，并將

頂點(diǎn)v并入集合U中。

(4)由于新頂點(diǎn)的加入，U的狀態(tài)發(fā)生變化，需要

對(duì)U與V-U之間的兩棲邊進(jìn)行調(diào)整。

(5)轉(zhuǎn)步驟(2)

5

10

(a)無向網(wǎng)(b)初始狀態(tài)(c)選取(A、B)(d)選取(B、D

(e)選取(B、F)(f)選取(B、C)(g)選取(E、F)

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

1、連通圖用鄰接矩陣net表示：

（Wjj當(dāng)（vi,vj）eE（G）且權(quán)為Wu

當(dāng)上可

edges[i][j]=10

OO否則

2、邊tree（生成樹）edgetree[n-l]

typedefstructedgedata

{intbeg,en;/*beg,en是結(jié)點(diǎn)序號(hào)*/

intlength;/*邊長(zhǎng)*/

}edge;

Prim算法構(gòu)造最小生成樹的過程

tree01234

Ibeg|00000

12345

〔length1012001500

(a)初始態(tài)K=0m=l

tree01234

IbegI00000

12345

〔length1012001500

(b)最小兩棲邊(0,1)K=0

bego__i__i__

en_____1__3__2__4__5

length1057156

(d)最小兩棲邊(L5K=2

tree01234

begI0I1I1I5FT"

en____1__3__5__42

length10561c)7

(e)最小兩棲邊(L2)N6：3

tree01234

begI0I1I1I1I5

en____1__3__5__24

length1056__710

(f)tree中存儲(chǔ)了最小生成樹的邊

算法關(guān)鍵一步：求第k條輕邊，將其加入tree中

1)求當(dāng)前最小兩棲邊及應(yīng)添加的點(diǎn)v

min=tree[k].length;

s=k;

for(j=k+1;j<=g.n-2;j++)

if(treeO].length<min)

{min=treeO].length;

s=j;

)

v=tree[s].en;/*入選頂點(diǎn)為v*/

2）通過交換，將當(dāng)前輕邊加入tree中

x=tree[s];tree[s]=tree[k];tree[k]=x;

3)調(diào)整各剩余點(diǎn)對(duì)應(yīng)的最小兩棲邊(由V力口入弓|起)

for(j=k+1;j<=g.n-2;j++)

{d=g.edges[v][tree[j].en];

if(d<treeO].length)

{tree[j].length=d;

treeO].beg=v;

)

}

算法總體控制：

1)初始化：建立初始入選點(diǎn)，并初始化生成樹邊

集tree。

for(v=1;v<=g.n-1;v++)

{tree[v-1].beg=0;/*此處從頂點(diǎn)v0開始求最小生成樹*/

tree[v-1].en=v;

tree[v-1].length=g.edges[0][v];

)

2)依次求當(dāng)前最小兩棲邊，并將其加入tree

for(k=0;k<=g.n-3;k++)執(zhí)彳亍關(guān)鍵一步

程序演示：prim.c

一般來講，

由于普里姆算法的時(shí)間復(fù)雜度為0（己），則適于

稠密圖。

853最小生成樹的克魯斯卡爾算法

Kruskal算法基本思想：

為使生成樹上邊的權(quán)值之和最小，顯然，其中

每一條邊的權(quán)值應(yīng)該盡可能地小?？唆斔箍査惴?/p>

的做法就是：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG,

然后從權(quán)值最小的邊開始，若它的添加不使SG中

產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直

至加上n-1條邊為止。

克魯斯卡爾算法需對(duì)e條邊按權(quán)值進(jìn)行排序，其時(shí)

間復(fù)雜度為O(eloge),則適于稀疏圖。

算法:

(1)初始化，TV={V。，％,...,vn}?TE={};

(2)如果TE具有n-1條邊，則輸出最小生成樹T,

并結(jié)束算法。

(3)在有序的E(G)邊表序列中，從當(dāng)前位置向

后尋找滿足下面條件的一條邊(U,V)：使得U在

一個(gè)連通分量上，V在另一個(gè)連通分量上，即(U,

v)是滿足此條件權(quán)值最小的邊，將其加入到T中，

合并U與V所點(diǎn)的兩個(gè)連通分量為一個(gè)連通分量。

(4)轉(zhuǎn)(2)

Kruskal算法動(dòng)態(tài)演示:

(a)無向網(wǎng)絡(luò)圖(b)最小生成樹求解過程

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

(a)

(d)(e)

/*********************************************/

/*kruskal求解最小生成樹算法*/

/*文件名kruskal.c函數(shù)名kruskal。7

/*********************************************/

voidkruskal(edgeadjlist[],edgetree[],intcnvx[],intn)

{intv=O,j,k;

forG=O;j<n;j++)

cnvx[j]=j;/*設(shè)置每一個(gè)頂點(diǎn)的連通分量*/

for(k=0;k<n-1;k++)/*樹中共有條邊7

{while(cnvx[adjlist[v].beg]==cnvx[adjlist[v].en])v++;

/*找到屬于兩個(gè)連通分量權(quán)最小的邊*/

tree[k]=adjlist[v];/*將邊v加入到生成樹中*/

for0=O;j<n;j++)/*兩個(gè)連通分量合并為一個(gè)連通分量7

if(cnvx[j]==cnvx[adjlist[v].en])

cnvx[j]=cnvx[adjlist[v].beg];

v++;

)

printf("最小生成樹是：\n");

for(j=O;j<n-1;j++)

printf(,,%3d%3d%6d\n',,tree0].beg,tree[j].en,tree[j].length);

}

算法8.6Kruskal求解最小生成樹

8.6最短路徑

問題的提出：

交通咨詢系統(tǒng)、通訊網(wǎng)、計(jì)算機(jī)網(wǎng)絡(luò)常要尋找兩結(jié)點(diǎn)

間最短路徑；

交通咨詢系統(tǒng)：A到B最短路徑；

計(jì)算機(jī)網(wǎng)絡(luò)：發(fā)送Email節(jié)省費(fèi)用A到B沿最短路徑

傳送；

路徑長(zhǎng)度：路徑上邊數(shù)

路徑上邊的權(quán)值之和

最短路徑：兩結(jié)點(diǎn)間權(quán)值之和最小的路徑；

始點(diǎn)最短路徑路徑長(zhǎng)度

10

如何求從某源點(diǎn)

到其余各點(diǎn)的最短路徑?

oO

本節(jié)介紹求最短路徑的兩個(gè)算法

A求從某個(gè)源點(diǎn)到其他各頂點(diǎn)的最短路徑(單源最短

路徑)。

?求每一對(duì)頂點(diǎn)之間的最短路徑。

861單源最短路徑

單源最短路徑問題是指：對(duì)于給定的有向網(wǎng)G=(V,

E),求源點(diǎn)V。到其它頂點(diǎn)的最短路徑。

Dijkstra提出了一個(gè)按路徑長(zhǎng)度遞增的順序逐步產(chǎn)生

最短路徑的方法，稱為Dijkstra算法。

Dijkstra算法的基本思想：

把圖中所有頂點(diǎn)分成兩組，第一組包括已確定最短

路徑的頂點(diǎn)，初始時(shí)只含有一個(gè)源點(diǎn)，記為集合S;

第二組包括尚未確定最短路徑的頂點(diǎn)，記為V-S。按

最短路徑長(zhǎng)度遞增的順序逐個(gè)把V?S中的頂點(diǎn)加到S中

去，直至從v0出發(fā)可以到達(dá)的所有頂點(diǎn)都包括到S中。

在這個(gè)過程中，總保持從V。到第一組（S）各頂點(diǎn)的

最短路徑都不大于從V。到第二組（V?S）的任何頂點(diǎn)的

最短路徑長(zhǎng)度，第二組的頂點(diǎn)對(duì)應(yīng)的距離值是從V。到

此頂點(diǎn)的只包括第一組（S）的頂點(diǎn)為中間頂點(diǎn)的最

短路徑長(zhǎng)度。對(duì)于S中任意一點(diǎn)j,V。到j(luò)的路徑長(zhǎng)度皆

小于V。到（V6）中任意一點(diǎn)的路徑長(zhǎng)度。

■引入一個(gè)輔助數(shù)組d［］。它的每一個(gè)分量d［i］表示當(dāng)前

找到的從源點(diǎn)V。到頂點(diǎn)Vj的最短路徑的長(zhǎng)版。初始狀

態(tài)：

-若從源點(diǎn)V。到頂點(diǎn)Vj有邊，貝［□為該邊上的權(quán)值

-若從源點(diǎn)v0到頂點(diǎn)y沒有邊，則d［i］為+ooo

■一般情況下，假設(shè)S是已求得的最短路徑的終點(diǎn)的集

合，則可證明：下一條最短路徑必然是從出發(fā)，中

間只經(jīng)過S中的頂點(diǎn)便可到達(dá)的那還頂點(diǎn)V-s

）的珞徑中的二條二...............................

■每茨求得二條最短路徑之后，其終點(diǎn)丫卜加入集合S,

然后對(duì)所有的MeV-S,修改其d［i］值。

Dijkstra算法可描述如下：

1)初始化：把圖中的所有頂點(diǎn)分成兩組；初始化源

點(diǎn)到各點(diǎn)的距離向量。

fS:已確定最短路徑的點(diǎn)集，初始S-{v};

<__0

Is":尚未確定最短路徑的點(diǎn)集，初始W-V(G)-V。;

d[j]—g.edges[v0][j],j=1,2,…,n-1;

//n為圖中頂點(diǎn)個(gè)數(shù)

2)求出S與5間的最短路徑，及相應(yīng)的點(diǎn)V

d[v]-min{d[i]},ieV(G)-S;

S-SU{v};

ss

3）由于v的加入，修改S中各結(jié)點(diǎn)與5中各點(diǎn)的最短

距離：

d[i]_min<d[i],d[v]+edges[v][i]},

對(duì)于每一個(gè)i￡V-S;

4）判斷：若S=V,則算法結(jié)束，否則轉(zhuǎn)2）o

Dijkstra算法中各輔助數(shù)組的變化

距離向量d路徑向量p

循環(huán)集合SV

012345012345

初始化僅｝—0004280000—1-100-1—1

1IAC120194280012T200T2

2{ACF150194253012-120552

；3(ACFB110194252912T20512

4{ACFBD130194252912-120512

5{ACFBDE140194252912T20512

如何從表中讀取源點(diǎn)0到終點(diǎn)v

的最短路徑？例如頂點(diǎn)A到D的最

短距離是d[3]=25,根據(jù)p[3]=5

一p[5]=2一p[2]=0,反過來排

列,得到路徑0,2,5,3（即A、C

、F、D）。

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

/***************************************************/

/*單源最短路徑算法文件名:dijkstra.c*1

/*函數(shù)名:spath_dij()、print_gpd()*/

/***************************************************/

includenc_ljjz.c"/*引入鄰接矩陣創(chuàng)建程序*/

typedefenum{FALSE,TRUE}boolean;"false為0,true為1*/

typedefintdist[m];/*距離向量類型*/

typedefintpath[m];/*路徑向量類型*/

voidspath_dij(mgraphg,intvO.pathp,distd)

{booleanfinal[m];

inti,kj,v,min,x;

/*第1步初始化集合S與距離向量d7

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

{final[v]=FALSE;

d[v]=g.edges[vO][v];

if(d[v]<FINITY&&d[v]!=0)p[v]=vO;elsep[v]=-1;

/*v無前驅(qū)*/

)

final[vO]=TRUE;d[v0]=0;/*初始時(shí)s中只有一個(gè)頂點(diǎn)7

/*第2步依次找出n?1個(gè)結(jié)點(diǎn)加入S中*/

for(i=1;i<g.n;i++)

{min=FINITY;

for(k=0;kvg.n;++k)/*找最小邊及對(duì)應(yīng)的入選頂點(diǎn)*/

if(!final[k]&&d[k]<min){v=k;min=d[k];}/*!final[k]表示k還

在V-S中*/

printf("\n%c—%d\n",g.vexs[v],min);/*輸出本次入

選的頂點(diǎn)及距離7

if(min==FINITY)return;

final[v]=TRUE;/*V力口入S*/

/*第3步修改S與V-S中各結(jié)點(diǎn)的距離7

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

if(!final[k]&&(min+g.edges[v][k]<d[k]))

{d[k]=min+g.edges[v][k];

P[k]=v；}

}/*endfor*/

voidprint_gpd(mgraphg,pathp,distd)

{/*輸出有向圖的最短路徑7

intst[20],i,pre,top=-1;/*定義棧st并初始化空棧7

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

{printf(”\nDistancd:%7d,path:1',d[i]);

st[++top]=i;

pre=p[i];/*從第i個(gè)頂點(diǎn)開始向前搜索最短路徑上的頂點(diǎn)*/

while(pre!=-1)

{st[++top]=pre;

pre=p[pre];}

while(top>0)

printf(,'%2d,',st[top-]);}}

voidmain()/*主程序7

{mgraphg;/*有向圖7

pathp;/*路徑向量*/

distd;/*最短路徑向量7

intvO;

creatmgraph1(&g);/*創(chuàng)建有向網(wǎng)的鄰接矩陣*/

print(g);/*輸出圖的鄰接矩陣7

printf(npleaseinputthesourcepointvO:1');

scanf(”％d”,&vO);/*輸入源點(diǎn)*/

spath_dij(g,vO,p,d);/*求vO至U其他各點(diǎn)的最短距離*/

print_gpd(g,pJd);/*輸出V0到其它各點(diǎn)的路徑信息及距離*/

862所有頂點(diǎn)對(duì)的最短路徑

■問題的提法：已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有

向圖，對(duì)每一對(duì)頂點(diǎn)viwvj,要求求出vi與vj之

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

解決這個(gè)問題顯然可以利用單源最短路徑算法，

具體做法是依次把有向網(wǎng)G中的每個(gè)頂點(diǎn)作為源點(diǎn)

,重復(fù)執(zhí)行Dijkstra算法n次，即靈行循環(huán)體：總的

時(shí)間復(fù)雜度為0(n3)。

for(v=0;v<g,n;v++)

(spath_dij(g,v,p,d);

prinjgpd(g,p，d);

下面將介紹用弗洛伊德(Floyd)算法來實(shí)現(xiàn)此功

能，時(shí)間復(fù)雜度仍為0(n3),但該方法比調(diào)用n次迪杰斯

特拉方法更直觀一'些。

2.弗洛伊德算法的基本思想

弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣

edges[N][N]來存儲(chǔ)帶權(quán)有向圖。算法的基本思想是：

設(shè)置一個(gè)NxN的矩陣A[N][N],其中除對(duì)角線的元

素都等于0外，其它元素的值表示頂點(diǎn)i到頂點(diǎn)j的

最短路徑長(zhǎng)度，運(yùn)算步驟為：

開始時(shí)，以任意兩個(gè)頂點(diǎn)之間的有向邊的權(quán)值作

為路徑長(zhǎng)度，沒有有向邊時(shí)，路徑長(zhǎng)度為巴此時(shí),A

[i]0]=edges[i]0],

以后逐步嘗試在原路徑中加入其它頂點(diǎn)作為中

間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來

的路徑長(zhǎng)度減少了，則以此新路徑代替原路徑，修

改矩陣元素。具體做法為：

第一步，讓所有邊上加入中間頂點(diǎn)0,取A[i]0]與

A[i][0]+A[0][j]中較小的值作的值.

第二步，讓所有邊上加入中間頂點(diǎn)1,取與

中較小的值，完成后得到…，如此

進(jìn)行下去，當(dāng)?shù)趎步完成后，得到,即為我們所

求結(jié)果,A表示頂點(diǎn)i到頂點(diǎn)j的最短距離。

因此，弗洛伊德算法可以描述為:

'A（-1）[i]|j]=edges[i]O]；"edges為圖的鄰接矩陣*/

<

<A（k+1）[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}

其中k=-1,1,2,...,n-2

下面給出Floyd的算法實(shí)現(xiàn)。

/*************************************************/

/*Floyd所有頂點(diǎn)對(duì)最短路徑算法7

/*文件名：floyd.c函數(shù)名：floyd1()*/

/*************************************************/

typedefintdist[m][m];/*距離向量*/

typedefintpath[m][m];/*路徑向量*/

voidfloyd1(mgraphg,pathp,distd)

{inti,j,k;

for(i=0;i<g.n;i++)/*初始化*/

for0=O;j<g.n;j++)

{d[i]0]=g-edges[i]0];

if(i!=j&&d[i]O]<FINITY)p[i]O]=i；elsep[i]0]=-1；

for(k=0;k<g.n;k++)/*遞推求解每一對(duì)頂點(diǎn)間的最短距離*/

{for(i=0;i<g.n;i++)

for0=O;j<g.n;j++)

if(d[i]0]>(d[i][k]+d[k]0]))

{d[i]0]=d[i][k]+d[k]0];

P[i]Ul=k；

)

)

算法8.8求網(wǎng)絡(luò)中每一對(duì)頂點(diǎn)之間的最短路徑

例

求下圖中所在頂點(diǎn)對(duì)之間的最短路徑。

rO1OO41

OO092

3508

0」

OOOO6

8.7拓?fù)渑判?/p>

一AOV網(wǎng)

有向無環(huán)圖：沒有回路的有向圖

應(yīng)用：工程流程、生產(chǎn)過程中各道工序的流程、程序

流程、課程的流程。

AOV網(wǎng)(activityonvertexnet)

用頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)的順序關(guān)系的有向圖

稱為AOV網(wǎng)。

某工程可分為7個(gè)子工程，若用頂點(diǎn)表示子工程(

也稱活動(dòng))，用弧表示子工程間的順序關(guān)系。工程流

程可用如下AOV網(wǎng)表示

二AOV網(wǎng)與拓?fù)渑判?/p>

A拓?fù)渑判?/p>

對(duì)工程問題，人們至少關(guān)心如下兩類問題：

1）工程能否順序進(jìn)行，即工程流程是否“合理”?

2）完成整項(xiàng)工程至少需要多少時(shí)間，哪些子工程是影臉

工程進(jìn)度的關(guān)鍵子工程？

為求解工程流程是否“合理”，通常用AOV網(wǎng)的

有向圖展示工程流程。

例1某工程可分為V。、Vv、2、、3、、4、、5、V67

個(gè)子工程，工程流程可用如下AOV網(wǎng)表示。其中頂點(diǎn)

:表示子工程（也稱活動(dòng)），?。罕硎咀庸こ涕g的

順序關(guān)系。

例課程流程圖

某校計(jì)算機(jī)專業(yè)課程流程可AOV網(wǎng)表示。其中頂點(diǎn):

表示課程（也稱