山東大學(xué)《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)05圖

實(shí)驗(yàn)五圖

一實(shí)驗(yàn)任務(wù)

1)圖的鄰接表存儲(chǔ)與遍歷

2)圖的最短路徑求解

二實(shí)驗(yàn)?zāi)康?/p>

1)圖的基本存儲(chǔ)方法。

2)掌握?qǐng)D的兩種搜索路徑的遍歷方法。

3)掌握?qǐng)D的有關(guān)應(yīng)用(最短路徑)。

三實(shí)驗(yàn)原理

1.圖

圖G由兩個(gè)集合組成：頂點(diǎn)(結(jié)點(diǎn))集合V和連接頂點(diǎn)的邊的集合E,集合

E由集合V中的不同的頂點(diǎn)對(duì)組成，通常記為6=(V,E)o圖是一種較線性表

和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中

任意兩個(gè)數(shù)據(jù)元素之間都可能有關(guān)。

圖的抽象數(shù)據(jù)類型定義如下：

ADTGraph/Digraph{

數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。

數(shù)據(jù)關(guān)系R：R={VR}

對(duì)于有向圖VR={<V<span>,w>|v,wiv且P(v,w),<V<span>,

w>表示從v到w的弧，

謂詞P(v,w)定義了弧<V<span>，w>的意義或

信息)

對(duì)于無(wú)向圖VR={(v,w)|v,wiv且P(v,w),(v,w)表示從v到w

的邊，謂詞P(v,w)定義了邊(v,w)

的意義或信息)

基本操作P：

CreateGraph(&G,V,VR)

返回結(jié)果：V是圖的頂點(diǎn)集，VR是圖中邊或弧集合。按V和VR的定

義構(gòu)造圖G。

DestoryGraph(&G)

初始條件：G是已經(jīng)存在的一個(gè)圖。

操作結(jié)果：銷毀圖G。

Exist(G,v,w)

初始條件：G是已經(jīng)存在的一個(gè)圖，v、w是兩個(gè)頂點(diǎn)。

操作結(jié)果：如果存在邊(v,w)或弧<V<span>，w>,則返回TRUE,

否則返回FALSEo

Edges(G)

初始條件：G是已經(jīng)存在的一個(gè)圖。

操作結(jié)果：返回圖中邊的數(shù)目。

Vertices(G)

初始條件：G是已經(jīng)存在的一個(gè)圖。

操作結(jié)果：返回圖中頂點(diǎn)的數(shù)目。

Add(&G,v,w)

初始條件：圖G已存在，v,w是兩個(gè)頂點(diǎn)。

操作結(jié)果：如果G是有向圖，則在G中添加一條弧<V<span>，w>；

如果G是無(wú)向圖，則在G中添加一條邊(v,w)o

Delete(&G,v,w)

初始條件：圖G已存在，v,w是兩個(gè)頂點(diǎn)。

操作結(jié)果：如果G是有向圖，則在G中刪除一條弧<V<span>,w>；

如果G是無(wú)向圖，則在G中刪除一條邊(v,w)o

Degree(G,v)

初始條件：圖G及頂點(diǎn)v已存在。

操作結(jié)果：返回圖G中頂點(diǎn)v的度。

Indegree(G,v)

初始條件：圖G及頂點(diǎn)v已存在。

操作結(jié)果：如果G是有向圖，則返回頂點(diǎn)v的入度；如果G是無(wú)向圖，

則返回圖G中頂點(diǎn)v的度。

Outdegree(G,v)

初始條件：圖G及頂點(diǎn)v已存在。

操作結(jié)果：如果G是有向圖，則返回頂點(diǎn)v的出度；如果G是無(wú)向圖，

則返回圖G中頂點(diǎn)v的度。

DFSTraverse(G,v,visit())

初始條件：圖G已存在，v是G中的某個(gè)頂點(diǎn)，visit是頂點(diǎn)的應(yīng)用函

數(shù)。

操作結(jié)果：從頂點(diǎn)v起深度優(yōu)先遍歷圖G,并對(duì)頂點(diǎn)調(diào)用函數(shù)visit一

次且僅一次。一旦visit失敗，則操作失敗。

BFSTraverse(G,v,visit())

初始條件：圖G已存在，v是G中的某個(gè)頂點(diǎn)，visit是頂點(diǎn)的應(yīng)用函

數(shù)。

操作結(jié)果：從頂點(diǎn)v起廣度優(yōu)先遍歷圖G,并對(duì)頂點(diǎn)調(diào)用函數(shù)visit一

次且僅一次。一旦visit失敗，則操作失敗。

}ADTGraph/Digraph

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

