圖的應(yīng)用(附代碼)

1、一、 【實驗構(gòu)思（ conceive） 】(10%) （本部分應(yīng)包括：描述實驗實現(xiàn)的基本思路，包括所用到的離散數(shù)學(xué)、工程數(shù)學(xué)、程序設(shè)計、算法等相關(guān)知識）本次實驗要求實現(xiàn)利用圖來完成一個校園導(dǎo)航程序。該程序應(yīng)該可以顯示多個地點的具體信息并顯示出兩地之間的所有路徑和最短路徑。我的想法是先對頂點和要構(gòu)建的網(wǎng)做一個結(jié)構(gòu)定義，然后建立一個無向網(wǎng)，并用無向網(wǎng)表示校園景點的平面圖。并用數(shù)組把所有地點進行編號并把他們的信息同樣放入數(shù)組保存。最后利用循環(huán)，標(biāo)志確定，等一系列知識完成這個尋找路徑的過程。二、 【實驗設(shè)計 (design)】(20%) （本部分應(yīng)包括：抽象數(shù)據(jù)類型的功能規(guī)格說明、主程序模塊、各子程序

2、模塊的偽碼說明，主程序模塊與各子程序模塊間的調(diào)用關(guān)系）typedef struct vertextype; / 對頂點的結(jié)構(gòu)定義，包括了頂點信息和內(nèi)容typedef struct mgraph; / 對網(wǎng)的結(jié)構(gòu)定義 ,包括頂點和邊void path(mgraph g,int i,int j,int k) / 尋找路徑函數(shù) ,確定路徑上第 k+1 個頂點的序號 ,并保證找到的是簡單路徑，然后置訪問標(biāo)志位為1 void disppath(mgraph g,int i,int j)/通過調(diào)用 path 函數(shù)，找到從 vi到vj的所有路徑并輸出void ppath(mgraph g,int path1

3、,int i,int v0)/找到最短路徑，則返回。否則依次輸出路徑中的景點名稱void dispath(mgraph g,int dist,int path1,int s,int n,int v0,int i)/ 當(dāng) v0 不等于 i，且 is，調(diào)用 ppath 函數(shù)，輸出路徑中的頂點void dijkstra(mgraph g,int v0,int p)/輸出最短路徑void searchname(mgraph g)/ 在網(wǎng)中找到其編號與輸入的頂點編號相同的頂點，然后輸出頂點的名稱和簡介信息void searchpath1(mgraph g)/ 在網(wǎng)中找到其編號與輸入的出發(fā)景點的編號相同的

4、頂點和與其編號與輸入的目的景點的編號相同的頂點，然后調(diào)用 disppath函數(shù),用來輸出兩個景點間的所有路徑void searchpath2(mgraph g)/ 在網(wǎng)中找到其編號與輸入的出發(fā)景點的編號相同的頂點和與其編號與輸入的目的景點的編號相同的頂點，然后調(diào)用dijkstra函數(shù),用來輸出兩個景點間的最短路徑void main()/主函數(shù)，調(diào)用子函數(shù)完成用戶要求三、 【實現(xiàn)描述（ implement） 】(30%) （本部分應(yīng)包括：抽象數(shù)據(jù)類型具體實現(xiàn)的函數(shù)原型說明、關(guān)鍵操作實現(xiàn)的偽碼算法、 函數(shù)設(shè)計、函數(shù)間的調(diào)用關(guān)系，關(guān)鍵的程序流程圖等，給出關(guān)鍵算法的時間復(fù)雜度分析。）#include

5、#include #define maxv 20 #define maxsize 20 #define maxlen 500 #define inf 32767/*用32767 表示*/ int a=0; 頂點的結(jié)構(gòu)定義typedef struct int num; char namemaxsize; char contentmaxlen; vertextype; 網(wǎng)的結(jié)構(gòu)定義typedef struct int edgesmaxvmaxv; int vexnum,arcnum; vertextype vexsmaxv; mgraph; int visitedmaxv; int pmaxv;

