HUNAN UNIVERSITY
课程实验报告
题目：求无向图中求两点间的所有简单路径 学生姓名： 学生学号： 专业班级： 指导老师： 完成日期：
一． 需求分析
输入形式
本程序要求用户首先输入一个结点总数，然后输入结点的城市编号（4位长的数字，例如电话区号，长沙是0731）,以及高速公路连接的两所城市（用高速公路连接的两个城市编号标记），最后输入要查询所有简单路径的两座城市的名称。当用户输入不合法时，提示用户输入有误，并重新输入。输入具体格式如下： 请输入城市总数：
请输入高速公路的条数： 请依次输入城市名称：
请输入高速公路连接的两座城市：
请输入需查询所有路径的两所城市的名称：
输出形式
从xx到xx的所有路径如下：
将所有路径（城市编号组成）存至用户指定的文件中。
程序功能
该程序可以通过构建一个图用来表示各个城市之间是否有高速公路连通的关系，可以实现查询两城市间所有路径的功能
测试数据
①请输入城市总数： 3
请依次输入城市编号：0001 0002 0003 有几对城市间有高速公路？3
请输入第一对连接城市的高速公路：0001 0002 请输入第二对连接城市的高速公路：0002 0003 请输入第三对连接城市的高速公路：0001 0003
请输入请输入需查询所有路径的两所城市的名称：0001 0003 从城市0001到0003的所有简单路径如下： 001->003
001->002->003
所有路径已存入文件中。
②请输入城市总数： 3
请依次输入城市编号：001 002 003 有几对城市间有高速公路？2
请输入第一对连接城市的高速公路：001 002 请输入第二对连接城市的高速公路：002 003
请输入请输入需查询所有路径的两所城市的名称：0001 0003 从城市0001到0003的所有简单路径如下：
001->002->003
所有路径已存入文件中。
③请输入城市总数： 3
请依次输入城市编号：001 002 003 有几对城市间有高速公路？ 0
请输入请输入需查询所有路径的两所城市的名称：0001 0003 从城市0001到0003的无简单路径
④请输入城市总数： 4
请依次输入城市编号：001 002 003 004 有几对城市间有高速公路？ 5
请输入第一对连接城市的高速公路：001 002 请输入第二对连接城市的高速公路：002 003 请输入第三对连接城市的高速公路：003 004 请输入第四对连接城市的高速公路：001 004 请输入第五对连接城市的高速公路：001 003
请输入请输入需查询所有路径的两所城市的名称：0001 0004 从城市0001到0003的所有简单路径如下： 0001->0004
0001->0003->0004 0001->0002->0004
0001->0002->0003->0004 0001->0003->0002->0004 所有路径已存入文件中。
⑤请输入城市总数： -1 结束程序
二． 概要设计
抽象数据类型
因为各个城市间的是否有高速公路连通的关系是非线性的，而且具有结构网状特性，并且高速公路是无向的，所以选择无向图来表示各个城市间的连通关系。 图的ADT设计：
数据对象：G=(V,E)，其中V表示顶点集合，E表示边集合 数据关系：VR＝{
int n();//图中顶点个数 int e();//图边数
int first(int);//该点的第一条临边 int next(int,int);//该点的第二条临边 void setEdge(int,int,int);//为边设置权值 void setMark(int ,int);//设置该顶点的标志值 int getMark(int);//获得该顶点的标志值
图的顶点ADT设计：
数据对象：城市编号（占3位的字母数字串）
数据关系:{vi|i=1,2,3……n} 基本操作：
int position();//获取顶点位置
算法基本思想
当用户输入完毕后，根据各城市间相应的关系构建一个无向图，并使用一个临接矩阵存储该图。考虑使用基于深度优先思想，在搜素过程中，每当访问一个节点，DFS就会递归访问它的所有未被访问的相邻节点。并通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。最后输出这些路径即可。
程序基本流程
该程序主要包括四个模块：
输入模块：由用户输入城市总数，城市编号，高速公路编号；
构建与存储模块：根据用户的输入构建无向图，并使用临接矩阵存储图； 访问模块：对该图进行深度优先搜索，得到所有路径； 输出模块：输出所有路径。
三． 详细设计
物理数据类型
①边的实现： class Edge {
public:
int vertex,weight;
Edge（）{ vertex=-1;weight=-1; } Edge(int v,intw){ vertex=v;weight=w;} };
②图的相邻矩阵实现： class Graphm {
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 mark[i]=0; //每一个顶点的标志值初始化为0 matrix =(int**) new int*[numVertex]; for(i=0;i for(j=0;j ~Graphm()