无向图中求两点间的所有简单路径+实验6预习报告.docVIP

HUNAN UNIVERSITY 课程实习报告 题 目 无向图中求两点间的所有简单路径 学生姓名 学生学号 专业班级 指导老师 李晓鸿 完 成 日 期 2014年月 需求分析 城市分布不均,且无向,两个城市之间有路连接。根据特点，可以抽象成一个无向图。城市为各点，高速路为边。按照用户的输入建立一个邻接表，输出两个点的所有路径。 （1）输入的形式和输入值的范围： 本程序要求首先输入一个正整数值N，代表城市总数，然后依次输入城市的代号，可以用四位数字表示。因此，用整数来存储。 不对非法输入做处理，即假设输入都是整数，都是合法的。 输出的形式： 将所有的可能路径用有顺序的城市编号表示并用数组存储，输出到用户指定的文件中。 (3) 程序所能达到的功能： 程序要求能够识别输入城市编号列表，高速公路。需要查找路径的两个城市时的错误，能够判断输入的两个城市之间是否存在路径，如果存在路径要求能够将路径输出。 （4）测试数据： 输入 请输入城市数量 请输入城市编号 0001 请输入城市编号 0002 请输入城市编号 0003 …… 城市编号列表输入完毕 请输入之间有高速公路连接的城市编号 0001 0002 请输入之间有高速公路连接的城市编号 0002 0003 请输入之间有高速公路连接的城市编号 0002 0004 …… 请输入要查找的两个城市之间的路 等待输入 c1 c2 输出 从c1到c2之间的所有简单路径为： 概要设计 抽象数据类型的定义： ADT 图 数据对象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;//设置标记 算法的基本思想： 　 程序需要输入城市编号及城市的编号对以实现城市间的高速公路的输入。然后输入某两个城市，得出城市间的所有简单路径。得到无向图中某两个城市间的简单路径，考虑使用基于深度优先思想，通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。  2、图的存储，用邻接矩阵来存。 主程序流程： 　　 程序主要由四个步骤组成  输入城市总数。  输入正确的城市编号列表。  输入所有的有高速公路直接连接的城市对编号。  循环输入需要寻找路径的城市对的编号寻找它们之间的所有简单 路径。　 详细设计 （1）图的存储：用邻接矩阵来存储，根据输入的顶点个数N创建一个N*N的矩阵，将其全部赋初值。然后根据边的情况来输入对应边的位置。 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; inumVertex; i++) mark[i] = UNVISITED; matrix = (int**) new int*[numVertex]; for (i=0; inumVertex; i++) matrix[i] = new int[numVertex]; for (i=0; i numVertex; i++) for (int j=0; jnumVertex; j++) matrix[i][