简单路径问题

-.z.背景简单路径：如果一条路径上的顶点除了起点和终点可以一样外，其它顶点均不一样，则称此路径为一条简单路径。问题描述假设用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。试设计一个找路程序，获取两个城市之间的所有简单路径。一．需求分析1.根本要求输入参数：结点总数，结点的城市编号〔3位长的数字，〕，连接城市的高速公路〔用高速公路连接的两个城市编号标记〕。输入要求取所有简单路径的两个城市编号。将所有路径〔有城市编号组成〕输出到用户指定的文件中。2.输入输出格形式：输入：(1)要求用户先输入结点总数〔总城市数n〕，再输入代表城市的编号〔三位数字〕。(2)屡次输入两个城市编号来确定城市之间的高速公路〔最多输入n(n-1)/2次〕。(3)输入两个城市的编号来获取简单路径。输出：两点中所有的简单路径。。3测试数据 输入 节点数：5 城市编号：001002003004005006路径： 001002001003002003002004003005004006005006查找路径： 00010005输出001-->003-->005001-->002-->003-->005001-->002-->004-->006-->005001-->003-->002-->004-->006->005二、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的每次输入，根据输入建立一个无向图，用基于深度优先搜索的方法找出简单路径。图的ADT设计：数据对象：Graph=(V,R) 数据关系：VR＝{<v,w>|v,w∈V且P(v,w)} <v,w>表示从v到w的一条弧，并称v为弧头，w为弧尾。 谓词P(v,w)定义了弧<v,w>的意义或信息。根本操作：classGraph{ //图的定义类public:intGetVe*Num()//获得图中顶点的个数 intLocate_Ve*(stringv)//获得顶点在图中的位置 voidDFS_Traverse()//深度优先搜索图};算法的根本思想对于用户想要查找路径的两个顶点，创立一个用于记录路径的数组，路径长度为0。以其中一个顶点为起点，访问该顶点，将该顶点参加路径，访问下一个未被访问的顶点，将其参加路径，并将路径长度加1。假设该顶点为终点，将该路径输出，然后从路径中删除该顶点，并将路径长度减1，访问下一个未被访问的顶点。假设不为终点，则访问下一个未被访问的顶点，直到路径长度不小于顶点个数。程序的流程程序由三个模块组成：(1)建图模块：完成顶点数，边数和顶点关系〔路径〕的输入，并依此建立一个无向图。(2)遍历模块：深度优先遍历图并打印与屏幕上，还可以在查找模块中被调用进展简单路径的查找。(3)查找模块：基于DFS的思想进展两点之间固定路径长度简单路径的查找，所以需要被调用N次〔N为图顶点数减一〕以完成所有简单路径查找并输出与屏幕上。三、详细设计物理数据类型顶点上存储的应为该城市的编码〔为三位数字〕，可以用三位的字符数组来存储，并检查是否属于字符的0~9。边上应存储有两城市之间路径长度〔此题只需求简单路径，所以全部设为1〕，无路径则设为-1。以整型数来存储。深度优先遍历图的伪代码：voidDFS_Traverse()//深度优先遍历图，将所有顶点定义为未访问{for(inti=0;i<ve*num;i++)visited[i]=false;for(i=0;i<ve*num;i++)if(!visited[i])DFS(i);}构造无向图的伪代码voidCreate_NDGraph()//构造无向图{stringv1,v2;inti,j,k;cout<<"输入顶点数和边数：";cin>>ve*num>>arum;while(ve*num>20)//提示顶点个数的限制{cout<<"请输入少于20个顶点(重新输入顶点数和边数)：";cin>>ve*num>>arum;}cout<<"输入顶点名称：";for(i=0;i<ve*num;i++)//顶点赋值，并将顶点的第一条边设置为空{ cin>>vertices[i].data;vertices[i].firstarc=NULL; if(i>0) //第二次输入时检查是否输入了和之前输入一样的顶点 { for(j=0;j<i;j++) if(vertices[i].data==vertices[j].data) //如果一样，提示重新输入 { cout<<"输入重复的顶点：--"<<vertices[i].data<<"--请重新输入："; i--; } }}for(k=0;k<arum;k++)//屡次输入两个顶点来构造边{cout<<"输入每条边对应的两个顶点：";cin>>v1>>v2;i=Locate_Ve*(v1);j=Locate_Ve*(v2);while(i==-1||j==-1||i==j)//当连个顶点中有一个不存在与该图中或两个顶点位于同一位置{cout<<"顶点中有不符合要求的，请重新输入：";cin>>v1>>v2;i=Locate_Ve*(v1);j=Locate_Ve*(v2);} //将i和j连接起来Arode*p=newArode;p->adjve*=j;p->ne*tarc=vertices[i].firstarc;vertices[i].firstarc=p;//置对称边Arode*q=newArode;q->adjve*=i;q->ne*tarc=vertices[j].firstarc;vertices[j].firstarc=q;}cout<<"无向图构造完成"<<endl;}深度搜索路径的伪代码voidDFS(intv){visited[v]=true;cout<<vertices[v].data<<"";Arode*p;intw;for(p=vertices[v].firstarc;p;p=p->ne*tarc){w=p->adjve*;if(!visited[w])DFS(w);}}打印出所有简单路径的伪代码：voidPrint_*_Y_Path(intu,intv,intd)//求出所有从u到v的路径，d刚进来的时候是-1{intm;d++;visited[u]=true;path[d]=u;if(u==v)//找到一条路径，输出该路径{for(inti=0;i<d;i++)cout<<vertices[path[i]].data<<"-->";cout<<vertices[path[i]].data<<endl;}else{Arode*p=vertices[u].firstarc;//继续DFSwhile(p){m=p->adjve*;if(!visited[m])//如果该顶点未被访问过Print_*_Y_Path(m,v,d);p=p->ne*tarc;}}//恢复环境，使顶点可重新使用//路径长度减一 visited[u]=false;d--; }};算法的具体步骤对于用户想要查找路径的两个顶点，创立一个用于记录路径的数组，路径长度为0。以其中一个顶点为起点，访问该顶点，将该顶点参加路径，访问下一个未被访问的顶点，将其参加路径，并将路径长度加1。假设该顶点为终点，将该路径输出，然后从路径中删除该顶点，并将路径长度减1，访问下一个未被访问的顶点。假设不为终点，则访问下一个未被访问的顶点，直到路径长度不小于顶点个数。当输入的顶点不在图中则提示错误。算法的时空分析算法基于DFS实现，运行次数和找到的路径数有关，假设找到的路径数为0，则时间代价为，假设找到的路径为N，则时间代价为。输入输出格式：cout<<〞请输入节点数：〞cin>>cout<<〞输入城市编号：〞cin>>cout<<〞请输入路径：〞<<endl;cin>>//路径cout<<〞请输入查找的路径：〞cin>>>>cout<<〞输出所有的简单路径〞四结果截图五附录〔代码〕#include<iostream>#include<string>usingnamespacestd;classGraphm{//Implementadjacencymatri*private: intnumVerte*,numEdge;//Storenumberofverticesedges int**matri*;//Pointertoadjacencymatri* int*mark;//Pointertomarkarraypublic: Graphm(intnumVert) {//Makegraphw/numVertvertices inti; numVerte*=numVert; numEdge=0; mark=newint[numVert];//Initializemarkarray for(i=0;i<numVerte*;i++) mark[i]=0; matri*=(int**)newint*[numVerte*];//Makematri* for(i=0;i<numVerte*;i++) matri*[i]=newint[numVerte*]; for(i=0;i<numVerte*;i++)//Edgesstartw/0weight for(intj=0;j<numVerte*;j++)matri*[i][j]=0; } intfirst(intv) {//Returnv'sfirstneighbor inti; for(i=0;i<numVerte*;i++) if(matri*[v][i]!=0)returni; returni;//Returnnifnone } intne*t(intv1,intv2) { //Getv1'sneighborafterv2 inti; for(i=v2+1;i<numVerte*;i++) if(matri*[v1][i]!=0)returni; returni; } intn() { returnnumVerte*; } inte() { returnnumEdge; } //Setedge(v1,v2)towgt voidsetEdge(intv1,intv2,intwgt) { if(wgt<0)cout<<"Illegalweightvalue"<<endl; if(matri*[v1][v2]==0)numEdge++; matri*[v1][v2]=wgt; } voiddelEdge(intv1,intv2){//Deleteedge(v1,v2) if(matri*[v1][v2]!=0)numEdge--; matri*[v1][v2]=0; } intweight(intv1,intv2){returnmatri*[v1][v2];} intgetMark(intv){returnmark[v];} voidsetMark(intv,intval){mark[v]=val;}};voidPathAll(Graphm*G,intu,intv,int*path,string*str,int&d)//d是到当前为止已走过的路径长度，调用时初值为-1{ intw,i; G->setMark(u,1); d++; //路径长度增1 path[d]=u; //将当前顶点添加到路径中 if(u==v&&d>=1) //输出一条路径 { cout<<"这两个城市间一条的简单路径为:"; for(i=0;i<=d;i++) cout<<str[path[i]]<<""; cout<<endl; } for(w=G->first(u);w<G->n();w=G->ne*t(u,w)) { if(G->getMark(w)==0) PathAll(G,w,v,path,str,d); } G->setMark(u,0);//恢复，可以再寻找 d--;//去掉这个点}intmain(){ intn; string*str; int*path; cout<<"输入城市个数："; cin>>n; GraphmG(n); str=newstring[n]; path=newint[n]; cout<<"输入所有城市编号！"<<endl; for(inti=0;i<n;i++) { cin