6、尋找路徑函數(shù)：void path(mgraph g,int i,int j,int k) /* 確定路徑上第 k+1 個頂點的序號 */ int s; if(pk=j)/*找到一條路徑 */ a+;/* 路徑的條數(shù)值加 1*/ printf( 第%d條:n,a); for(s=0;s,); printf(n); s=0; while(sg.vexnum) if(s!=i)/*保證找到的是簡單路徑 */ if(g.edgespks!=inf&visiteds=0) /* 當(dāng)vk與vs之間有邊存在且 vs未被訪問過 */ visiteds=1;/*置訪問標(biāo)志位為

7、1,即已訪問的 */ pk+1=s;/*將頂點s加入到 p數(shù)組中 */ path(g,i,j,k+1); visiteds=0;/*重置訪問標(biāo)志位為 0，以便該頂點能被重新使用*/ s+; 輸出路徑函數(shù)：void disppath(mgraph g,int i,int j) int k; p0=i; for(k=0;k,);/*依次輸出路徑中的景點名稱*/ 計算最短路徑函數(shù)：void dispath(mgraph g,int dist,int path1,int s,int n,int v0,int i) if(si=1&i!=v0) /* 當(dāng)v0不等于 i，且

8、is*/ printf( 從%s到%s的最短游覽路徑是 :n,,); printf(%s-,); ppath(g,path1,i,v0);/*調(diào)用ppath 函數(shù)，輸出路徑中的頂點*/ printf(%s ,); printf( 路徑長度： %d米n,disti); 輸出最短路徑函數(shù)：void dijkstra(mgraph g,int v0,int p) int distmaxv,path1maxv; int smaxv; int mindis,i,j,u,n=g.vexnum; for(i=

9、0;in;i+) disti=g.edgesv0i;/*距離初始化 */ si=0;/*s置空*/ if(g.edgesv0iinf)/*路徑初始化 */ path1i=v0; else path1i=-1; sv0=1;path1v0=0;/*源點編號 v0放入s中*/ for(i=0;in;i+) mindis=inf; u=-1; for(j=0;jn;j+)/*選取不在 s中具有最小距離的頂點 u*/ if(sj=0&distjmindis) u=j; mindis=distj; su=1;/* 頂點u加入s中*/ for(j=0;jn;j+)/*修改不在 s中的頂點的距離 *

10、/ if(sj=0) if(g.edgesujinf&distu+g.edgesujdistj) /* 修正disti,path1i*/ distj=distu+g.edgesuj; path1j=u; dispath(g,dist,path1,s,n,v0,p);/*輸出最短路徑 */ 查詢景點信息函數(shù)：void searchname(mgraph g) printf( 景點： n1: 體育館 n2: 中邦樓 n3: 文匯樓 n4: 西門n5: 食堂n6: 格物樓 n7: 力行樓n8: 楠苑n9: 梓苑n10: 實驗樓 n11: 圖書館 n); int i; char s; prin

11、tf( 選擇： ); scanf(%d,&i); for(int j=0;jg.vexnum;j+)/*g.vexnum表示網(wǎng)中的頂點個數(shù) */ if(i=g.vexsj.num)/*在網(wǎng)中找到其編號與輸入的頂點編號相同的頂點*/ printf(%s簡介： n,);/*輸出頂點的名稱 */ printf(%s,g.vexsj.content);/*輸出頂點的簡介信息 */ printf(n); 查詢所有路徑函數(shù)：void searchpath1(mgraph g) printf( 景點： n1: 體育館 n2: 中邦樓 n3: 文匯樓 n4: 西門n5: 食堂n

12、6: 格物樓 n7: 力行樓n8: 楠苑n9: 梓苑n10: 實驗樓 n11: 圖書館 n); int i,j; char s; printf( 選擇出發(fā)景點： ); scanf(%d,&i); printf( 選擇目地景點： ); scanf(%d,&j); for(int k=0;kg.vexnum;k+)/*g.vexnum表示網(wǎng)中的頂點個數(shù) */ if(i=g.vexsk.num) i=k;/* 在網(wǎng)中找到其編號與輸入的出發(fā)景點的編號相同的頂點*/ for(int l=0;lg.vexnum;l+) if(j=g.vexsl.num) j=l;/* 在網(wǎng)中找到其編號與輸

13、入的目地景點的編號相同的頂點*/ printf( 從%s到%s的所有游覽路徑有 :n,,);/*輸出出發(fā)景點和目地景點的名稱*/ disppath(g,i,j);/*調(diào)用disppath 函數(shù),用來輸出兩個景點間的所有路徑*/ 查詢最短路徑函數(shù)：void searchpath2(mgraph g) printf( 景點： n1: 體育館 n2: 中邦樓 n3: 文匯樓 n4: 西門n5: 食堂n6: 格物樓 n7: 力行樓n8: 楠苑n9: 梓苑n10: 實驗樓 n11: 圖書館 n); int i=0,j=0; char s=0; printf

