求无向图中求两点间的所有简单路径实验报告..docxVIP

HUNAN UNIVERSITY课程实验报告题目：求无向图中求两点间的所有简单路径学生姓名：学生学号：专业班级：指导老师： 完成日期： 需求分析输入形式本程序要求用户首先输入一个结点总数，然后输入结点的城市编号（4位长的数字，例如电话区号，长沙是0731）,以及高速公路连接的两所城市（用高速公路连接的两个城市编号标记），最后输入要查询所有简单路径的两座城市的名称。当用户输入不合法时，提示用户输入有误，并重新输入。输入具体格式如下：请输入城市总数：请输入高速公路的条数：请依次输入城市名称：请输入高速公路连接的两座城市：请输入需查询所有路径的两所城市的名称：输出形式从xx到xx的所有路径如下：将所有路径（城市编号组成）存至用户指定的文件中。程序功能该程序可以通过构建一个图用来表示各个城市之间是否有高速公路连通的关系，可以实现查询两城市间所有路径的功能测试数据①请输入城市总数： 3请依次输入城市编号：0001 0002 0003有几对城市间有高速公路？3请输入第一对连接城市的高速公路：0001 0002请输入第二对连接城市的高速公路：0002 0003请输入第三对连接城市的高速公路：0001 0003请输入请输入需查询所有路径的两所城市的名称：0001 0003从城市0001到0003的所有简单路径如下：001-003001-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的所有简单路径如下：0001000300020002-00030003-0002-0004所有路径已存入文件中。⑤请输入城市总数： -1 结束程序概要设计抽象数据类型因为各个城市间的是否有高速公路连通的关系是非线性的，而且具有结构网状特性，并且高速公路是无向的，所以选择无向图来表示各个城市间的连通关系。图的ADT设计：数据对象：G=(V,E)，其中V表示顶点集合，E表示边集合数据关系：VR＝{v,w| v,w∈V 且 P(v,w)} v,w表示从 v 到 w 的一条弧， v 为弧头，w 为弧尾。 基本操作：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;}};②图的相邻