試驗(yàn)八圖論算法

1、實(shí)驗(yàn)八圖論算法現(xiàn)實(shí)生活中的諸多問題可以轉(zhuǎn)換為相應(yīng)的圖論問題，例如交通流、航空路線、 室內(nèi)線路布置等問題。圖由假設(shè)干個(gè)頂點(diǎn)和頂點(diǎn)之間的連接邊組成，一種簡(jiǎn)單方法是 使用鄰接矩陣來存儲(chǔ)圖，但是該方法通常會(huì)浪費(fèi)較多的存儲(chǔ)空間，因而標(biāo)準(zhǔn)的方法 是使用鄰接表來存儲(chǔ)圖。本實(shí)驗(yàn)實(shí)現(xiàn)圖和它的一些相關(guān)應(yīng)用。1. 實(shí)驗(yàn)?zāi)康腶掌握?qǐng)D的組織和存儲(chǔ)結(jié)構(gòu)；b掌握?qǐng)D的常用算法：創(chuàng)立頂點(diǎn)、創(chuàng)立邊、刪除邊、查找邊等；c掌握?qǐng)D的一些根本應(yīng)用。2. 實(shí)驗(yàn)內(nèi)容圖的實(shí)現(xiàn) 目標(biāo)：基于鄰接表結(jié)構(gòu)定義一個(gè)有向圖，并實(shí)現(xiàn)其常用算法。其中，圖中每個(gè)頂點(diǎn) 存放一個(gè)字符串?dāng)?shù)據(jù)，每條邊存放一個(gè)浮點(diǎn)型數(shù)據(jù)信息。一算法填空：根據(jù)功能提示，完善下劃線處的代碼

2、1圖數(shù)據(jù)類型的定義定義相應(yīng)的結(jié)構(gòu)體數(shù)據(jù)類型，用來表示圖中的相關(guān)數(shù)據(jù)對(duì)象#defi ne MAXVERTEXNUM 100 typedef struct adjVert /鄰接頂點(diǎn)數(shù)據(jù)類型 int adjvert; /鄰接頂點(diǎn)索引號(hào) float edge Info; /邊上的數(shù)據(jù)信息 struct adjVert *n ext; Graph_AdjVert;typedef struct vert / 頂點(diǎn)數(shù)據(jù)類型 char data128; / 頂點(diǎn)數(shù)據(jù) *pHead; /該頂點(diǎn)的鄰接表表頭指針 Graph Vert;typedef struct / 圖數(shù)據(jù)類型 vMAXVERTEXNUM;/

3、頂點(diǎn)數(shù)組 n; /實(shí)際頂點(diǎn)個(gè)數(shù) Graph;(2) 初始化圖在使用圖之前，初始化其為一個(gè)空?qǐng)D?？梢酝ㄟ^一個(gè)函數(shù)實(shí)現(xiàn)該操作，函數(shù)接 收一個(gè)待初始化的圖的地址作為參數(shù)。void In itGraph(Graph *g)/* 初始化指針g所指向的圖為空*/g- = 0; /設(shè)置圖中頂點(diǎn)的個(gè)數(shù)為0:空?qǐng)D(3) 創(chuàng)立圖頂點(diǎn)給定一個(gè)頂點(diǎn)數(shù)據(jù)，在圖中為其創(chuàng)立一個(gè)新頂點(diǎn)。int CreateVertex(Graph *g, char *vertData)/*給定字符串?dāng)?shù)據(jù)“ vertData在g指向的圖中為其創(chuàng)立一個(gè)新頂點(diǎn)*/ 1.指向新頂點(diǎn)在圖g中的存儲(chǔ)位置Graph_Vert *pNewVert = &(

4、 g-v g- n );/ 2.把頂點(diǎn)數(shù)據(jù)存入到新頂點(diǎn)中 strcpy(, );/ 3.初始化新頂點(diǎn)的鄰接表為空/ 4.圖中頂點(diǎn)個(gè)數(shù)加1/ 5.返回新頂點(diǎn)在圖中存放位置的索引 retur n g-n - 1;(4) 創(chuàng)立圖邊在圖中的兩個(gè)頂點(diǎn)之間創(chuàng)立一條有向邊，并存儲(chǔ)邊上的數(shù)據(jù)信息void CreateEdge(Graph *g, i nt v1, i nt v2, float edgeData)/*在圖g中的兩個(gè)索引號(hào)為v1和v2的頂點(diǎn)之間創(chuàng)立一條有向邊*/ 1.開辟一個(gè)鄰接頂點(diǎn)空間Graph_AdjVert *pAdjVert = 0;pAdjVert = ;/ 2.建立頂點(diǎn)v1相對(duì)頂點(diǎn)v2

