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

实验6无向图中求两点间的所有简单路径 问题描述 若用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。试设计一个找路程序，获取两个城市之间的所有简单路径。 基本要求 （1） 输入参数：结点总数，结点的城市编号（4位长的数字，例如电话区号，长沙 是0731），连接城市的高速公路（用高速公路连接的两个城市编号标记）。 （2） 输入 要求取所有简单路径的两个城市编号。 （3） 将所有路径（有城市编号组成）输出到用户指定的文件中。 实现提示 基于DFS的思想。 一、需求分析 城市分布不均，且无向，两个城市之间有路连接，根据特点，可以抽象成一个无向图，城市为各点，高速路为边。按照用户的输入建立一个邻接表，输出两个点的所有路径。 (1) 输入的形式和输入值的范围：本程序要求首先输入一个正整数值N，代表城市总数，然后依次输入城市的代号，可以用四位数字表示。因此，用整数来存储。 (2) 输出的形式：根据输入的数据，进行输入，若能成功，则将所有序列输出，若不能成功，则提示报错。 (3) 程序所能达到的功能：程序要求能够识别输入城市编号列表，高速公路，需要查找路径的两个城市时的错误，能够判断输入的两个城市之间是否存在路径，如果存在路径要求能够将路径输出。 二、概要设计 1.抽象数据类型 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）?输入城市总数? （2）?输入正确的城市编号列表? （3）?输入所有的有高速公路直接连接的城市对编号? （4）?循环输入需要寻找路径的城市对的编号寻找它们之间的所有简单路径。 3.算法的基本思想 （1）程序需要输入城市编号及城市的编号对以实现城市间的高速公路的输入。然后输入某两个城市，得出城市间的所有简单路径。得到无向图中某两个城市间的简单路径，考虑使用基于深度优先思想，通过相应的设置标志的方式使最终能不重复地走遍所有的简单路径。 （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][j]?=?0;} 2）查找：从起始的城市对应的顶点开始，逐次访问其邻接顶点。访问一个顶点时，标记为1，将其存入数组中。? 如果被访问的点在其此次所在的路径中之前已被访问（包括此次访问到的是起始顶点），或该顶点没有邻接顶点了且该顶点不是目的顶点，就不再继续访问其邻接顶点，此条路径不再继续。? 如果该顶点是目的顶点，则将该条路径上之前访问的包括此次访问的顶点全部输出，显示所找到的一条简单路径。? 之后将上一个顶点置为0，观察是否还有其余临点，如果有继续查找，如果