无向图数据结构报告

工程造价最小问题一、问题描述如果以无向网表示n个城市之间的交通网络建设规划，顶点表示城市，边上的权表示该线路的造价，试设计一个方案，使这个交通网的总造价最小。二、根本要求了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般标准进行软件开发，培养软件工作者所具备的科学工作方法和作风。5.要求完成以下功能(1)输出顶点信息：将各地地名输出。(2)输出边的信息：将各地间每两个位置〔假设两个地点之间有直接路径〕的距离输出。(3)修改：修改两个地点〔假设两个地点之间有直接路径〕间的工程造价，并重新输出每两个地点〔假设两个地点之间有直接路径〕间的工程造价。(4)求最最小的工程造价：输出给定两点之间的最小造价的及途径的地点或输出任意一点与其它各点的最短路径。(6)删除：删除任意一条边。(7)插入：插入任意一条边。6.实现要点：a)对图的创立采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。b)为了便于访问，用户可以先输出所有的地点和距离。c)用户可以随意修改两点之间好的距离。d)用户可以增加及删除边。e)当用户操作错误时，系统会出现出错提示。三、数据结构的设计抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性数据元素的集合，称为顶点集。数据关系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各函数名typedefstruct//图中顶点表示点，存放点名称voidMenu()//输出菜单voidPutOutVex(MGraph*G)//输出每个顶点的信息voidPutOutArc(MGraph*G)//输出每条边的信息voidDijkstra(MGraph*G)//迪杰斯特拉算法求最短路径voidDeleteVex(MGraph*G)//删除某个顶点voidDeleteArc(MGraph*G)//删除某条边voidInsertArc(MGraph*G)//插入某条边voidmain()//主函数主程序voidmain(){初始化；while(“命令”!=“退出”){Switch语句接受命令〔输入选择项序号〕；处理命令；}}本程序运用函数的调用，只有两个模块，它们的调用关系为：主程序模块带权无向图模块四、程序流程图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<<"请输入出发点:\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(&