實驗五圖

一實驗任務

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

2)圖的最短路徑求解

二實驗目的

1)圖的基本存儲方法。

2)掌握圖的兩種搜索路徑的遍歷方法。

3)掌握圖的有關應用(最短路徑)。

三實驗原理

1.圖

圖G由兩個集合組成：頂點(結點)集合V和連接頂點的邊的集合E,集合

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

和樹更為復雜的數據結構。在圖形結構中，結點之間的關系可以是任意的，圖中

任意兩個數據元素之間都可能有關。

圖的抽象數據類型定義如下：

ADTGraph/Digraph{

數據對象V：V是具有相同特性的數據元素的集合，稱為頂點集。

數據關系R：R={VR}

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

w>表示從v到w的弧，

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

信息)

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

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

的意義或信息)

基本操作P：

CreateGraph(&G,V,VR)

返回結果：V是圖的頂點集，VR是圖中邊或弧集合。按V和VR的定

義構造圖G。

DestoryGraph(&G)

初始條件：G是已經存在的一個圖。

操作結果：銷毀圖G。

Exist(G,v,w)

初始條件：G是已經存在的一個圖，v、w是兩個頂點。

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

否則返回FALSEo

Edges(G)

初始條件：G是已經存在的一個圖。

操作結果：返回圖中邊的數目。

Vertices(G)

初始條件：G是已經存在的一個圖。

操作結果：返回圖中頂點的數目。

Add(&G,v,w)

初始條件：圖G已存在，v,w是兩個頂點。

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

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

Delete(&G,v,w)

初始條件：圖G已存在，v,w是兩個頂點。

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

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

Degree(G,v)

初始條件：圖G及頂點v已存在。

操作結果：返回圖G中頂點v的度。

Indegree(G,v)

初始條件：圖G及頂點v已存在。

操作結果：如果G是有向圖，則返回頂點v的入度；如果G是無向圖，

則返回圖G中頂點v的度。

Outdegree(G,v)

初始條件：圖G及頂點v已存在。

操作結果：如果G是有向圖，則返回頂點v的出度；如果G是無向圖，

則返回圖G中頂點v的度。

DFSTraverse(G,v,visit())

初始條件：圖G已存在，v是G中的某個頂點，visit是頂點的應用函

數。

操作結果：從頂點v起深度優先遍歷圖G,并對頂點調用函數visit一

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

BFSTraverse(G,v,visit())

初始條件：圖G已存在，v是G中的某個頂點，visit是頂點的應用函

數。

操作結果：從頂點v起廣度優先遍歷圖G,并對頂點調用函數visit一

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

}ADTGraph/Digraph

2.圖的存儲結構

(1)鄰接矩陣

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

矩陣AdjMatrix,AdjMatrix中的每個元素是0或1。假設圖G中頂點集合:V={1,

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

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

<!-[if!vml]-->

<!-[endif]->

圖的鄰接矩陣存儲結構的C語言描述形式如下：

#defineINFINITYINT_MAX

#defineMAX_VERTEX_NUM20

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

有向網、無向

網}

typedefstructnode{

VertexTypevextex；〃頂點信息

}Node；

typedefstructarcs{

intadj；//頂點鄰接關系

...〃該邊或弧的相關信息指針

}Arcs;

typedefstruct{

Nodenodes[MAX_VERTEX_NUM]；〃頂點集合

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

intvexnum,arcnum；〃頂點數和弧數

GraphKindkind;

〃kind取值1、2、3、4分別表示有向圖、無向圖、有向網、無向

網

}Graph;

（2）鄰接表

鄰接表（AdjacencyList）是一種順序存儲與鏈式存儲相結合的存儲結構，

順序存儲部分用來保存圖中頂點信息，鏈式存儲部分保存圖中邊或弧的信息。具

體做法是：圖G被表示為一個數組或向量v[l],v[2],v[n],每個元素對應