14、( 選擇出發(fā)景點： ); scanf(%d,&i); printf( 選擇目地景點： ); scanf(%d,&j); for(int k=0;kg.vexnum;k+)/*g.vexnum表示網(wǎng)中的頂點個數(shù) */ if(i=g.vexsk.num) i=k;/* 在網(wǎng)中找到其編號與輸入的出發(fā)景點的編號相同的頂點*/ for(int l=0;lg.vexnum;l+) if(j=g.vexsl.num) j=l;/* 在網(wǎng)中找到其編號與輸入的目地景點的編號相同的頂點*/ dijkstra(g,i,j);/*調(diào)用 dijkstra 函數(shù),用來輸出兩個景點間的最短路徑*/ 主函數(shù)：

15、void main() int i=0,j=0; int b11=1,2,3,4,5,6,7,8,9,10,11;/*整型數(shù)組 ,用來給每個頂點的編號進行賦值*/ char *c11= 體育館 , 中邦樓 , 文匯樓 ,西門, 食堂, 格物樓 ,力行樓 ,楠苑,梓苑,實驗樓 , 圖書館 ;/* 字符串指針數(shù)組 ,用來給每個頂點的名稱進行賦值*/ char *d11= /* 字符串指針數(shù)組 ,用來給每個頂點的簡介信息進行賦值*/ 體育館建筑面積 23993m2 ，座席數(shù)：固定坐席 4068 個、觀眾臨時坐席 3956 個。, 中邦樓配有多個教室，為大量學(xué)生提供了自習(xí)和上課的地方。, 文匯樓有 5

16、層,配有4個電梯 ,總建設(shè)面積 12167 平方米，可同時容納 2000 人上課。 , 西門的整體設(shè)計思想明確、富有時代氣息。, 食堂設(shè)計的簡約實用，有較為豐富的食物提供并為學(xué)生營造了舒適休閑環(huán)境。, 格物樓為公共教學(xué)樓，約有100 個教室，供 10000 學(xué)生上課。 , 力行樓結(jié)構(gòu)合理，設(shè)施先進。每個學(xué)生教室都配備了高亮度多媒體投影機，極大地方便了教師在課堂上利用現(xiàn)代教育技術(shù)。, 楠苑結(jié)構(gòu)合理，設(shè)施先進，為大量學(xué)生配置了舒適的住宿環(huán)境, 梓苑的建筑精美別致、結(jié)構(gòu)合理、功能齊備，為大量學(xué)生配置了舒適的住宿環(huán)境, 實驗樓建筑面積 25000 平方米，為軟件學(xué)院學(xué)生提供實驗設(shè)備與場所。, 圖書館藏

17、書豐富、建筑宏偉、環(huán)境幽雅。館內(nèi)服務(wù)功能完備，擁有多種現(xiàn)代化的服務(wù)手段。 ,; mgraph g;/*定義一個 mgraph 類型的變量 g,用來創(chuàng)建一個無向網(wǎng) */ /* 建立一個無向網(wǎng)，并用無向網(wǎng)表示校園景點的平面圖*/ int a1111= /* 用inf表示對應(yīng)頂點間沒有直達的道路， 用其它整型變量表示對應(yīng)頂點間有直達的道路，且路徑的長度就是該整型變量的值*/ inf,300,inf,inf,inf,inf,inf,inf,inf,inf,350, 300,inf,50,inf,inf,150,inf,inf,120,inf,inf, inf,50,inf,150,inf,inf,in

