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

《实验无向图中求两点间的所有简单路径》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验6无向图中求两点间的所有简单路径计科二班宋瑞霞20100810217一、需求分析1、用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。设计一个找路程序，获取两个城市之间的所有简单路径。2、由用户通过键盘输入：（1）结点总数，（2）结点的城市编号（4位长的数字，例如电话区号，长沙是0731），（3）连接城市的高速公路（用高速公路连接的两个城市编号标记），（4）要求取所有简单路径的两个城市编号。不对非法输入做处理，即假设输入都是合法的。3、输出：将所有路径（有城市编号组成）输出到DOS界面上。4、测试数据：输入：68（结点数和边数）00

2、0100020003000400050006（结点的城市编号）00010003（连接城市间的高速公路）0001000500020006000300020003000400030006000400060005000600010002(要求取所有简单路径的两个城市编号)输出：000100030002（两个城市间的所有简单路径）000100030006000200010003000400060002000100050006000200010005000600030002000100050006000400030002二、概要设计抽象数据类型根据对问题的分析，要

3、用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。所以要建立一个图来实现。图的ADT设计如下：数据元素：包括一个顶点集合和一个边集合数据关系：网状关系基本操作：Graph(intnumvert)//构造图结构virtualintn()=0;//获取顶点的个数virtualintfirst(int)=0;//访问所给顶点的第一个邻居virtualintnext(int,int)=0;//访问当前邻居的下一个邻居virtualvoidsetedge(int,int)=0;//建立所给两顶点之间的边virtualvoidsetmark(int

4、v,intval)=0;//给顶点做标记virtualintgetmark(intv)=0;//获取顶点是否已做标记算法的基本思想首先，根据输入的结点总数构建一个线性表，将输入的城市编号即顶点依次添加到线性表中；然后就是在图的二维数组中存入边即连接两个城市间的高速公路，这步操作首先要找到两个城市即两个顶点在线性表中的位置如m和n，然后再在二维数组相应的位置(m,n)上存入1建立该条边；最后当所有的边都存入图中后，由于深度优先的结果是沿着图的某一分支搜索直至末端，然后回溯，在沿着另一条分支搜索，依次类推，故对图进行深度优先搜索，即可得到两个城市间的简单路径

5、。程序的流程程序由四个模块组成：1、输入模块：输入图的顶点和边；2、构建模块：用线性表存储顶点，用二维数组存储边，构建图结构；3、处理模块：对图进行深度优先搜索；4、输出模块：将深度优先搜索后得到的所有简单路径输出到DOS界面上。三、详细设计物理数据类型该问题需要输入4位长的数字表示的城市编号，为了能够存储，采用C++语言中的字符串string来定义变量线性表中的元素类型，数组的大小为4。根据用邻接矩阵表示法来实现图的相关知识，要先建立一个线性表来存储顶点，由于结点总数即图的顶点数已知，则线性表的长度已知，故用顺序表实现比较好，因为顺序表是预先分配一段连

6、续的存储空间，而且没有结构性开销。1、顺序表的具体实现如下：template（在本问题，Elem为string）classAlist{private:intmaxSize;//顺序表的最大长度intlistSize;//顺序表的实际长度intfence;//指向当前位置Elem*listArray;//存储顺序表元素的数组public:Alist(intsize=DefaultListSize)//构造一个由用户指定最大长度的空顺序表{maxSize=size;listSize=fence=0;listArray=newElem[m

7、axSize];}boolappend(constElem&item)//添加{if(listSize==maxSize)returnfalse;else{listArray[listSize++]=item;returntrue;}}intrightLength()const//右边长度{returnlistSize-fence;}boolgetvalue(iElem&it)const//获取当前位置的元素值，若右边为空，返回false{if(rightLength()==0)returnfalse;else{it=listArray[fence];r

8、eturntrue;}}voidsetStart()//将当前位置置0{fenc