《湖南大学数据结构DFS简单路径问题预习报告》由会员分享，可在线阅读，更多相关《湖南大学数据结构DFS简单路径问题预习报告（7页珍藏版）》请在装配图网上搜索。
1、HUNANUNIVERSITY课程实习报告题目：简单路径问题学生姓名学生学号专业班级指导老师李晓鸿完成日期背景简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径。问题描述若用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。试设计一个找路程序，获取两个城市之间的所有简单路径。基本要求（1）输入参数：结点总数，结点的城市编号（4位长的数字，例如电话区号，长沙是0731），连接城市的高速公路（用高速公路连接的两个城市编号标记）。（2）输入要求取所有简单路径的两个城市编号。（3）将所有路径（有城市编号组成）输出到用户指定的文件中。实现提
2、示基于DFS的思想。一、需求分析城市分布不均，且无向，两个城市之间有路连接，根据特点，可以抽象成一个无向图，城市为各点，高速路为边。按照用户的输入建立一个邻接表，输出两个点的所有路径。（1）输入的形式和输入值的范围：本程序要求首先输入一个正整数值N,代表城市总数，然后依次输入城市的代号，可以用四位数字表示。因此，用整数来存储。（2）输出的形式：根据输入的数据，进行输入，若能成功，则将所有序列输出，若不能成功，则提示报错。（3）程序所能达到的功能：程序要求能够识别输入城市编号列表，高速公路，需要查找路径的两个城市时的错误，能够判断输入的两个城市之间是否存在路径，如果存在路径要求能够将路径输出。二
3、、概要设计抽象数据类型ADT图数据对象：V,R（图是由一个顶点集V和一个弧集R构成的数据结构）数据关系：Graph=（V,R）VR=|v,wV且P（v,w）基本操作：1. intn()=0;/返回图节点数inte()=0;/返回图边数intfirst(int)=0;/返回该节点的第一条邻边voidsetEdge(intv1,intv2)/加边intnext(int,int)=0;/返回下一条邻边intgetMark(int)=0;/有标记吗voidsetMark(int,int)=0;/设置标记程序的流程程序主要由四个步骤组成：1) 输入城市总数输入正确的城市编号列表输入所有的有高速公路直接连
4、接的城市对编号循环输入需要寻找路径的城市对的编号寻找它们之间的所有简单路径。算法的基本思想(1)程序需要输入城市编号及城市的编号对以实现城市间的高速公路的输入。然后输入某两个城市，得出城市间的所有简单路径。得到无向图中某两个城市间的简单路径，考虑使用基于深度优先思想，通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。2)图的存储：用邻接矩阵来存储三、详细设计(1)图的存储：用邻接矩阵来存储:根据输入的顶点个数N创建一个N*N的矩阵，将其全部赋初值。然后根据边的情况来输入对应边的位置。classGraphm:publicGraphprivate:intnumVertex,numEdge
5、;int*matrix;int*mark;public:Graphm(intnumVert)inti,j;numVertex=numVert;numEdge=0;mark=newintnumVert;for(i=0;inumVertex;i+)marki=UNVISITED;matrix=(int*)newint*numVertex;for(i=0;inumVertex;i+)matrixi=newintnumVertex;for(i=0;inumVertex;i+)for(intj=0;jsetMark(u,1);d+;/pathd=u;if(u=v&d=1)路径长度增1/将当前顶点添加到路
6、径中/输出一条路径cout这两个城市间一条的简单路径为:for(i=0;i=d;i+)coutstrpathi;coutfirst(u);wn();w=G-next(u,w)if(G-getMark(w)=0)PathAll(G,w,v,path,str,d);G-setMark(u,0);/恢复，可以再寻找d-;/去掉这个点（3）图的基本操作返回结点的第一条邻边。由于用邻接矩阵来存储，当下标0时，就找到了邻边。成功就返回邻边的位置。intfirst（intv）matrixvi不等于inti;for(i=0;inumVertex;i+)if(matrixvi!=0)returni;return
7、i;返回下一条邻边。当下标matrixvi不等于0时，就找到了邻边。成功就返回邻边的位置。intnext(intv1,intv2)inti;for(i=v2+1;inumVertex;i+)if(matrixv1i!=0)returni;returni;加边。传入结点，若该边不存在，则结点数+1，并添加该边。voidsetEdge(intv1,intv2)if(matrixv1v2=0)numEdge+;matrixv1v2=1;获取结点的个数。直接返回个数。intn()returnnumVertex;获取边的数量。直接返回边的数量。inte()returnnumEdge;算法的时空分析邻接矩
8、阵的空间代价为(|V|2)，查找设共计访问的结点次数为k,则易知函数的时间开销为?(k)。函数的调用关系图厂提示用户输入城市总数输入城市代号超找城市之间的路径输出(4) 输入和输出的格式输入请输入城市数量等待输入请输入城市编号0001请输入城市编号0002请输入城市编号0003城市编号列表输入完毕！请输入之间有高速公路连接的城市编号cl和C2:00010002请输入要查找的两个城市之间的路等待输入输出从cl到c2之间的路为：四、用户使用说明(可选)1、本程序的运行环境为DOS操作系统，执行文件为conversion.exe2、运行程序时输入请输入城市数量等待输入请输入城市编号0001请输入城市编号0002请输入城市编号0003城市编号列表输入完毕！请输入之间有高速公路连接的城市编号c1和c2：00010002请输入要查找的两个城市之间的路等待输入输出从c1到c2之间的路为：等待输入请输入城市编号0001请输入城市编号0002请输入城市编号0003城市编号列表输入完毕！请输入之间有高速公路连接的城市编号c1和c2：00010002请输入要查找的两个城市之间的路等待输入输出从c1到c2之间的路为:
湖南大学数据结构DFS简单路径问题预习报告