18、f,inf,inf,inf,inf, inf,inf,180,inf,100,inf,inf,inf,inf,inf,inf, inf,inf,inf,230,inf,100,68,inf,inf,inf,inf, inf,80,inf,inf,100,inf,inf,60,inf,inf,inf, inf,inf,inf,inf,80,inf,inf,180,inf,inf,inf, inf,inf,inf,inf,inf,200,180,inf,105,150,inf, inf,122,inf,inf,inf,inf,inf,105,inf,inf,inf, inf,inf,inf,inf

19、,inf,inf,inf,156,inf,inf,240, 305,inf,inf,inf,inf,inf,inf,inf,inf,220,inf; g.vexnum=11;/*網(wǎng)中頂點的個數(shù)為 11，即校園景點的個數(shù)為 11*/ g.arcnum=14;/*網(wǎng)中邊的個數(shù)為 14，即校園景點間的道路為 14條*/ for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.edgesij=aij;/*建立無向網(wǎng)的鄰接矩陣 */ for(i=0;ig.vexnum;i+) g.vexsi.num=bi;/*給每個頂點一個編號 */ strcpy(g.vexsi.n

20、ame,ci);/*通過字符串復(fù)制函數(shù)給每個頂點一個名稱*/ strcpy(g.vexsi.content,di);/*通過字符串復(fù)制函數(shù)給每個頂點加上信息，即作為景點的簡介信息 */ int select;/*定義一個整型變量 ,用來輸入不同的選擇 */ printf(-校園導(dǎo)游程序-); printf( 本程序能夠： ); do/* 可提供循環(huán)輸入選擇 ,當(dāng)輸入的選擇為 4時,退出循環(huán) */ printf(1:查詢景點的信息 2:查詢景點間的游覽路徑3:查詢景點間的最短游覽路徑4:退出 ); printf( 選擇:); scanf(%d,&select); switch(selec

21、t) /* 判斷select 的值，根據(jù)其值跳轉(zhuǎn)到相應(yīng)的子模塊繼續(xù)執(zhí)行*/ case 1: searchname(g);/*查詢景點的信息 */ break; case 2: searchpath1(g);/*查詢景點間的游覽路徑 */ break; case 3: searchpath2(g);/*查詢景點間的最短游覽路徑*/ break; case 4:/* 退出程序 */ break; while(select!=4);/*當(dāng)select 的值不為 4時，繼續(xù)循環(huán) */ 四、 【測試結(jié)果（ testing） 】(10%) （本部分應(yīng)包括：對實驗的測試結(jié)果，應(yīng)具體列出每次測試所輸入的數(shù)據(jù)以

22、及輸出的數(shù)據(jù)，并對測試結(jié)果進行分析總結(jié)）用戶提示界面：選擇 1：查詢景點的信息選擇 2：查詢景點間的路徑選擇 3：查詢景點間的最短瀏覽路徑測試結(jié)果分析： 本程序基本達到了實驗的目的， 能夠根據(jù)用戶輸入的出發(fā)地、 目的地，自動的檢索可行路徑，并能夠給出其中最短的路徑。五、 【實驗總結(jié)】 (10%) （本部分應(yīng)包括：自己在實驗中完成的任務(wù)，注意組內(nèi)的任意一位同學(xué)都必須獨立完成至少一項接口的實現(xiàn) ；對所完成實驗的經(jīng)驗總結(jié)、心得）通過這次實驗， 讓我對圖有了更深入的認(rèn)識，尤其是圖的存儲方式以及圖的各種操作。這次實驗以呈貢校區(qū)為藍本，通過編程實現(xiàn)兩個地點之間最短路徑的檢索，這一方面讓我了解了圖的應(yīng)用，

23、一方面也提高了我應(yīng)用圖來解決實際問題的能力。這次實驗讓我收獲不少。當(dāng)然，實驗中也遇到了不少問題，比方說如何利用一個無向圖來完成路程的表示。所以在今后的學(xué)習(xí)中要不斷努力，不斷提高自己。六、 【代碼】 (10%) （本部分應(yīng)包括：完整的代碼及充分的注釋。注意紙質(zhì)的實驗報告無需包括此部分。格式統(tǒng)一為，字體 : georgia , 行距: 固定行距 12，字號: 小五）#include #include #define maxv 20 #define maxsize 20 #define maxlen 500 #define inf 32767/*用 32767 表示 */ int a=0; type

