简单路径问题

次）

。

(3)

输入两个城市的编号来获取简单路径。

< br>

输出：两点中所有的简单路径。

。

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

－

数据结构课程实验指导书

二、概要设计

抽象数据类型

为实现上述程序的功能 ，

应以整数存储用户的每次输入，

根据输入建立一个无向图，< /p>

用

基于深度优先搜索的方法找出简单路径。

图的

ADT

设计：

数据对象：

Graph = (V , R )

数据关系：

VR

＝

{| v,w

∈

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

。

以其中一个 顶点为起点，

访问该顶点，

将该顶点加入路径，

访问下一个未被访问的顶点，

将其加入路径，并将路径长度加

< br>1

。若该顶点为终点，将该路径输出，然后从路径中删

除 该顶点，并将路径长度减

1

，访问下一个未被访问的顶点。若不 为终点，则访问下一

个未被访问的顶点，直到路径长度不小于顶点个数。

程序的流程

程序由三个模块组成：

(1)

建图模块：完成顶点数，边数和顶点关系（路径）的输入，并依此建立一个无向图。

(2)

遍历模块：深度优先遍历图并打印与屏幕 上，还可以在查找模块中被调用进行简单

路径的查找。

(3)

查找模块：基于

DFS

的思想进行两点之间固定路径长度简单路径的查找，所以需要

被调用

次（

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<<

输入顶点数和边数：< /p>

cin>>vexnum>>arcnum;

while(vexnum>20)

//

提示顶点个数的限制

{

cou t<<

请输入少于

20

个顶点

(

重新输入顶点数和边数

)

：

cin>>vexnum>>arcnum;

}

cou t<<

输入顶点名称：

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

//

多次输入两个顶点来构造边

{

cou t<<

输入每条边对应的两个顶点：

cin>>v1>>v2;

i=Locate_Vex(v1);

j=Locate_Vex(v2);

while(i == -1 || j == -1||i == j)

//

当连个顶点中有一个不存在与该图中或两个顶点位于同一位置

{

cou t<<

顶点中有不符合要求的，请重新输入：

< br>

cin>>v1>>v2;

i=Locate_Vex(v1);

j=Locate_Vex(v2);

}

//

将< /p>

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)

//< /p>

求出所有从

u

到

v

的路径，

d

刚进来的时候是