5、的鄰接頂點(diǎn)信息pAdjVert-adjvert = ;pAdjVert-edgel nfo =;/ 3.把該鄰接頂點(diǎn)參加到頂點(diǎn)v1的鄰接表中(放于表頭)pAdjVert- n ext =;g-vv1.pHead =;(5) 調(diào)試使用上述操作，完成下面代碼，運(yùn)行并調(diào)試程序。void mai n()Graph a; /定義一個(gè)圖對(duì)象/ 1.初始化該圖為空?qǐng)D / 2.依次輸入學(xué)校內(nèi)的主要景點(diǎn)名稱，并在圖中為其創(chuàng)立對(duì)應(yīng)頂點(diǎn) / 3.根據(jù)輸入景點(diǎn)之間的地理關(guān)系和距離，在圖中的頂點(diǎn)之間建立/相應(yīng)的連接邊。注意：圖中的邊為有向邊(而景點(diǎn)之間的道路是/無向的，可通過建兩條有向邊來模擬無向邊)，邊權(quán)值為景點(diǎn)距離

6、/ 4.依次輸出每個(gè)景點(diǎn)的相鄰景點(diǎn)以及它們之間的距離(二)算法練習(xí)：根據(jù)功能提示，實(shí)現(xiàn)算法。(1) 刪除圖邊刪除圖中的某條有向邊v1, v2。算法實(shí)現(xiàn)提示：1)在頂點(diǎn)v1的鄰接表中查 找是否存在鄰接頂點(diǎn)v2 ； 2)如果存在，把該鄰接頂點(diǎn)從v1的鄰接表中移除。如刪 除成功，返回1;否那么返回-1。函數(shù)原型如下：/*刪除g所指向的圖中的有向邊v1, v2*/int DeleteEdge(Graph *g, int v1, int v2) ;(2) 查找圖頂點(diǎn)在圖中查找包含給定數(shù)據(jù)的頂點(diǎn)。如找到，返回頂點(diǎn)索引；否那么，返回 -1。函 數(shù)原型如下：/*在g所指向的圖中查找包含指針vertData所指

7、向字符串?dāng)?shù)據(jù)的頂點(diǎn)*/int Fin dVertex(Graph *g, char *vertData) ;(3) 查找圖邊在圖中查找一條特定的有向邊v1, v2。如找到，返回該邊所對(duì)應(yīng)的鄰接頂點(diǎn)； 否那么，返回NULL。函數(shù)原型如下：/*在g所指向的圖中查找有向邊v1, v2*/Graph AdjVert* FindEdge(Graph *g, int v1, int v2) ;(4)調(diào)試構(gòu)建測(cè)試數(shù)據(jù)，在主函數(shù)中調(diào)用上述所有操作，運(yùn)行并調(diào)試程序三思考1圖中頂點(diǎn)的單鏈表存儲(chǔ)在當(dāng)前的圖定義存儲(chǔ)中，我們使用數(shù)組來存放圖中的頂點(diǎn)。這種方式雖然實(shí)現(xiàn) 簡(jiǎn)單，但是存在以下缺乏： 最多只能存放MAXVERT

8、EXNUM 個(gè)元素； 如果 刪除圖中的某個(gè)頂點(diǎn)，存儲(chǔ)在之后的其它頂點(diǎn)的索引號(hào)會(huì)發(fā)生改變，相應(yīng)地需要更 新對(duì)應(yīng)邊中的頂點(diǎn)索引號(hào)，這需要較大的時(shí)間開銷。為了解決這一問題，可考慮使 用單鏈表來存儲(chǔ)圖中的頂點(diǎn)，進(jìn)而在鄰接表中的鄰接頂點(diǎn)中存放對(duì)應(yīng)頂點(diǎn)的地址而 不是頂點(diǎn)索引。嘗試使用單鏈表來存儲(chǔ)圖中頂點(diǎn)，并實(shí)現(xiàn)其常用算法。二、圖的應(yīng)用目標(biāo)：利用圖來解決一些實(shí)際應(yīng)用問題。1無權(quán)圖最短路徑問題給定一個(gè)無權(quán)圖，計(jì)算一個(gè)頂點(diǎn)到其它頂點(diǎn)的最短路徑。以學(xué)校的景點(diǎn)圖為例，計(jì)算從某一景點(diǎn)到達(dá)另一景點(diǎn)需要借道其它景點(diǎn)數(shù)最少的路線。注意：該路線不一 定距離最短。為了實(shí)現(xiàn)該問題，對(duì)圖頂點(diǎn)數(shù)據(jù)類型進(jìn)行了擴(kuò)充，具體算法如下：typ