24、def struct int num; char namemaxsize; char contentmaxlen; vertextype; typedef struct int edgesmaxvmaxv; int vexnum,arcnum; vertextype vexsmaxv; mgraph; int visitedmaxv; int pmaxv; void path(mgraph g,int i,int j,int k) /* 確定路徑上第k+1 個頂點的序號 */ int s; if(pk=j)/*找到一條路徑 */ a+;/* 路徑的條數(shù)值加1*/ printf(第%d 條:n,

25、a); for(s=0;s,); printf(n); s=0; while(sg.vexnum) if(s!=i)/*保證找到的是簡單路徑*/ if(g.edgespks!=inf&visiteds=0) /* 當(dāng) vk 與 vs 之間有邊存在且vs 未被訪問過 */ visiteds=1;/*置訪問標(biāo)志位為1,即已訪問的 */ pk+1=s;/*將頂點 s 加入到 p 數(shù)組中 */ path(g,i,j,k+1); visiteds=0;/*重置訪問標(biāo)志位為0，以便該頂點能被重新使用*/ s+; void disppath(mgraph g,int i,i

26、nt j) int k; p0=i; for(k=0;k,);/*依次輸出路徑中的景點名稱*/ void dispath(mgraph g,int dist,int path1,int s,int n,int v0,int i) if(si=1&i!=v0) /* 當(dāng) v0 不等于 i，且 is*/ printf(從%s 到%s 的最短游覽路徑是:n,,); printf(%s-,); ppath(g,path1,i,v0);/*調(diào)用 ppath 函數(shù)，輸出路徑中的頂點*/ printf

27、(%s ,); printf(路徑長度： %d 米n,disti); void dijkstra(mgraph g,int v0,int p) int distmaxv,path1maxv; int smaxv; int mindis,i,j,u,n=g.vexnum; for(i=0;in;i+) disti=g.edgesv0i;/*距離初始化 */ si=0;/*s置空 */ if(g.edgesv0iinf)/*路徑初始化 */ path1i=v0; else path1i=-1; sv0=1;path1v0=0;/*源點編號 v0 放入 s 中*/ for(i

28、=0;in;i+) mindis=inf; u=-1; for(j=0;jn;j+)/*選取不在s中具有最小距離的頂點u*/ if(sj=0&distjmindis) u=j; mindis=distj; su=1;/*頂點 u 加入 s中*/ for(j=0;jn;j+)/*修改不在s中的頂點的距離*/ if(sj=0) if(g.edgesujinf&distu+g.edgesujdistj) /* 修正 disti,path1i*/ distj=distu+g.edgesuj; path1j=u; dispath(g,dist,path1,s,n,v0,p);/*輸出最短

29、路徑 */ void searchname(mgraph g) printf(景點：n1: 體育館 n2: 中邦樓 n3: 文匯樓 n4: 西門 n5: 食堂 n6: 格物樓 n7: 力行樓 n8: 楠苑 n9: 梓苑 n10:實驗樓 n11: 圖書館 n); int i; char s; printf( 選擇： ); scanf(%d,&i); for(int j=0;jg.vexnum;j+)/*g.vexnum表示網(wǎng)中的頂點個數(shù)*/ if(i=g.vexsj.num)/*在網(wǎng)中找到其編號與輸入的頂點編號相同的頂點*/ printf(%s簡介： n,);/*

30、輸出頂點的名稱 */ printf(%s,g.vexsj.content);/*輸出頂點的簡介信息*/ printf(n); void searchpath1(mgraph g) printf(景點：n1: 體育館 n2: 中邦樓 n3: 文匯樓 n4: 西門 n5: 食堂 n6: 格物樓 n7: 力行樓 n8: 楠苑 n9: 梓苑 n10:實驗樓 n11: 圖書館 n); int i,j; char s; printf( 選擇出發(fā)景點：); scanf(%d,&i); printf(選擇目地景點：); scanf(%d,&j); for(int k=0;kg.vexnum;k

31、+)/*g.vexnum表示網(wǎng)中的頂點個數(shù)*/ if(i=g.vexsk.num) i=k;/*在網(wǎng)中找到其編號與輸入的出發(fā)景點的編號相同的頂點*/ for(int l=0;lg.vexnum;l+) if(j=g.vexsl.num) j=l;/*在網(wǎng)中找到其編號與輸入的目地景點的編號相同的頂點*/ printf(從%s到%s的所有游覽路徑有:n,,);/*輸出出發(fā)景點和目地景點的名稱*/ disppath(g,i,j);/*調(diào)用 disppath 函數(shù) ,用來輸出兩個景點間的所有路徑*/ void searchpath2(mgraph g)