(1)鄰接矩陣

一個(gè)n個(gè)頂點(diǎn)的圖G=(V,E)的鄰接矩陣(AdjacencyMatrix)是一個(gè)nxn

矩陣AdjMatrix,AdjMatrix中的每個(gè)元素是0或1。假設(shè)圖G中頂點(diǎn)集合:V={1,

2,n},那么AdjMatrix中的元素定義如下：

AdjMatrix[i][j]=<i-[jf!vml]-><!--[endif]->

<!-[if!vml]-->

<!-[endif]->

圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述形式如下：

#defineINFINITYINT_MAX

#defineMAX_VERTEX_NUM20

typedefenum{DG=1,AG,DN,AN}GraphKind；〃{有向圖、無(wú)向圖;

有向網(wǎng)、無(wú)向

網(wǎng)}

typedefstructnode{

VertexTypevextex；〃頂點(diǎn)信息

}Node；

typedefstructarcs{

intadj；//頂點(diǎn)鄰接關(guān)系

...〃該邊或弧的相關(guān)信息指針

}Arcs;

typedefstruct{

Nodenodes[MAX_VERTEX_NUM]；〃頂點(diǎn)集合

Arcsarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃鄰接矩陣

intvexnum,arcnum；〃頂點(diǎn)數(shù)和弧數(shù)

GraphKindkind;

〃kind取值1、2、3、4分別表示有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向

網(wǎng)

}Graph;

（2）鄰接表

鄰接表（AdjacencyList）是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)結(jié)構(gòu)，

順序存儲(chǔ)部分用來(lái)保存圖中頂點(diǎn)信息，鏈?zhǔn)酱鎯?chǔ)部分保存圖中邊或弧的信息。具

體做法是：圖G被表示為一個(gè)數(shù)組或向量v[l],v[2],v[n],每個(gè)元素對(duì)應(yīng)

圖中一個(gè)頂點(diǎn)。每個(gè)v[□存儲(chǔ)頂點(diǎn)%的信息，以及一個(gè)指向包含所有依附于頂點(diǎn)

W的邊組成的單鏈表的指針，v[□稱之為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)結(jié)構(gòu)如下圖所示：

其中data存放與頂點(diǎn)相關(guān)的信息，firstarc是指針；鄰接單鏈表中每個(gè)結(jié)點(diǎn)表示

依附于該頂點(diǎn)的一條邊（對(duì)于有向圖則是以頂點(diǎn)w為尾的?。Q為邊（?。┙Y(jié)

點(diǎn)，其結(jié)構(gòu)如下圖所示：

其中adjvex存放依附于該邊的另一個(gè)頂點(diǎn)在一維數(shù)組中的序號(hào)，對(duì)于有向

圖，存放的是該弧結(jié)點(diǎn)所表示的弧的弧頭頂點(diǎn)在一維數(shù)組中的序號(hào)；nextarc為

指向下一條邊（或?。┙Y(jié)點(diǎn)的指針；inf。存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。

圖的鄰接表存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述形式如下：

#defineMAXLEN10

typedefstructnode{/*邊結(jié)點(diǎn)結(jié)構(gòu)*/

intadjvex;/*存放與頭結(jié)點(diǎn)相鄰接的頂點(diǎn)在數(shù)組中的

序號(hào)*/

intinfo;/*權(quán)值等信息*/

structnode*nextarc;/*指向與頭結(jié)點(diǎn)相鄰接下一個(gè)頂點(diǎn)的

表結(jié)點(diǎn)*/

}EdgeNode;

typedefstruct{/*頭結(jié)點(diǎn)結(jié)構(gòu)*/

intid;/*頂點(diǎn)入度*/

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

EdgeNode*firstarc;/*指向頭結(jié)點(diǎn)對(duì)應(yīng)的單鏈表中的表結(jié)

點(diǎn)*/

}VexNode;

typedefstruct{/*鄰接表結(jié)構(gòu)*/

VexNodeadjs[MAXLEN];/*鄰接表的頭結(jié)點(diǎn)集合*/

intvexnum,arcnum;/*頂點(diǎn)數(shù)，邊數(shù)*/

intkind;/*圖的種類*/

}AdjList;

3.圖的遍歷

圖有兩種搜索路徑的遍歷方法：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。

圖的深度優(yōu)先搜索(Depth-FirstSearch,DFS)策略是從給定頂點(diǎn)v出發(fā)，

在回溯之前，沿著從v出發(fā)的一條路徑盡可能深入前進(jìn)。其遍歷規(guī)則為：從v出

發(fā)，訪問(wèn)v的一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)wl,再?gòu)膚l出發(fā)，訪問(wèn)wl的一個(gè)未被

