無向圖數(shù)據(jù)結構報告

工程造價最小問題一、問題描述如果以無向網(wǎng)表示n個城市之間的交通網(wǎng)絡建設規(guī)劃，頂點表示城市，邊上的權表示該線路的造價，試設計一個方案，使這個交通網(wǎng)的總造價最小。二、根本要求了解并掌握數(shù)據(jù)結構與算法的設計方法，具備初步的獨立分析和設計能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等根本方法和技能；提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；訓練用系統(tǒng)的觀點和軟件開發(fā)一般標準進行軟件開發(fā)，培養(yǎng)軟件工作者所具備的科學工作方法和作風。5.要求完成以下功能(1)輸出頂點信息：將各地地名輸出。(2)輸出邊的信息：將各地間每兩個位置〔假設兩個地點之間有直接路徑〕的距離輸出。(3)修改：修改兩個地點〔假設兩個地點之間有直接路徑〕間的工程造價，并重新輸出每兩個地點〔假設兩個地點之間有直接路徑〕間的工程造價。(4)求最最小的工程造價：輸出給定兩點之間的最小造價的及途徑的地點或輸出任意一點與其它各點的最短路徑。(6)刪除：刪除任意一條邊。(7)插入：插入任意一條邊。6.實現(xiàn)要點：a)對圖的創(chuàng)立采用鄰接矩陣的存儲結構，而且對圖的操作設計成了模板類。為了便于處理，對于圖中的每一個頂點和每一條邊都設置了初值。b)為了便于訪問，用戶可以先輸出所有的地點和距離。c)用戶可以隨意修改兩點之間好的距離。d)用戶可以增加及刪除邊。e)當用戶操作錯誤時，系統(tǒng)會出現(xiàn)出錯提示。三、數(shù)據(jù)結構的設計抽象數(shù)據(jù)類型圖的定義如下：ADTGraph{數(shù)據(jù)對象V：V是具有相同特性數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關系R：R={VR}VR={〔v，w〕|v,w∈V,(v,w)表示v和w之間存在路徑}根本操作P：CreatGraph(&G,V,VR)初始條件：V是圖的頂點集，VR是圖中邊的集合。操作結果：按定義(V,VR)構造圖G。DestroyGraph(&G)初始條件：圖G已存在。操作結果：銷毀圖。LocateVex(G,u)初始條件：圖G存在，u和G中頂點具有相同特征。操作結果：假設G中存在頂點u，那么返回該頂點在圖中“位置”；否那么返回其它信息。GetVex(G,v)初始條件：圖G存在，v是G中某個頂點。操作結果：返回v的信息。InsertVex(&G,v)初始條件：圖G存在，v和G中頂點具有相同特征。操作結果：在圖G中增添新頂點v。DeleteVex(&G,v)初始條件：圖G存在，v和G中頂點具有相同特征。操作結果：刪除G中頂點v及其相關的邊。InsertArc(&G,v,w)初始條件：圖G存在，v和w是G中兩個頂點。操作結果：在G中增添弧<v,w>，假設G是無向的，那么還增添對稱弧<w,v>。DeleteArc(&G,v,w)初始條件：圖G存在，v和w是G中兩個頂點。操作結果：在G中刪除弧<v,w>，假設G是無向的，那么還刪除對稱弧<w,v>。}ADTGraph各函數(shù)名typedefstruct//圖中頂點表示點，存放點名稱voidMenu()//輸出菜單voidPutOutVex(MGraph*G)//輸出每個頂點的信息voidPutOutArc(MGraph*G)//輸出每條邊的信息voidDijkstra(MGraph*G)//迪杰斯特拉算法求最短路徑voidDeleteVex(MGraph*G)//刪除某個頂點voidDeleteArc(MGraph*G)//刪除某條邊voidInsertArc(MGraph*G)//插入某條邊voidmain()//主函數(shù)主程序voidmain(){初始化；while(“命令”!=“退出”){Switch語句接受命令〔輸入選擇項序號〕；處理命令；}}本程序運用函數(shù)的調用，只有兩個模塊，它們的調用關系為：主程序模塊帶權無向圖模塊四、程序流程圖MMain()InitGraph()PutOutVex()PutOutArc()Change()Dijkstra():DeleteVex():DeleteArc():InsertArc()exit(1)五、源程序#include<stdio.h>#include<iostream.h>#include<stdlib.h>#include<conio.h>#include<malloc.h>#include<string.h>#defineMAX10000#defineMAXLEN8#defineADJTYPEinttypedefstruct{charname[30];intnum;}VEXTYPE;typedefstruct{VEXTYPEvexs[MAXLEN];ADJTYPEarcs[MAXLEN][MAXLEN];intvexnum,arcnum;}MGraph;MGraphb;MGraphInitGraph(){inti,j;MGraphG;G.vexnum=6;G.arcnum=7;for(i=0;i<G.vexnum;i++)G.vexs[i].num=i;strcpy(G.vexs[0].name,"北京");strcpy(G.vexs[1].name,"重慶");strcpy(G.vexs[2].name,"廣州");strcpy(G.vexs[3].name,"長沙");strcpy(G.vexs[4].name,"上海");strcpy(G.vexs[5].name,"哈爾濱");for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j]=MAX;G.arcs[0][5]=100;G.arcs[0][2]=10;G.arcs[0][4]=30;G.arcs[4][5]=60;G.arcs[4][3]=20;G.arcs[3][5]=10;G.arcs[1][2]=5;for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[j][i]=G.arcs[i][j];returnG;}voidMenu(){cout<<"需要輸出各地點的信息請按0\n";cout<<"需要各地間工程造價的信息輸出請按1\n";cout<<"需要修改請按2\n";cout<<"需要求出最小的工程造價請按3\n";cout<<"需要刪除某個地點請按4\n";cout<<"需要刪除某條路徑請按5\n";cout<<"需要插入某條路徑請按6\n";cout<<"需要退出請按7\n";}voidPutOutVex(MGraph*G){intv;for(v=0;v<G->vexnum;v++)cout<<G->vexs[v].num<<G->vexs[v].name<<endl;}voidPutOutArc(MGraph*G){for(inti=0;i<G->vexnum;i++)for(intj=0;j<G->vexnum;j++)if(G->arcs[i][j]<MAX){cout<<"從"<<G->vexs[i].name<<"到"<<G->vexs[j].name<<G->arcs[i][j]<<endl;}}voidChange(MGraph*G){intv0,v1,length;cout<<"change\n";cin>>v0;cin>>v1;cout<<"length:";cin>>length;G->arcs[v0][v1]=G->arcs[v1][v0]=length;}voidDijkstra(MGraph*G){intv,w,i,min,t=0,x,v0,v1;intfinal[20],D[20],p[20][20];cout<<"請輸入出發(fā)點:\n";cin>>v0;if(v0<0||v0>G->vexnum){cout<<"此點地點不存在!請重新輸入頂點編號:";cin>>v0;}cout<<"請輸入目的地:\n";cin>>v1;if(v1<0||v1>G->vexnum){cout<<"此點地點不存在!請重新輸入地點編號:";cin>>v1;}for(v=0;v<G->vexnum;++v){final[v]=0;D[v]=G->arcs[v0][v];for(w=0;w<G->vexnum;++w)p[v][w]=0;if(D[v]<MAX){p[v][v0]=1;p[v][v]=1;}}D[v0]=0;final[v0]=1;for(i=1;i<G->vexnum;++i){min=MAX;for(w=0;w<G->vexnum;++w)if(!final[w])if(D[w]<min){v=w;min=D[w];}final[v]=1;for(w=0;w<G->vexnum;++w)if(!final[w]&&(min+G->arcs[v][w]<D[w])){D[w]=min+G->arcs[v][w];for(x=0;x<G->vexnum;++x)p[w][x]=p[v][x];p[w][w]=1;}}cout<<"從"<<G->vexs[v0].name<<"到"<<G->vexs[v1].name<<"的最小工程造價為："<<D[v1]<<endl;cout<<"路徑為：";for(intj=0;j<G->vexnum;++j){if(p[v1][j]==1)cout<<G->vexs[j].name<<endl;}}voidDeleteVex(MGraph*G)//刪除某個頂點{ introw,col; intv0; cout<<"請輸入要刪除的地點"; cin>>v0; for(inti=v0;i<G->vexnum;i++) G->vexs[i]=G->vexs[i+1]; G->vexnum--; for(row=0;row<G->vexnum;row++) { for(col=v0;col<G->vexnum;col++) G->arcs[row][col]=G->arcs[row][col+1]; } for(col=0;col<G->vexnum;col++) { for(row=v0;row<G->vexnum;row++) G->arcs[col][row]=G->arcs[col][row+1]; }}voidDeleteArc(MGraph*G){intv0,v1;cout<<"請輸入兩地點:\n";cin>>v0>>v1;G->arcs[v0][v1]=MAX;G->arcs[v1][v0]=MAX;}voidInsertArc(MGraph*G){intv0,v1,l=0;cout<<"請輸入兩地點:\n";cin>>v0>>v1;cout<<"請輸入工程造價:\n";cin>>l;G->arcs[v0][v1]=l;G->arcs[v1][v0]=l;}voidmain(){inta;b=InitGraph();Menu();cin>>a;while(a!=7){switch(a){case0:PutOutVex(&b);Menu();break;case1:PutOutArc(&b);Menu();break;case2:Change(&b);Menu();break;case3:Dijkstra(&b);Menu();break;case4:DeleteVex(&b);Menu();break;case5:DeleteArc(&