实验6无向图中求两点间的所有简单路径.doc

实验6无向图中求两点间的所有简单路径背景简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径。问题描述若用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。试设计一个找路程序，获取两个城市之间的所有简单路径。基本要求（1） 输入参数：结点总数，结点的城市编号（4位长的数字，例如电话区号，长沙是0731），连接城市的高速公路（用高速公路连接的两个城市编号标记）。（2） 输入 要求取所有简单路径的两个城市编号。（3） 将所有路径（有城市编号组成）输出到用户指定的文件中。实现提示基于DFS的思想。一、需求分析城市分布不均，且无向，两个城市之间有路连接，根据特点，可以抽象成一个无向图，城市为各点，高速路为边。按照用户的输入建立一个邻接表，输出两个点的所有路径。(1) 输入的形式和输入值的范围：本程序要求首先输入一个正整数值N，代表城市总数，然后依次输入城市的代号，可以用四位数字表示。因此，用整数来存储。(2) 输出的形式：根据输入的数据，进行输入，若能成功，则将所有序列输出，若不能成功，则提示报错。(3) 程序所能达到的功能：程序要求能够识别输入城市编号列表，高速公路，需要查找路径的两个城市时的错误，能够判断输入的两个城市之间是否存在路径，如果存在路径要求能够将路径输出。二、概要设计 因为所有顶点的特征一致，并且顶点和其他的多个顶点间可能存在联系，由此顶点之间存在一个网状结构，顶点间的联系与方向无关，所以用一个无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路，数据的对象是图中的每一个顶点和无向边。由此为本问题确定一个图的数据关系。1.抽象数据类型图的ADT数据对象：V,R（图是由一个顶点集 V 和一个弧集 R构成的数据结构）数据关系：Graph = (V,R) VR|v,wV且P(v,w)基本操作： int n() =0; / 返回图节点数int e() =0; /返回图边数int first(int)=0;/返回该节点的第一条邻边void setEdge(int v1, int v2)/加边int next(int, int) =0; /返回下一条邻边int getMark(int) =0;/有标记吗void setMark(int, int) =0;/设置标记2.算法的基本思想（1）首先将图中每个顶点的访问标志初始化为0，每访问一个点，则访问标记改为1。 从图中给定的顶点V 出发，访问此顶点，然后依次从V的各个未被访问的邻接点出发深度优先搜索遍历图，每访问一个顶点，访问标记为1，把该点存入数组中，直至在图中遍历到和V有路径相通的目标顶点V0，输出该条简单路径。如果此次路径访问的顶点已经被访问，将上一个顶点访问标志设为0，继续访问其余邻接点，如果没有邻接点，则返回上一个顶点，将访问标志设为0，继续用DFS查找简单路径。如果算法结束，没有简单路径输出，那么输出没有简单路径（2）图的存储：用邻接矩阵来存储3.程序的流程 （1） 初始化模块：输入城市数量，再输入相应城市编号及相邻城市间的通路路径， 构建一个邻接矩阵来初始化一个无向图。 （2） DFS模块：对无向图进行深度优先搜索，查找的两顶点之间若存在通路时的所 有简单路径。 （3） 输出模块：若两城市(顶点)间存在通路，那么输出所有的简单路径。否则，输 出没有简单路径，结束程序。 三、详细设计图的存储：用邻接矩阵来存储:根据输入的顶点个数N创建一个N*N的矩阵，将其全部赋初值。然后根据边的情况来输入对应边的位置。(一) 无向图的基本操作 (邻接矩阵)1. 初始化一个有向图Graphm(int numVert)int i,j;numVertex = numVert; /顶点数numEdge=0;mark=new intnumVert; /初始化标志数组 for(i=0;inumVertex;i+) marki=0; /每一个顶点的标志值初始化为0 matrix =(int*) new int*numVertex; for(i=0;inumVertex;i+) matrixi=new intnumVertex; /构建一个相邻矩阵 for(i=0;inumVertex;i+) for(j=0;jnumVertex;j+) matrixij=0;2. 有向图的销毁Graphm()delete mark;for(int i=0;inumVertex;i+)delete matrixi;delete matrix; /销毁相邻矩阵3. 获取第一个邻居int first(int v) /返回该点的第一条邻边int i;for(i=0;inumVertex;i+)if(matrixvi!=0) return i; /当顶点和顶点i有边时，返回顶点i的值 return i;int next(int v1,int v2) /获得v1的邻居v2int i;for(i=v2+1;inumVertex;i+)if(matrixv1i!=0) return i;return i;4. 其他基本操作void setEdge(int v1,int v2) /设置无向图的边if(matrixv1v2=0)numEdge+;matrixv1v2=1;int getMark(int v) /获取顶点标记的值return markv;int setMark(int v,int val) /设置访问的标记值markv=val;(2) 获得顶点的下标的函数为了方便表示对应顶点在相邻矩阵的位置关系，用一个整型数组存储顶点的值(城市编号)，所以存储顶点的数组的下标可以用来映射为顶点构建的相邻矩阵的下标。每次要获得顶点对应的下标时，用顶点与数组中数据逐个比较，在相等时返回该值的下标。int getNum(int *vert,int n,int s)for(int i=0;i=1) /当该点为目的顶点并且路径大于等于一cout这两个城市间一条的简单路径为:;flag=1;for (i=0;i=d;i+)coutpathi; /输出该条路径coutendl;for (w=G.first(n);wG.n();w=G.next(n,w) /继续查找该顶点的相邻顶点if (G.getMark(w)=0)temp=DFS_all(G,w,v1,path,d,vert,flag);G.setMark(n,0);/恢复，可以再寻找d-;return flag;算法的具体步骤设置一个标志变量flag，赋初值为0，当有一条简单路径输出时，flag变为1。如果DFS结束后flag仍为0，那么输出没有找到简单路径。 如图伪代码实现如下： Graphm T; int v100,path100; int flag=0,d=-1; /标志变量flag coutn; T.CreatGraphm(n); /构建一个n*n的矩阵存放图 /获得城市编号 /输入不同两个城市的边的关系while(v1!=0)&(v2!=0)T.setEdge(n1,n2); /无向图中，两顶点间边的关系对称T.setEdge(n2,n1); /从不同顶点设置两次边/输入查找的城市编号flag =DFS_all(T,v1,v2,path,d,v,f);if(flag =0)/输出没有路径算法的时空分析邻接矩阵的空间代价为(|V|2)，查找设共计访问的结点次数为k，则易知函数的时间开 销为(k)。输入和输出的格式输入输入城市数量输入城市编号for(i=0;in;i+) cout每个城市的区号(四位)：vi; 输入之间有高速公路连接的城市编号：cinv1v2;while(v1!=0)&(v2!=0) n1=getNum(v,n,v1);n2=getNum(v,n,v2);T.setEdge(n1,n2);T.setEdge(n2,n1);cout输入不同两个城市的边的关系，区