訪問(wèn)的鄰接頂點(diǎn)w2,然后從w2出發(fā)，訪問(wèn)w2的一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)w3,...,

如此下去，直到一個(gè)所有鄰接點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn)為止。然后回溯到尚有鄰接點(diǎn)

未被訪問(wèn)的頂點(diǎn)，重復(fù)上述過(guò)程，直到圖中所有與v有路徑相通的頂點(diǎn)都被訪問(wèn)

過(guò)；此時(shí)，若圖中還存在未被訪問(wèn)過(guò)的頂點(diǎn)，則從其中一個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)出

發(fā)，重復(fù)上述過(guò)程，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。

圖的廣度優(yōu)先搜索(Broad-FirstSearch,BFS)策略是在訪問(wèn)給定頂點(diǎn)v之

后，先訪問(wèn)與V鄰接的所有頂點(diǎn)Wl、W2、…、Wk，然后再依次從Wl、W2、…、

Wk出發(fā)，訪問(wèn)它們的未被訪問(wèn)過(guò)的鄰接頂點(diǎn)，重復(fù)上述操作，直到圖中所有被

訪問(wèn)過(guò)的頂點(diǎn)的鄰接頂點(diǎn)都被訪問(wèn)為止。若此時(shí)圖中還有未被訪問(wèn)過(guò)的頂點(diǎn)，則

從一個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，重復(fù)上述過(guò)程，直到圖中所有的頂點(diǎn)都被訪問(wèn)過(guò)

為止。

4.最短路徑

圖的最短路徑問(wèn)題有：一是求從一個(gè)頂點(diǎn)(源點(diǎn))到其它各頂點(diǎn)的最短路徑；

二是求每對(duì)頂點(diǎn)之間的最短路徑。第一種情況采用迪杰斯特拉算法解決，這是一

個(gè)按路徑長(zhǎng)度遞增的順序逐步產(chǎn)生最短路徑的算法。第二種情況采用Floyd算法

求解。

(1)Dijkstra算法的實(shí)現(xiàn)

設(shè)有向網(wǎng)G=(V,E),它采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)。若鄰接矩陣為Cost,

并規(guī)定：

'Wjj頂去點(diǎn)到頂點(diǎn)之間有直接邊，且權(quán)值為Wjj

Cost[i][j]=<0i=j,頂點(diǎn)i與頂點(diǎn)j是同一個(gè)頂點(diǎn)

8頂點(diǎn)i和頂點(diǎn)j之間沒(méi)有邊

設(shè)立兩個(gè)一維數(shù)組S和Distance,其中S存放已經(jīng)找到最短路徑的頂點(diǎn)，它的初

始狀態(tài)為：集合S中只含有起始頂點(diǎn)(源點(diǎn))。并規(guī)定：

.未找到源點(diǎn)到頂點(diǎn)看的最短路徑

SC，]=|1已經(jīng)找到源點(diǎn)到頂點(diǎn)v的最短路徑

Distance的每個(gè)分量Distance[口表示當(dāng)前所找到的從起始頂點(diǎn)v到每個(gè)目的頂點(diǎn)

W的最短路徑長(zhǎng)度。它的初始表態(tài)為：若從v到％有弧，則Distance。]為弧上的

權(quán)值，否則置Distance。]為8,即Distance。]=Cost[LocateVex（v）][i],LocateVex

