简单路径问题
余年寄山水
953次浏览
2021年01月18日 19:50
最佳经验
本文由作者推荐
九尾妖狐出装-狼和鹿的故事
数据结构课程实验指导书
背景
简单路径：如果一条路径上的顶点 除了起点和终点可以相同外，其它顶点均不相
同，则称此路径为一条简单路径。
问题描述
若用无向图表示高速公路网，
其中顶点表示城市，
边表示 城市之间的高速公路。
试设计
一个找路程序，获取两个城市之间的所有简单路径。
一．需求分析
1.
基本要求
（
1
）
输入参数：结点总数，结点的城市编号（
3
位长的数字，
）
，连接城市的高速公
路（用高速公路连接的两个城市编号标记）。
（
2
）
输入
要求取所有简单路径的两个城市编号。
（
3
）
将所有路径（有城市编号组成）输出到用户指定的文件中。
2.
输入输出格形式：
输入：
(1)
要求用户 先输入结点总数（总城市数
n
）
，再输入代表城市的编号（三位数字）
。
(2)
多次输入两个城市编号来确定城市之间的高速公路（最多输入
n(n-1 )/2
次）
。
(3)
输入两个城市的编号来获取简单路径。
输出：两点中所有的简单路径。
。
3
测试数据
输入
节点数：
5
城市编号：
001 002 003 004 005 006
路径：
001 002
001 003
002 003
002 004
003 005
004 006
005 006
查找路径：
0001 0005
输出
001-->003-->005
001-->002-->003-->005
001-->002-->004-->006-->005
001-->003-->002-->004-->006->005
－
1
－
数据结构课程实验指导书
二、概要设计
抽象数据类型
为实现上述程序的功能，
应 以整数存储用户的每次输入，
根据输入建立一个无向图，
用
基于深度优先搜索的方法找 出简单路径。
图的
ADT
设计：
数据对象：
Graph = (V , R )
数据关系：
VR
＝
{
∈
V
且
P(v,w)}
表示从
v
到
w
的一条弧，并称
v
为弧头，
w
为弧尾。
谓词
P(v,w)
定义了弧
的意义或信息。
基本操作：
class Graph {
//
图的定义类
public:
int GetVexNum()
//
获得图中顶点的个数
int Locate_Vex(string v)
//
获得顶点在图中的位置
void DFS_Traverse()
//
深度优先搜索图
};
算法的基本思想
对于用户想要查找路径的两个顶点，创建一个用于记录路径的数组，
路径长度为
0
。
以其中一个顶 点为起点，
访问该顶点，
将该顶点加入路径，
访问下一个未被访问的顶点，
将 其加入路径，并将路径长度加
1
。若该顶点为终点，将该路径输出，然后从路径中删
除 该顶点，并将路径长度减
1
，访问下一个未被访问的顶点。若不为终点，则访问下一
个 未被访问的顶点，直到路径长度不小于顶点个数。
程序的流程
程序由三个模块组成：
(1)
建图模块：完成顶点数，边数和顶点关系（路 径）的输入，并依此建立一个无向图。
(2)
遍历模块：深度优先遍历图并打印与屏 幕上，还可以在查找模块中被调用进行简单
路径的查找。
(3)
查找模块： 基于
DFS
的思想进行两点之间固定路径长度简单路径的查找，所以需要
被调用
N
次（
N
为图顶点数减一）以完成所有简单路径查找并输出与屏幕上。
－
2
－
数据结构课程实验指导书
三、详细设计
物理数据类型
顶点上存储的应为该城市的编码（为 三位数字）
，可以用三位的字符数组来存储，并检
查是否属于字符的
0~9
。 边上应存储有两城市之间路径长度（本题只需求简单路径，所以全
部设为
1
）
，无路径则设为
-1
。以整型数来存储。
深度优先遍历图的伪代码：
void DFS_Traverse()
//
深度优先遍历图，将所有顶点定义为未访问
{
for(int i=0;i
visited[i]=false;
for(i=0;i
if(!visited[i])
DFS(i);
}
构造无向图的伪代码
void Create_NDGraph()
//
构造无向图
{
string v1,v2;
int i,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;j
if(vertices[i].data==vertices[j].data)
//
如果相同，提示重新输入
{
cout<<
输入重复的顶点：
--
请重新
输入：
－
3
－
数据结构课程实验指导书
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=new ArcNode;
p->adjvex=j;
p->nextarc=vertices[i].firstarc;
vertices[i].firstarc=p;
//
置对称边
ArcNode *q=new ArcNode;
q->adjvex=i;
q->nextarc=vertices[j].firstarc;
vertices[j].firstarc=q;
}
cout<<
无向图构造完成
}
深度搜索路径的伪代码
void DFS(int v)
{
visited[v]=true;
cout<
ArcNode *p;
int w;
for(p=vertices[v].firstarc;p;p=p->nextarc)
{
－
4
－
数据结构课程实验指导书
w=p->adjvex;
if(!visited[w])
DFS(w);
}
}
打印出所有简单路径的伪代码：
void Print_X_Y_Path(int u,int v,int d)
//
求出所有从
u
到
v
的路径，
d
刚进来的时候是
-1
{
int m;
d++;
visited[u]=true;
path[d]=u;
if(u == v) //
找到一条路径
，输出该路径
{
for(int i=0;i
cout<
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--;
}
};
算法的具体步骤
< br>对于用户想要查找路径的两个顶点，
创建一个用于记录路径的数组，
路径长度为
0
。
以其中一个顶点为起点，
访问该顶点，
将该顶点加入路径，< br>访问下一个未被访问的顶点，
将其加入路径，并将路径长度加
1
。若该顶点为终 点，将该路径输出，然后从路径中删除该
－
5
－