32、printf(景點：n1: 體育館 n2: 中邦樓 n3: 文匯樓 n4: 西門 n5: 食堂 n6: 格物樓 n7: 力行樓 n8: 楠苑 n9: 梓苑 n10:實驗樓 n11: 圖書館 n); int i=0,j=0; char s=0; printf( 選擇出發(fā)景點：); scanf(%d,&i); printf(選擇目地景點：); scanf(%d,&j); for(int k=0;kg.vexnum;k+)/*g.vexnum表示網(wǎng)中的頂點個數(shù)*/ if(i=g.vexsk.num) i=k;/*在網(wǎng)中找到其編號與輸入的出發(fā)景點的編號相同的頂點*/ for(int l

33、=0;lg.vexnum;l+) if(j=g.vexsl.num) j=l;/*在網(wǎng)中找到其編號與輸入的目地景點的編號相同的頂點*/ dijkstra(g,i,j);/*調(diào)用 dijkstra函數(shù) ,用來輸出兩個景點間的最短路徑*/ void main() int i=0,j=0; int b11=1,2,3,4,5,6,7,8,9,10,11;/*整型數(shù)組 ,用來給每個頂點的編號進行賦值*/ char *c11= 體育館 , 中邦樓 , 文匯樓 , 西門 ,食堂 , 格物樓 , 力行樓 ,楠苑 , 梓苑 , 實驗樓 , 圖書館 ;/*字符串指針數(shù)組 ,用來給每個頂點的名稱進行賦值*/ ch

34、ar *d11= /* 字符串指針數(shù)組,用來給每個頂點的簡介信息進行賦值*/ 體育館建筑面積23993m2 ，座席數(shù)：固定坐席4068 個、觀眾臨時坐席3956 個。 , 中邦樓配有多個教室，為大量學(xué)生提供了自習(xí)和上課的地方。, 文匯樓有 5 層,配有 4 個電梯 ,總建設(shè)面積12167 平方米，可同時容納2000 人上課。 , 西門的整體設(shè)計思想明確、富有時代氣息。, 食堂設(shè)計的簡約實用，有較為豐富的食物提供并為學(xué)生營造了舒適休閑環(huán)境。, 格物樓為公共教學(xué)樓，約有100 個教室，供10000 學(xué)生上課。 , 力行樓結(jié)構(gòu)合理， 設(shè)施先進。 每個學(xué)生教室都配備了高亮度多媒體投影機，極大地方便了教

35、師在課堂上利用現(xiàn)代教育技術(shù)。 , 楠苑結(jié)構(gòu)合理，設(shè)施先進，為大量學(xué)生配置了舒適的住宿環(huán)境, 梓苑的建筑精美別致、結(jié)構(gòu)合理、功能齊備，為大量學(xué)生配置了舒適的住宿環(huán)境, 實驗樓建筑面積25000 平方米，為軟件學(xué)院學(xué)生提供實驗設(shè)備與場所。, 圖書館藏書豐富、建筑宏偉、環(huán)境幽雅。館內(nèi)服務(wù)功能完備，擁有多種現(xiàn)代化的服務(wù)手段。,; mgraph g;/*定義一個mgraph類型的變量g,用來創(chuàng)建一個無向網(wǎng)*/ /* 建立一個無向網(wǎng)，并用無向網(wǎng)表示校園景點的平面圖*/ int a1111= /* 用 inf 表示對應(yīng)頂點間沒有直達的道路，用其它整型變量表示對應(yīng)頂點間有直達的道路，且路徑的長度就是該整型變量的值 */ inf,300,inf,inf,inf,inf,inf,inf,inf,inf,350, 300,inf,50,inf,inf,150,in