用于確定頂點(diǎn)v在G中的位序。

利用Distance的各個(gè)分量的值，選取當(dāng)前具有的最短路徑的頂點(diǎn)垮，使得

Distance[j]=min{Distance[i]|vieV-S}

然后將頂點(diǎn)Vj加入集合S中，即令SU]=1,同時(shí)對(duì)于所有S[i]=0的頂點(diǎn)Vi,修

改源點(diǎn)到它們可達(dá)的最短路徑為

Distance[i]=min{Distance[i],Distance[j]+Cost[j][i]}

上述過(guò)程重復(fù)執(zhí)行n-1次，就可以得到源點(diǎn)到其它頂點(diǎn)的最短路徑值。

（2）Floyd算法的思想

假設(shè)求從頂點(diǎn)W到頂點(diǎn)垮的最短路徑。如果從頂點(diǎn)Vi到頂點(diǎn)Vj有弧，則從頂

點(diǎn)坐到頂點(diǎn)埼存在一條長(zhǎng)度為Cost[i][j]的路徑，該路徑不一定是最短路徑，尚

需進(jìn)行n次試探。首先考慮路徑（w,vo,vj）是否存在（即判斷弧（w,vo）和

（Vo，Vj）是否存在）。如果存在，則比較（Vi，Vo，Vj）和（Vi，Vj）的路徑長(zhǎng)度，

然后取長(zhǎng)度較短者為頂點(diǎn)Vi到頂點(diǎn)Vj的中間頂點(diǎn)的序號(hào)不大于0的最短路徑。

假如在路徑上再增加一個(gè)頂點(diǎn)V1,也就是說(shuō)，如果（Vi,…，VI）和（VI,...?

Vj）分別是當(dāng)前找到的中間頂點(diǎn)的序號(hào)不大于0的最短路徑，那么V1，

Vj）就有可能是從Vi到頂點(diǎn)Vj的中間頂點(diǎn)的序號(hào)不大于I的最短路徑。將它和已

經(jīng)得到的從Vi到頂點(diǎn)Vj的中間頂點(diǎn)序號(hào)不大于0的最短路徑相比較，從中選出

中間頂點(diǎn)的序號(hào)不大于1的最短路徑之后，再增加一個(gè)頂點(diǎn)V2,繼續(xù)進(jìn)行試探。

依次類推。在一般情況下，若（Vi,…，Vk）和（Vk,…，Vj）分別是從Vi到頂點(diǎn)

Vk和從Vk到頂點(diǎn)Vj的中間頂點(diǎn)的序號(hào)不大于k-l的最短路徑，則將（Vi,...,Vk,...,

Vj）和已經(jīng)得到的從vi到Vj且中間頂點(diǎn)序號(hào)不大于k-l的最短路徑相比較，其長(zhǎng)

度較短者便是從頂點(diǎn)Vi到頂點(diǎn)Vj的中間序號(hào)不大于k的最短路徑。這樣，在經(jīng)過(guò)

n次比較后，最后求得的必是從頂點(diǎn)％到頂點(diǎn)垮的最短路徑。按此方法，可以同

時(shí)求得各對(duì)頂點(diǎn)的最短路徑。

四實(shí)驗(yàn)設(shè)備、儀器、工具與資料

微機(jī)、VC

五實(shí)驗(yàn)內(nèi)容

（1）實(shí)驗(yàn)任務(wù)1：圖的遍歷

針對(duì)下圖所示的有向圖，編寫C程序完成如下功能：

1）建立有向圖的鄰接表

2）并在鄰接表存儲(chǔ)基礎(chǔ)上完成深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

V2

圖5-1有向圖

（2）實(shí)驗(yàn)任務(wù)2：求解圖的最短路徑

給出五個(gè)城市的交通圖如圖5-2所示，弧上數(shù)字表示城市之間的道路長(zhǎng)度。

現(xiàn)要在五個(gè)城市中選擇一個(gè)城市建造一個(gè)物流配送中心。問(wèn)這個(gè)物流配送中心應(yīng)

設(shè)在哪個(gè)城市到其他城市的路程之和最短？請(qǐng)編程解決這個(gè)問(wèn)題。