简单路径问题.docx
《简单路径问题.docx》由会员分享，可在线阅读，更多相关《简单路径问题.docx（15页珍藏版）》请在冰点文库上搜索。
简单路径问题
背景
简单路径：
如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径。
问题描述
若用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。
试设计一个找路程序，获取两个城市之间的所有简单路径。
一．需求分析
1.基本要求
（1）输入参数：
结点总数，结点的城市编号（3位长的数字，），连接城市的高速公路（用高速公路连接的两个城市编号标记）。
（2）输入要求取所有简单路径的两个城市编号。
（3）将所有路径（有城市编号组成）输出到用户指定的文件中。
2.输入输出格形式：
输入：
（1）要求用户先输入结点总数（总城市数n），再输入代表城市的编号（三位数字）。
（2）多次输入两个城市编号来确定城市之间的高速公路（最多输入n（n-1）/2次）。
（3）输入两个城市的编号来获取简单路径。
输出：
两点中所有的简单路径。
。
3测试数据
输入
节点数：
5城市编号：
001002003004005006
路径：
001002
001003
002003
002004
003005
004006
005006
查找路径：
00010005
输出
001-->003-->005
001-->002-->003-->005
001-->002-->004-->006-->005
001-->003-->002-->004-->006->005
二、概要设计
抽象数据类型
为实现上述程序的功能，应以整数存储用户的每次输入，根据输入建立一个无向图，用基于深度优先搜索的方法找出简单路径。
图的ADT设计：
数据对象：
Graph=（V,R）
数据关系：
VR＝{|v,w∈V且P（v,w）}
表示从v到w的一条弧，并称v为弧头，w为弧尾。
谓词P（v,w）定义了弧的意义或信息。
基本操作：
classGraph{//图的定义类
public:
intGetVexNum（）//获得图中顶点的个数
intLocate_Vex（stringv）//获得顶点在图中的位置
voidDFS_Traverse（）//深度优先搜索图
};
算法的基本思想
对于用户想要查找路径的两个顶点，创建一个用于记录路径的数组，路径长度为0。
以其中一个顶点为起点，访问该顶点，将该顶点加入路径，访问下一个未被访问的顶点，将其加入路径，并将路径长度加1。
若该顶点为终点，将该路径输出，然后从路径中删除该顶点，并将路径长度减1，访问下一个未被访问的顶点。
若不为终点，则访问下一个未被访问的顶点，直到路径长度不小于顶点个数。
程序的流程
程序由三个模块组成：
（1）建图模块：
完成顶点数，边数和顶点关系（路径）的输入，并依此建立一个无向图。
（2）遍历模块：
深度优先遍历图并打印与屏幕上，还可以在查找模块中被调用进行简单路径的查找。
（3）查找模块：
基于DFS的思想进行两点之间固定路径长度简单路径的查找，所以需要被调用N次（N为图顶点数减一）以完成所有简单路径查找并输出与屏幕上。
三、详细设计
物理数据类型
顶点上存储的应为该城市的编码（为三位数字），可以用三位的字符数组来存储，并检查是否属于字符的0~9。
边上应存储有两城市之间路径长度（本题只需求简单路径，所以全部设为1），无路径则设为-1。
以整型数来存储。
深度优先遍历图的伪代码：
voidDFS_Traverse（）//深度优先遍历图，将所有顶点定义为未访问
{
for（inti=0;ivisited[i]=false;
for（i=0;iif（!
visited[i]）
DFS（i）;
}
构造无向图的伪代码
voidCreate_NDGraph（）//构造无向图
{
stringv1,v2;
inti,j,k;
cout<<"输入顶点数和边数：
";
cin>>vexnum>>arcnum;
while（vexnum>20）//提示顶点个数的限制
{
cout<<"请输入少于20个顶点（重新输入顶点数和边数）：
";
cin>>vexnum>>arcnum;
}
cout<<"输入顶点名称：
";
for（i=0;i{
cin>>vertices[i].data;
vertices[i].firstarc=NULL;
if（i>0）//第二次输入时检查是否输入了和之前输入相同的顶点
{
for（j=0;jif（vertices[i].data==vertices[j].data）//如果相同，提示重新输入
{
cout<<"输入重复的顶点：
--"<";
i--;
}
}
}
for（k=0;k{
cout<<"输入每条边对应的两个顶点：
";
cin>>v1>>v2;
i=Locate_Vex（v1）;
j=Locate_Vex（v2）;
while（i==-1||j==-1||i==j）
//当连个顶点中有一个不存在与该图中或两个顶点位于同一位置
{
cout<<"顶点中有不符合要求的，请重新输入：
";
cin>>v1>>v2;
i=Locate_Vex（v1）;
j=Locate_Vex（v2）;
}
//将i和j连接起来
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;
}
cout<<"无向图构造完成"<}
深度搜索路径的伪代码
voidDFS（intv）{
visited[v]=true;
cout<ArcNode*p;
intw;
for（p=vertices[v].firstarc;p;p=p->nextarc）
{
w=p->adjvex;
if（!
visited[w]）
DFS（w）;
}
}
打印出所有简单路径的伪代码：
voidPrint_X_Y_Path（intu,intv,intd）
//求出所有从u到v的路径，d刚进来的时候是-1
{
intm;
d++;
visited[u]=true;
path[d]=u;
if（u==v）//找到一条路径，输出该路径
{
for（inti=0;icout<";
cout<}
else
{
ArcNode*p=vertices[u].firstarc;//继续DFS
while（p）
{
m=p->adjvex;
if（!
visited[m]）//如果该顶点未被访问过
Print_X_Y_Path（m,v,d）;
p=p->nextarc;
}
}
//恢复环境，使顶点可重新使用
//路径长度减一
visited[u]=false;
d--;
}
};
算法的具体步骤
对于用户想要查找路径的两个顶点，创建一个用于记录路径的数组，路径长度为0。
以其中一个顶点为起点，访问该顶点，将该顶点加入路径，访问下一个未被访问的顶点，将其加入路径，并将路径长度加1。
若该顶点为终点，将该路径输出，然后从路径中删除该顶点，并将路径长度减1，访问下一个未被访问的顶点。
若不为终点，则访问下一个未被访问的顶点，直到路径长度不小于顶点个数。
当输入的顶点不在图中则提示错误。
算法的时空分析
算法基于DFS实现，运行次数和找到的路径数有关，若找到的路径数为0，则时间代价为
，若找到的路径为N，则时间代价为
。
输入输出格式：
cout<<”请输入节点数：
”
cin>>
cout<<”输入城市编号：
”
cin>>
cout<<”请输入路径：
”<cin>>//路径
cout<<”请输入查找的路径：
”
cin>>>>
cout<<”输出所有的简单路径”
四结果截图
五附录（代码）
#include
#include
usingnamespacestd;
classGraphm
{//Implementadjacencymatrix
private:
intnumVertex,numEdge;//Storenumberofverticesedges
int**matrix;//Pointertoadjacencymatrix
int*mark;//Pointertomarkarray
public:
Graphm（intnumVert）
{//Makegraphw/numVertvertices
inti;
numVertex=numVert;
numEdge=0;
mark=newint[numVert];//Initializemarkarray
for（i=0;imark[i]=0;
matrix=（int**）newint*[numVertex];//Makematrix
for（i=0;imatrix[i]=newint[numVertex];
for（i=0;ifor（intj=0;j}
intfirst（intv）
{//Returnv'sfirstneighbor
inti;
for（i=0;iif（matrix[v][i]!
=0）returni;
returni;//Returnnifnone
}
intnext（intv1,intv2）
{
//Getv1'sneighborafterv2
inti;
for（i=v2+1;iif（matrix[v1][i]!
=0）returni;
returni;
}
intn（）
{
returnnumVertex;
}
inte（）
{
returnnumEdge;
}
//Setedge（v1,v2）towgt
voidsetEdge（intv1,intv2,intwgt）
{
if（wgt<0）cout<<"Illegalweightvalue"<if（matrix[v1][v2]==0）numEdge++;
matrix[v1][v2]=wgt;
}
voiddelEdge（intv1,intv2）{//Deleteedge（v1,v2）
if（matrix[v1][v2]!
=0）numEdge--;
matrix[v1][v2]=0;
}
intweight（intv1,intv2）{returnmatrix[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<cout<}
for（w=G->first（u）;wn（）;w=G->next（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<<"输入所有城市编号！
"<for（inti=0;i{
cin>>str[i];
intj=0;
while（j!
=i）//检查是否重复
if（str[j++]==str[i]）
{
cout<<"输入错误！
重新输入!
"<i--;
break;
}
}
//字符串数组中的编号与图中节点一一对应
cout<<"输入高速公路（编号编号字符（当字符为E时结束））:
"<intV1=-1,V2=-1;
charc;
stringstr1,str2;
while（c!
='E'）
{
cin>>str1>>str2>>c;
for（inti=0;i{
if（str[i]==str1）
V1=i;
if（str[i]==str2）
V2=i;
}
if（V1!
=-1&&V2!
=-1&&V1!
=V2）
{
G.setEdge（V1,V2,1）;
G.setEdge（V2,V1,1）;
}
else
cout<<"输入有误！
重新输入！
"<}
cout<<"输入要搜索的两个城市编号：
";
cin>>str1>>str2;
for（i=0;i{
if（str[i]==str1）
V1=i;
if（str[i]==str2）
V2=i;
}
int*num=newint[n];
intd=-1;
PathAll（&G,V1,V2,num,str,d）;
if（d==0）
cout<<"两城市间无简单路径!
"<return0;
}
升级会员 