圖中一個頂點。每個v[□存儲頂點%的信息，以及一個指向包含所有依附于頂點

W的邊組成的單鏈表的指針，v[□稱之為頭結點。頭結點結構如下圖所示：

其中data存放與頂點相關的信息，firstarc是指針；鄰接單鏈表中每個結點表示

依附于該頂點的一條邊（對于有向圖則是以頂點w為尾的弧），稱為邊（弧）結

點，其結構如下圖所示：

其中adjvex存放依附于該邊的另一個頂點在一維數組中的序號，對于有向

圖，存放的是該弧結點所表示的弧的弧頭頂點在一維數組中的序號；nextarc為

指向下一條邊（或弧）結點的指針；inf。存儲和邊或弧相關的信息，如權值等。

圖的鄰接表存儲結構的C語言描述形式如下：

#defineMAXLEN10

typedefstructnode{/*邊結點結構*/

intadjvex;/*存放與頭結點相鄰接的頂點在數組中的

序號*/

intinfo;/*權值等信息*/

structnode*nextarc;/*指向與頭結點相鄰接下一個頂點的

表結點*/

}EdgeNode;

typedefstruct{/*頭結點結構*/

intid;/*頂點入度*/

chardata;/*頂點信息*/

EdgeNode*firstarc;/*指向頭結點對應的單鏈表中的表結

點*/

}VexNode;

typedefstruct{/*鄰接表結構*/

VexNodeadjs[MAXLEN];/*鄰接表的頭結點集合*/

intvexnum,arcnum;/*頂點數，邊數*/

intkind;/*圖的種類*/

}AdjList;

3.圖的遍歷

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

圖的深度優先搜索(Depth-FirstSearch,DFS)策略是從給定頂點v出發，

在回溯之前，沿著從v出發的一條路徑盡可能深入前進。其遍歷規則為：從v出

發，訪問v的一個未被訪問的鄰接頂點wl,再從wl出發，訪問wl的一個未被

訪問的鄰接頂點w2,然后從w2出發，訪問w2的一個未被訪問的鄰接頂點w3,...,

如此下去，直到一個所有鄰接點都被訪問過的頂點為止。然后回溯到尚有鄰接點

未被訪問的頂點，重復上述過程，直到圖中所有與v有路徑相通的頂點都被訪問

過；此時，若圖中還存在未被訪問過的頂點，則從其中一個未被訪問過的頂點出

發，重復上述過程，直到圖中所有頂點都被訪問為止。

圖的廣度優先搜索(Broad-FirstSearch,BFS)策略是在訪問給定頂點v之

后，先訪問與V鄰接的所有頂點Wl、W2、…、Wk，然后再依次從Wl、W2、…、

Wk出發，訪問它們的未被訪問過的鄰接頂點，重復上述操作，直到圖中所有被

訪問過的頂點的鄰接頂點都被訪問為止。若此時圖中還有未被訪問過的頂點，則

從一個未被訪問過的頂點出發，重復上述過程，直到圖中所有的頂點都被訪問過

為止。

4.最短路徑

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

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

個按路徑長度遞增的順序逐步產生最短路徑的算法。第二種情況采用Floyd算法

求解。

(1)Dijkstra算法的實現

設有向網G=(V,E),它采用鄰接矩陣作為存儲結構。若鄰接矩陣為Cost,

并規定：

'Wjj頂去點到頂點之間有直接邊，且權值為Wjj

Cost[i][j]=<0i=j,頂點i與頂點j是同一個頂點

8頂點i和頂點j之間沒有邊

設立兩個一維數組S和Distance,其中S存放已經找到最短路徑的頂點，它的初

始狀態為：集合S中只含有起始頂點(源點)。并規定：

.未找到源點到頂點看的最短路徑

SC，]=|1已經找到源點到頂點v的最短路徑

Distance的每個分量Distance[口表示當前所找到的從起始頂點v到每個目的頂點

W的最短路徑長度。它的初始表態為：若從v到％有弧，則Distance。]為弧上的

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

用于確定頂點v在G中的位序。

利用Distance的各個分量的值，選取當前具有的最短路徑的頂點垮，使得

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

然后將頂點Vj加入集合S中，即令SU]=1,同時對于所有S[i]=0的頂點Vi,修

改源點到它們可達的最短路徑為

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

上述過程重復執行n-1次，就可以得到源點到其它頂點的最短路徑值。

（2）Floyd算法的思想

假設求從頂點W到頂點垮的最短路徑。如果從頂點Vi到頂點Vj有弧，則從頂

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

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

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

然后取長度較短者為頂點Vi到頂點Vj的中間頂點的序號不大于0的最短路徑。

假如在路徑上再增加一個頂點V1,也就是說，如果（Vi,…，VI）和（VI,...?

Vj）分別是當前找到的中間頂點的序號不大于0的最短路徑，那么V1，

Vj）就有可能是從Vi到頂點Vj的中間頂點的序號不大于I的最短路徑。將它和已

經得到的從Vi到頂點Vj的中間頂點序號不大于0的最短路徑相比較，從中選出

中間頂點的序號不大于1的最短路徑之后，再增加一個頂點V2,繼續進行試探。

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

Vk和從Vk到頂點Vj的中間頂點的序號不大于k-l的最短路徑，則將（Vi,...,Vk,...,

Vj）和已經得到的從vi到Vj且中間頂點序號不大于k-l的最短路徑相比較，其長

度較短者便是從頂點Vi到頂點Vj的中間序號不大于k的最短路徑。這樣，在經過

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

時求得各對頂點的最短路徑。

四實驗設備、儀器、工具與資料

微機、VC

五實驗內容

（1）實驗任務1：圖的遍歷

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

1）建立有向圖的鄰接表

2）并在鄰接表存儲基礎上完成深度優先遍歷和廣度優先遍歷。

V2

圖5-1有向圖

（2）實驗任務2：求解圖的最短路徑

給出五個城市的交通圖如圖5-2所示，弧上數字表示城市之間的道路長度。

現要在五個城市中選擇一個城市建造一個物流配送中心。問這個物流配送中心應

設在哪個城市到其他城市的路程之和最短？請編程解決這個問題。