数据结构 无向图中求两点间所有简单路径 实验6报告

为了方便表示对应顶点在相邻矩阵的位置关系，用一个整型数组存储顶点的值(城市编号)，所以存储顶点的数组的下标可以用来映射为顶点构建的相邻矩阵的下标。

每次要获得顶点对应的下标时，用顶点与数组中数据逐个比较，在相等时返回该值的下标。

int getNum(int *vert,int n,int s) { for(int i=0;i

(三) DFS找到所有简单路径函数

从起始的城市对应的顶点开始，每访问一个顶点时，将其存入数组，标记值设为1，逐次访问其邻接顶点。 如果被访问的点在其此次所在的路径中之前已被访问，或该顶点没有邻接顶点了且该顶点不是目的顶点，则返回上一个顶点置为0，继续查找其他邻接点。

如果该顶点是目的顶点，则将该条路径此次访问的存储顶点的数组输出，输出该条简单路径。 之后将上一个顶点置为0，观察是否还有其余邻点，如果有继续查找，如果没有，则返回上一个顶点，置为0，继续用DFS查找简单路径。

设置一个标志变量flag，赋初值为0，当输出一次简单路径时，flag变为1。如果DFS结束后flag仍为0，那么输出没有找到简单路径。

int DFS_all(Graphm G,int u,int v,int *path,int &d,int *vert，int &flag)//d为已走过的路径长度

{ int w,i,n,v1,temp; //设置一个标志变量flag n=getNum(vert,G.n(),u); //根据顶点获得下标值 v1=getNum(vert,G.n(),v); //根据顶点获得下标值 G.setMark(n,1); //该顶点标记为1 d++; path[d]=u; if (n==v1&&d>=1) //当该点为目的顶点并且路径大于等于一 { cout<<\这两个城市间一条的简单路径为:\ flag=1; for (i=0;i<=d;i++) cout<

return flag; }

算法的具体步骤

开始输入顶点个数n用顶点创建n*n矩阵T.CreatGraphm(n); flag=0;输入有边的顶点v1,v2(v1!=0&&v2!=0)?T.setEdge(v1,v2); T.setEdge(v2,v1);输入查找的顶点v1,v2DFS_allpath(T,v1,v2,path,d,v,f);flag==0？没有路径！结束输出路径

设置一个标志变量flag，赋初值为0，当有一条简单路径输出时，flag变为1。如果DFS结束后flag仍为0，那么输出没有找到简单路径。 如图伪代码实现如下： Graphm T; int v[100],path[100]; int flag=0,d=-1; //标志变量flag cout<<\输入城市数量：\ cin>>n; 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|×|V|矩阵，所以邻接矩阵的空间代价为Θ(|V|^2)，对于有n个顶点的和E条弧的无向图而言，DFS对每条边分别沿两个方向进行处理，且每个顶点必须被访问一次，所以总的时间代价为Θ(|V|+|E|) 。 综上可知，该程序的时间复杂度为Max（Θ(|V|^2)，Θ(|V|+|E|)）。 输入和输出的格式 输入：

1. 输入城市的编号

for(i=0;i

{ cout<<\每个城市的区号(四位)：\ cin>>v[i]; } 2. 输入查找的城市编号 cout<<\输入要查找路径的两个城市区号：\

cin>>v1>>v2;

3. 输入不同两个城市的边的关系

cin>>v1>>v2;

while((v1!=0)&&(v2!=0)) { n1=getNum(v,n,v1); n2=getNum(v,n,v2); T.setEdge(n1,n2); T.setEdge(n2,n1); cout<<\输入不同两个城市的边的关系，区号用空格隔开：\ cin>>v1>>v2; }

输出：

1. 有简单路径

if (n==v1&&d>=1) {

cout<<\这两个城市间一条的简单路径为:\ flag=1;

for (i=0;i<=d;i++)

cout<

}

2. 没有路径 if(f==0)

cout<<\查找的两城市间没有简单路径！\

四、测试数据

1． 有路径，输入的图如下：

2000100040003000 运行结果，

2． 没有简单路径，输入图如下：

10002000 运行结果，