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

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

背景

简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径。

问题描述

若用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。试设计一个找路程序，获取两个城市之间的所有简单路径。

基本要求

（1） 输入参数：结点总数，结点的城市编号（4位长的数字，例如电话区号，长沙

是0731），连接城市的高速公路（用高速公路连接的两个城市编号标记）。

（2） 输入 要求取所有简单路径的两个城市编号。

（3） 将所有路径（有城市编号组成）输出到用户指定的文件中。

实现提示

基于DFS的思想。

一、需求分析

城市分布不均，且无向，两个城市之间有路连接，根据特点，可以抽象成一个无向图，城市为各点，高速路为边。按照用户的输入建立一个邻接表，输出两个点的所有路径。

(1) 输入的形式和输入值的范围：本程序要求首先输入一个正整数值N，代表城市总数，然后依次输入城市的代号，可以用四位数字表示。因此，用整数来存储。

(2) 输出的形式：根据输入的数据，进行输入，若能成功，则将所有序列输出，若不能成功，则提示报错。

(3) 程序所能达到的功能：程序要求能够识别输入城市编号列表，高速公路，需要查找路径的两个城市时的错误，能够判断输入的两个城市之间是否存在路径，如果存在路径要求能够将路径输出。

二、概要设计

因为所有顶点的特征一致，并且顶点和其他的多个顶点间可能存在联系，由此顶点之间存在一个网状结构，顶点间的联系与方向无关，所以用一个无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路，数据的对象是图中的每一个顶点和无向边。由此为本问题确定一个图的数据关系。

1.抽象数据类型

图的ADT

数据对象：V,R（图是由一个顶点集 V 和一个弧集 R构成的数据结构）

数据关系：Graph = (V,R) VR＝{<v,w>|v,w∈V且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 int[numVert]; //初始化标志数组

} for(i=0;i<numVertex;i++) mark[i]=0; //每一个顶点的标志值初始化为0 matrix =(int**) new int*[numVertex]; for(i=0;i<numVertex;i++) matrix[i]=new int[numVertex]; //构建一个相邻矩阵 for(i=0;i<numVertex;i++) for(j=0;j<numVertex;j++) matrix[i][j]=0;

2. 有向图的销毁

~Graphm()

{

delete []mark;

for(int i=0;i<numVertex;i++)

delete [] matrix[i];

delete [] matrix; //销毁相邻矩阵

}

3. 获取第一个邻居

int first(int v) //返回该点的第一条邻边

{

int i;

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

if(matrix[v][i]!=0) return i; //当顶点和顶点i有边时，返回顶点i的值 return i;

}

int next(int v1,int v2) //获得v1的邻居v2

{

int i;

for(i=v2+1;i<numVertex;i++)

if(matrix[v1][i]!=0) return i;

return i;

}

4. 其他基本操作

void setEdge(int v1,int v2) //设置无向图的边

{

if(matrix[v1][v2]==0)

numEdge++;

matrix[v1][v2]=1;

}

int getMark(int v) //获取顶点标记的值

{return mark[v];}

int setMark(int v,int val) //设置访问的标记值

{mark[v]=val;}

(二) 获得顶点的下标的函数

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

每次要获得顶点对应的下标时，用顶点与数组中数据逐个比较，在相等时返回该值的下标。 int getNum(int *vert,int n,int s)

{

for(int i=0;i<n;i++){

if(vert[i]==s) //如果顶点s等于数组vert[i]的值

return 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<<path[i]<<"-->"; //输出该条路径

cout<<endl;

}

for (w=G.first(n);w<G.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 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|2)，查找设共计访问的结点次数为k，则易知函数的时间开 销为 (k)。

输入和输出的格式

输入

输入城市数量

输入城市编号

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

{ cout<<"每个城市的区号(四位)："<<endl;

cin>>v[i]; }

输入之间有高速公路连接的城市编号：

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<<"输入不同两个城市的边的关系，区号用空格隔开："<<endl; cin>>v1>>v2; }

输入要查找的两个城市之间的路：

cout<<"输入要查找路径的两个城市区号："<<endl;

cin>>v1>>v2;

输出

1. 有简单路径

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

{

cout<<"这两个城市间一条的简单路径为:";

flag=1;

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

cout<<path[i]<<"-->"; //输出该条路径

}

2. 没有路径

if(f==0)

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

本文来源：https://www.bwwdw.com/article/e83i.html