9、edef struct vert / 頂點(diǎn)數(shù)據(jù)類型char data128; / 頂點(diǎn)數(shù)據(jù)Graph_AdjVert *pHead; /該頂點(diǎn)的鄰接表表頭指針/最短路徑算法運(yùn)行過程記錄表中的數(shù)據(jù)int known;float dis;int path; Graph_Vert;int ComputeUnweightShortPathGraph *g, int v1, int v2/*令圖g為無權(quán)圖，計(jì)算頂點(diǎn)v1到頂點(diǎn)v2之間的最短路徑*/int i, j;intQueue q; /使用隊(duì)列來模擬算法運(yùn)行過程Graph_AdjVert *p;Graph_Vert *v, *w;int bFound

10、 = 0; /是否找到一條合法路徑：0/1/初始化算法運(yùn)行過程記錄表for(i = 0; i n; i +)v = &(g-vi);/ 各個(gè)頂點(diǎn)v-known = 0;/確定該頂點(diǎn)是否有從v1到它的最短路徑v-dis = -1;/最短路徑距離v-path = -1;/從v1到達(dá)該頂點(diǎn)的路徑上的前一個(gè)頂點(diǎn)g-vv1.dis = 0;/ 從頂點(diǎn) v1 出發(fā)Ini tQueue(&q);EnQueue(&q, v1); /把v1放入隊(duì)列中，開始模擬算法運(yùn)行過程while(!lsQueueEmpty()/ 隊(duì)列非空i = DeQueue(&q);/出隊(duì)列，算法運(yùn)行到達(dá)該頂點(diǎn)v = ;/從圖中取出該頂點(diǎn)

11、v-known = 1;/標(biāo)記該頂點(diǎn)存在與v1的最短路徑if( ) /如果該頂點(diǎn)即為v2，那么最短路徑計(jì)算完成bFound = 1;break;/繼續(xù)從該頂點(diǎn)出發(fā)，把相鄰頂點(diǎn)放入算法運(yùn)行隊(duì)列p = v-pHead;while(p != 0)j = ; /相鄰頂點(diǎn)的索引號(hào)w = ; /從圖中取出該相鄰頂點(diǎn)if(w-dis = -1) /查看是否該頂點(diǎn)已被訪問過;設(shè)置該頂點(diǎn)的路徑距離為v的路徑距離+1 ;設(shè)置該頂點(diǎn)的前一個(gè)頂點(diǎn)為v (索引，即i)EnQueue(, j); /把該頂點(diǎn)放入隊(duì)列中 p = p-n ext;retur n bFound;2帶權(quán)圖最短路徑問題類似地，給定一個(gè)帶權(quán)圖，可計(jì)算

12、一個(gè)頂點(diǎn)到其它頂點(diǎn)的最短路徑。以學(xué)校的 景點(diǎn)圖為例，計(jì)算從某一景點(diǎn)到達(dá)另一景點(diǎn)距離最短的路線。算法可通過如下函數(shù) 實(shí)現(xiàn)：/*令圖g為有權(quán)圖，計(jì)算頂點(diǎn)v1到頂點(diǎn)v2之間的最短路徑*/int ComputeWeightShortPathGraph *g, int v1, int v2;3最小生成樹問題給定一個(gè)帶權(quán)的連通圖，為其計(jì)算一棵最小生成樹。以學(xué)校的景點(diǎn)圖為例各 個(gè)景點(diǎn)之間均連通，假設(shè)每條道路的單位造價(jià)本錢相同，在現(xiàn)有景點(diǎn)圖的根底上， 設(shè)計(jì)一個(gè)可以保證所有景點(diǎn)有道路相通但總造價(jià)最小的景點(diǎn)連接方案。算法可通過 如下函數(shù)實(shí)現(xiàn)：/*令圖g為帶權(quán)的連通圖，為其計(jì)算一棵最小生成樹，且存儲(chǔ)在 圖gTree中*/void ComputeMi nSpa nTreeGraph *g. Graph *gTree;4綜合練習(xí)利用圖實(shí)現(xiàn)一個(gè)簡(jiǎn)單的航線管理系統(tǒng)。這里，航線中的每個(gè)出發(fā)或者到達(dá)城市 對(duì)應(yīng)著圖中的一個(gè)頂點(diǎn)，而每條航線對(duì)應(yīng)