资源描述：
《图-铁路最短路径实习报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、图-铁路最短路径实习报告09040502班学号:052415朱博凯一、需求分析（1）本程序需要用户自行创建或打开已有的铁路图，城市名可以是中文也可以用英文表示，输入要求最短路径的两个城市，按回车键进行选定的操作！（2）程序功能：寻找两个指定城市之间的最短路径。（3）测试地图：city.txt；二、概要设计为实现本程序功能，应以图结构存储城市、路径以及相应的信息。1、图的抽象数据类型定义ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR} VR={
2、v,w(-V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作P：
3、CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图GDesoyGraph(&G);初始条件：图G存在操作结果：销毁图GLocateVex(G,u);初始条件：图G存在，u一G中顶点有相同特征操作结果：若G中存在顶点u,则返回该顶点在图中位置；否则返回其它信息。GetVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的值。PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点操作结果：对v赋值valueFirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返
4、回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”NextAdjVex(G,v,w);初始条件：图G存在,v是G中某个顶点,w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征操作结果：在图G中增添新顶点vDeleteVex(&G,v);初始条件：图G存在，v是G中某个顶点操作结果：删除G中顶点v及其相关的弧InsertAcr(&G,v,w);初始条件：图G存在，v和w是G中两个顶点操作结果：在G中增添弧,若G是无向的，则还增添对称弧DeleteArc(&
5、G,v,w);初始条件：图G存在，v和w是G中两个顶点操作结果：在G中删除弧,若G是无向的，则还删除对称弧DFSTraverser(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。BFSTRaverse(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次。一旦Visit()失败，则操作失败。}ADTGraph1、程序包括6个模块1
6、）主程序模块：2）创建交通图；3）载入已有交通图；4）显示城市列表；5）求最短路径；6）显示结果；三、详细设计1、元素类型、结点类型typedefstructArcCell{intadj;//相邻接的城市路径长度}ArcCell;//定义边的类型typedefstructVertexType{intnumber;//城市序号charcity[20];//城市名称}VertexType;//顶点类型typedefstructMGraph{VertexTypevexs[MAX_VERTAX_NUM];//图中的顶点，即为城市ArcCellarcs[MAX_VERTAX_NUM][MAX_VER
7、TAX_NUM];//图中的边，即为城市间的距离intvexnum,arcnum;//顶点数，边数}MGraph;//定义图的类型1、主函数和其他函数的伪码#defineINFINITY10000#defineMAX_VERTAX_NUM100#defineFALSE0#defineTRUE1#defineNULL0//函数定义voidSave(charfilename[10],MGraphG);intLocateVex(MGraphG,charu[20]);voidCreateUDN();voidShortestPath(intv0);voiddisplaycity();voidoutp
8、ut(intcity1,intcity2);//全局变量MGraphG;intP[MAX_VERTAX_NUM][MAX_VERTAX_NUM];longD[MAX_VERTAX_NUM];voidCreateUDN()//造图函数{charv1[20],v2[20],c;inti,j,w;printf("请输入城市数:");scanf("%d",&G.vexnum);printf("");printf("请输入%d
