南昌航空大學數(shù)據(jù)結(jié)構(gòu)與算法實驗六

1、南昌航空大學實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法實驗名稱：班級：XXX學生姓名：指導教師評定：XXX簽名:一、實驗?zāi)康膶嶒灹鶊D的遍歷XXX學號：XXXXXXXX圖結(jié)構(gòu)有著廣泛的應(yīng)用。二、實驗內(nèi)容本實驗主要涉及兩個方面的內(nèi)容：一個是有關(guān)圖的最短路徑問題，用一個交通查詢系統(tǒng)例子來驗證迪杰斯特拉算法和費洛伊德算法；而另一個則工程項目實施過程中的關(guān)鍵路徑問題 。三、程序分析設(shè)計一個交通查詢系統(tǒng)， 能讓游客查詢從任一城市頂點到另一城市頂點之間的最短路徑或最低花費或最少時間等問題。 對于不同查詢要求， 可輸入城市間的路程或所需時間或所需費用。本程序共分三個部分：（ 1）建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；（ 2）單源最

2、短路徑；（ 3）實現(xiàn)兩個城市頂點之間的最短路徑。四、程序源代碼該實例程序的源代碼如下：（1）建立有向圖的存儲結(jié)構(gòu)/ 文件名 CreateMGraph.cVoid CreateMGraph(MGraph * G，int n ，int e)/采用鄰接矩陣表示法構(gòu)造有向圖G，n， e 表示圖的當前頂點數(shù)和邊數(shù)int i,j,k,w;for(i=1;i<=n;i+)G->vexsi=(char)i;for(i=1;i<=n;i+)for(j=1;j<=n;j+)G->vexsij=Maxint;/初始化鄰接矩陣printf("輸入 %d 條邊的 i 、j 及 w

3、:n",e);for(k=1;k<=e;k+)scanf("%d,%d,%d,",&i,&j,&w);G->arcsij=w;printf("有向圖的存儲結(jié)構(gòu)建立完畢n");/ 文件 dijkstra.cvoid Dijkstra(MGraph *G ,int v1,int n)int D2MVNum,P2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;v<=nv+)Sv=FALSE;D2v=G->arcsv1v;if(D2v<Maxint)P

4、2v=v1;elsep2v=0;D2v1=0;Sv1=TRUE;for(i=2;i<n;i+)min=Maxint;for(w=1;w<=n;w+)if(!Sw&& D2w<min)v=w;min=D2w;Sv=TRUE;for(w=1;w<=n;w+)if(!Sw&& D2v+G->arcsvw<D2w)D2w=D2v+G->arcsvw;P2w=v;printf("路徑長度路徑 n");for(i=1;i<=n;i+)printf("%5d",D2i);printf(&q

5、uot;%5d",i);v=P2i;while(v!=0)printf("<-%d",v);v=P2v;printf("n");/ 文件 floyd.cvoid Floyd(MGraph *G,int n)int i,j,k,w;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(G->arcsij!=Maxint)Pij=j;elsePij=0;Dij=G->arcsij;for(k=1;k<=n;k+)for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(Di

6、k+Dkj<Dij)Dij=Dik+Dkj;Pij=Pik;/ 主程序#include#include#define MVNum100#define Maxint 32767enumbooleanFALSE,TRUE;typedef char VertexType;typedef intAdjmatrix;typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;#include "CreateMGraph

7、.c"#include "dijkstra.c"#include "floyd.c"void main()MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf("輸入圖中頂點個數(shù)和邊數(shù)n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);w, hile(xz!=0)printf("*求城市之間的最短路徑*n");printf(&qu

8、ot;=n");printf("1.求一個城市到所有城市的最短路徑n");printf("2.求任意的兩個城市之間的最短路徑n");printf("=n");printf("請選擇：1、或2、選擇0、退出： ");scanf("%d",&xz);if(xz=2)Floyd(G,n)printf("輸入源點 (或稱起點 ) 和終點 :v,w:");scanf("%d,%d",&v,&w);k=Pvw;if(k=0)print

9、f("頂點 %d 到 %d 無路徑 !n",v,w);elseprintf("從頂點 %d 到%d 的最短路徑是：%d!n",v,w,v);while(k!=w)printf("->%d",k);k=Pkw;printf("->%d",w);printf("路徑長度 :%dn",Dvw);elseif(xz=1)printf("求單源路徑，輸入源點v:");scanf("%d",&v);Dijkstra(G,v,n);printf(&q

10、uot;結(jié)束求最短路徑,再見 !n");五、實驗結(jié)果輸入圖中頂點個數(shù)和邊數(shù)n， e：7， 10 (表示輸入7 個頂點和 10 條邊 )輸入 10 條邊的 i、j 及 w1， 7，92， 1，202， 3，102， 4，303， 5，55， 4，125， 7，156， 5，86， 7，107， 3，18有向圖的存儲結(jié)構(gòu)建立完畢*求城市之間的最短路徑*=1求一個城市到所有城市的最短路徑2求任意的兩個城市之間的最短路徑=請選擇：1、或2、選擇0、退出：1求單源路徑，輸入源點v:1 （表示求從頂點1 到其他所有頂點的最短路徑）路徑長度路徑01/說明頂點 1 到 1路徑長度為 0327672/說明頂點 1 到 2無路徑， 32767 表示273<-7<-1/ 說明頂點 1 到 3 路徑長度為 27，路徑為 1，7， 3444<-5<-3<-7<-1325<-3<-7<