HUNAN UNIVERSITY
课程实验报告
题 目： 无向图中求两点间的所有简单路径
学生姓名
学生学号 ******0102
专业班级 计算机科学与技术班
完 成 日 期 weight的所有形式
一、需求分析
城市分布不均，且无向，两个城市之间有路连接，根据特点，可以抽象成一个无向图，城市为各点，高速路为边。按照用户的输入建立一个邻接表，输出两个点的所有路径。
(1) 输入的形式和输入值的范围：本程序要求首先输入一个正整数值N，代表城市总数，然后依次输入城市的代号，可以用四位数字表示。因此，用整数来存储。
(2) 输出的形式：根据输入的数据，进行输入，若能成功，则将所有序列输出，若不能成功，则提示报错。
(3) 程序所能达到的功能：程序要求能够识别输入城市编号列表，高速公路，需要查路径的两个城市时的错误，能够判断输入的两个城市之间是否存在路径，如果存在路径要求能够将路径输出。
二、概要设计
抽象数据类型
因为各个结点直间是网状结构，那么一个结点会和多个结点连接，因此我们使用图来存储各个结点的信息。
ADT Graph{
数据对象：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;//设置标记}
算法的基本思想
程序需要输入城市编号及城市的编号对以实现城市间的高速公路的输入。然后输入某两个城市，得出城市间的所有简单路径。得到无向图中某两个城市间的简单路径，考虑使用基于深度优先思想，通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。
程序流程
程序主要由四个步骤组成：
（1） 输入城市总数
（2） 输入正确的城市编号列表
（3） 输入所有的有高速公路直接连接的城市对编号
（4） 循环输入需要寻路径的城市对的编号寻它们之间的所有简单路径。
三、详细设计
实现概要设计中的数据类型
为了方便编写这个程序，图用二阶矩阵来存储。
图的构建和基本操作：
class Graphm : public Graph
{
private:
int numVertex, numEdge;
int **matrix;
int *mark;
public:
Graphm(int numVert)
{
int i, j;
numVertex = numVert; numEdge = 0;
mark = new int[numVert]; for (i=0; i<numVertex; i++) mark[i] = UNVISITED;
matrix = (int**) new int*[numVertex];
for (i=0; i<numVertex; i++)
matrix[i] = new int[numVertex];
for (i=0; i< numVertex; i++)
for (int j=0; j<numVertex; j++)
matrix[i][j] = 0;}
<1>返回结点的第一条邻边。由于用邻接矩阵来存储，当下标matrix[v][i]不等于 0 时，就到了邻边。成功就返回邻边的位置。
int first(int v)
{
int i;
for (i=0; i<numVertex; i++)
if (matrix[v][i] != 0) return i;
return i;
}
<2>返回下一条邻边。当下标matrix[v][i]不等于0 时，就到了邻边。成功就返回邻 边的位置。
int next(int v1, int v2)
{
int i;
for(i=v2+1; i<numVertex; i++)
if (matrix[v1][i] != 0) return i;
return i;
}
<3>加边。传入结点，若该边不存在，则结点数+1，并添加该边。
void setEdge(int v1, int v2)
{
if (matrix[v1][v2] == 0)
numEdge++;
matrix[v1][v2] = 1;
}
<4>获取结点的个数。直接返回个数。
int n() { return numVertex; }
<5>获取边的数量。直接返回边的数量。
int e() { return numEdge; }
查：
从起始的城市对应的顶点开始，逐次访问其邻接顶点。访问一个顶点时，标记为1，将其存入数组中。
如果被访问的点在其此次所在的路径中之前已被访问（包括此次访问到的是起始顶点），或该顶点没有邻接顶点了且该顶点不是目的顶点，就不再继续访问其邻接顶点，此条路径不再继续。
如果该顶点是目的顶点，则将该条路径上之前访问的包括此次访问的顶点全部输出，显示所到的一条简单路径。
void PathAll(Graphm *G,int u,int v,int *path,string* str,int &d)
//d是到当前为止已走过的路径长度，调用时初值为-1
{
int w,i;
G->setMark(u,1);
d++; //路径长度增1
path[d]=u; //将当前顶点添加到路径中
if (u==v&&d>=1) //输出一条路径
{
cout<<"这两个城市间一条的简单路径为:";
for (i=0;i<=d;i++)
cout<<str[path[i]]<<" ";
cout<<endl;
}
for (w=G->first(u);w<G->n();w=G->next(u,w))
{
if (G->getMark(w)==0)
PathAll(G,w,v,path,str,d);
}
G->setMark(u,0);//恢复，可以再寻 d--;//去掉这个点
}
算法的时空分析
邻接矩阵的空间代价为Θ(|V|2)，查设共计访问的结点次数为k，则易知函数的时间开 销为Ɵ(k)。
输入和输出的格式
输入
请输入城市数量
请输入城市编号： 0001
请输入城市编号： 0002
请输入城市编号 ：0003
……
城市编号列表输入完毕！
请输入之间有高速公路连接的城市编号c1和c2： 0001 0002 ……
请输入要查的两个城市之间的路 等待输入
输出
从c1到c2之间的路为
四、测试结果
五、用户使用说明（可选）
1、本程序的运行环境为DOS操作系统，执行文件为实验六2.exe
2、运行程序时：
(1) 显示提示“请输入结点总数”，此时输入结点数。
(2) 数据输入完毕后，查所有简单路径，若有则输出若没有输出这两个点不连通。
六、实验心得
这次实验让我更加了解深度优先搜索遍历，对课堂内容更加了解。
七、附录
#include<iostream>
#include<fstream>
#include<string.h>
#include<iomanip>
using namespace std;
class AStack
{
private:
int size;//栈的大小
int top;//栈中元素的多少
string *listArray;
public:
AStack(int sz=0)//构建栈
{
size=sz;
top=0;
listArray=new string[sz];
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论