求无向图中求两点间的所有简单路径实验报告

HUNANUNIVERSITY课程实验报告题目：求无向图中求两点间的所有简单路径学生姓名：学生学号：专业班级：指导老师：完成日期：一．需求分析输入形式本程序要求用户首先输入一个结点总数，然后输入结点的城市编号（4位长的数字，例如电话区号，长沙是0731）,以及高速公路连接的两所城市（用高速公路连接的两个城市编号标记），最后输入要查询所有简单路径的两座城市的名称。当用户输入不合法时，提示用户输入有误，并重新输入。输入具体格式如下：请输入城市总数：请输入高速公路的条数：请依次输入城市名称：请输入高速公路连接的两座城市：请输入需查询所有路径的两所城市的名称：输出形式从xx到xx的所有路径如下：将所有路径（城市编号组成）存至用户指定的文件中。程序功能该程序可以通过构建一个图用来表示各个城市之间是否有高速公路连通的关系，可以实现查询两城市间所有路径的功能测试数据①请输入城市总数：3请依次输入城市编号：000100020003有几对城市间有高速公路？3请输入第一对连接城市的高速公路：00010002请输入第二对连接城市的高速公路：00020003请输入第三对连接城市的高速公路：00010003请输入请输入需查询所有路径的两所城市的名称：00010003从城市0001到0003的所有简单路径如下：001-003001-002-003所有路径已存入文件中。②请输入城市总数：3请依次输入城市编号：001002003有几对城市间有高速公路？2请输入第一对连接城市的高速公路：001002请输入第二对连接城市的高速公路：002003请输入请输入需查询所有路径的两所城市的名称：00010003从城市0001到0003的所有简单路径如下：001-002-003所有路径已存入文件中。③请输入城市总数：3请依次输入城市编号：001002003有几对城市间有高速公路？0请输入请输入需查询所有路径的两所城市的名称：00010003从城市0001到0003的无简单路径④请输入城市总数：4请依次输入城市编号：001002003004有几对城市间有高速公路？5请输入第一对连接城市的高速公路：001002请输入第二对连接城市的高速公路：002003请输入第三对连接城市的高速公路：003004请输入第四对连接城市的高速公路：001004请输入第五对连接城市的高速公路：001003请输入请输入需查询所有路径的两所城市的名称：00010004从城市0001到0003的所有简单路径如下：0001-00040001-0003-00040001-0002-00040001-0002-0003-00040001-0003-0002-0004所有路径已存入文件中。⑤请输入城市总数：-1结束程序二．概要设计抽象数据类型因为各个城市间的是否有高速公路连通的关系是非线性的，而且具有结构网状特性，并且高速公路是无向的，所以选择无向图来表示各个城市间的连通关系。图的ADT设计：数据对象：G=(V,E)，其中V表示顶点集合，E表示边集合数据关系：VR＝{v,w|v,w∈V且P(v,w)}v,w表示从v到w的一条弧，v为弧头，w为弧尾。基本操作：intn();//图中顶点个数inte();//图边数intfirst(int);//该点的第一条临边intnext(int,int);//该点的第二条临边voidsetEdge(int,int,int);//为边设置权值voidsetMark(int,int);//设置该顶点的标志值intgetMark(int);//获得该顶点的标志值图的顶点ADT设计：数据对象：城市编号（占3位的字母数字串）数据关系:{vi|i=1,2,3……n}基本操作：intposition();//获取顶点位置算法基本思想当用户输入完毕后，根据各城市间相应的关系构建一个无向图，并使用一个临接矩阵存储该图。考虑使用基于深度优先思想，在搜素过程中，每当访问一个节点，DFS就会递归访问它的所有未被访问的相邻节点。并通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。最后输出这些路径即可。程序基本流程该程序主要包括四个模块：输入模块：由用户输入城市总数，城市编号，高速公路编号；构建与存储模块：根据用户的输入构建无向图，并使用临接矩阵存储图；访问模块：对该图进行深度优先搜索，得到所有路径；输出模块：输出所有路径。三．详细设计物理数据类型①边的实现：classEdge{public:intvertex,weight;Edge（）{vertex=-1;weight=-1;}Edge(intv,intw){vertex=v;weight=w;}};②图的相邻矩阵实现：classGraphm{private:intnumVertex,numEdge;int**matrix;int*mark;public:Graphm(intnumVert){inti,j;numVertex=numVert;//顶点数numEdge=0;mark=newint[numVert];for(i=0;inumVertex;i++)mark[i]=0;//每一个顶点的标志值初始化为0matrix=(int**)newint*[numVertex];for(i=0;inumVertex;i++)matrix[i]=newint*[numVertex];for(i=0;inumVertex;i++)for(j=0;jnumVertex;j++)matrix[i][j]=0;}~Graphm(){delete[]mark;for(inti=0;inumVertex;i++)delete[]matrix[i];delete[]matrix;}//析构函数intn(){returnnumVertex;}//顶点个数intfirst(intv)//该顶点的第一条邻边{inti;for(i=0;inumVertex;i++)if(matrix[v][i]!=0)returni;returni;}intnext(intv1,intv2)//获得v1的邻居v2{inti;for(i=v2+1;inumVertex;i++)if(matrix[v1][i]!=0)returni;returni;}voidsetEdge(intv1,intv2)//设置有向图的边{if(matrix[v1][v2]==0)numEdge++;matrix[v1][v2]=1;}intgetMark(intv)//获取顶点标记的值{returnmark[v];}intsetMark(intv,intval)//设置访问的标记{mark[v]=val;}}③DFS的实现：voidDFS（Graph*G,intv）{PreVisit(G,v);G-setMark(v,1);for(intw=G-first(v);wG-n();w=G-next(v,w))if(G-getMark(w)==0)DFS(G,w);PostVisit(G,v);}算法具体步骤根据用户的输入，构建一个无向图，并使用一个临接矩阵存储该图。对该图进行深度优先搜索，并通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。得到所有路径后，输出这些路径即可。函数调用关系输入建图与存图临接矩阵存储主程序DFS搜索输出算法时空分析在表的存储中，临接矩阵的时间代价是Θ（|V2|）,而在无向图中，DFS从两个方向处理每条边，每个顶点都必须被访问，且只能被访问一次，因此时间代价是Θ（|V|+|E|）。所以该算法总时间代价是Θ（|V|2）。输入输出格式输入：cincityNum;for(inti=0;icityNum;i++)cincity[i];cinroadNum;for(i=0;iroadNum;i++){cinroadName;}请输入城市总数：3请依次输入城市编号：001002003有几对城市间有高速公路？3请输入第一对连接城市的高速公路：001002请输入第二对连接城市的高速公路：002003请输入第三对连接城市的高速公路：001003请输入要查询路径的两座城市编号：001003输出：001到003的所有路径如下：001-003001-002-003所有路径已存入文件中。四．调试分析在实际编程中，程序曾陷入过死循环，尝试了一些方法仍然没有解决，最后使用了goto语句才解决了这个问题五．测试结果六．用户使用说明1.该程序可以通过构建一个有向图来实现查找两城市间的所有简单路径的功能；2.使用该程序时，首先按照要求输入各类参数，若输入有误，系统提示输入有误，并重新输入；3.最后的结果将直接输出在DOS界面。七．实验心得通过该实验，我掌握了图的深度优先搜索的方法代码：graph.h文件：#includeiostream#includestring#includequeueusingnamespacestd;boolvisited[100];intpath[100];classArcNode{public:intadjvex;ArcNode*nextarc;};classVexNode{public:stringdata;ArcNode*firstarc;};classGraph{private:VexNodevertices[100];intvexnum;intarcnum;public:Graph(){vexnum=0;arcnum=0;}~Graph(){delete[]vertices;}intgetArcnum(){returnarcnum;}intGetVexNum(){returnvexnum;}intPosition(stringv){for(inti=0;ivexnum;i++)if(vertices[i].data==v)returni;return-1;}voidBuild_Graph(){//构造无向图stringv1,v2;inti,j,k;cout输入城市个数：;cinvexnum;cout请输入高速公路的条数：;cinarcnum;cout输入城市名称：;for(i=0;ivexnum;i++){cinvertices[i].data;vertices[i].firstarc=NULL;}for(k=0;karcnum;k++){cout输入每条高速公路连接的两座城市：;cinv1v2;i=Position(v1);j=Position(v2);while(i==-1||j==-1){cout输入有误，请重新输入：;cinv1v2;i=Position(v1);j=Position(v2);}ArcNode*p=newArcNode;p-adjvex=j;p-nextarc=vertices[i].firstarc;vertices[i].firstarc=p;//置对称边ArcNode*q=newArcNode;q-adjvex=i;q-nextarc=vertices[j].firstarc;vertices[j].firstarc=q;}}voidPrint_Road(intu,intv,intl,intd){//求出一条长度为l的从u到v的路径inti=0;intm;d++;visited[u]=true;path[d]=u;if(u==v&&d==l){for(i=0;il;i++)coutvertices[path[i]].data--;coutvertices[path[i]].dataendl;}elseif(u==v&&d!=l){//出现这种情况直接回溯上一顶点gotoloop;}ArcNode*p=vertices[u].firstarc;while(p){m=p-adjvex;if(!visited[m])Print_Road(m,v,l,d