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