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

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

2、4 0005 0006（结点的城市编号） 0001 0003（连接城市间的高速公路） 0001 0005 0002 0006 0003 0002 0003 0004 0003 0006 0004 0006 0005 0006 0001 0002(要求取所有简单路径的两个城市编号)输出：0001 0003 0002（两个城市间的所有简单路径） 0001 0003 0006 00020001 0003 0004 0006 0002 0001 0005 0006 00020001 0005 0006 0003 00020001 0005 0006 0004 0003 0002二、概要设计抽象数据类型

3、根据对问题的分析，要用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。所以要建立一个图来实现。图的adt设计如下：数据元素：包括一个顶点集合和一个边集合数据关系：网状关系基本操作： graph(int numvert) /构造图结构 virtual int n() =0; /获取顶点的个数 virtual int first(int ) =0; /访问所给顶点的第一个邻居virtual int next(int ,int ) =0; /访问当前邻居的下一个邻居virtual void setedge(int ,int ) =0; /建立所给两顶点之间的边virtual voi

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

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

6、1、顺序表的具体实现如下： template（在本问题，elem为string） class alist private: int maxsize;/顺序表的最大长度 int listsize;/ 顺序表的实际长度 int fence;/指向当前位置 elem * listarray;/存储顺序表元素的数组public: alist(int size=defaultlistsize)/构造一个由用户指定最大长度的空顺序表 maxsize =size; listsize=fence=0; listarray= new elem maxsize; bool append(const elem &

7、item)/添加 if(listsize=maxsize) return false; else listarraylistsize+=item; return true; int rightlength() const/右边长度 return listsize-fence; bool getvalue(ielem& it) const/获取当前位置的元素值，若右边为空，返回false if(rightlength()=0) return false; else it=listarrayfence; return true; void setstart()/将当前位置置0 fence=0; v

8、oid next()/右移一位 if(fencelistsize) fence+; ;2、图的具体实现如下：class graphprivate:int numvertex,numedge;/存储顶点数和边数int *matrix;/指向邻接矩阵的指针int *mark; /指向访问标记数组的指针public:graph(int numvert)/实现邻接矩阵int i,j;numvertex=numvert;numedge=0;mark=new intnumvert;for(i=0;inumvertex;i+)/初始化标记数组marki=0;matrix=(int*) new int*num

9、vertex;/构造邻接矩阵for(i=0;inumvertex;i+)matrixi=new intnumvertex;for(i=0;inumvertex;i+)for(j=0;jnumvertex;j+)matrixij=0;graph()/析构函数delete mark;for(int i=0;inumvertex;i+)delete matrixi;delete matrix;int n()/获取顶点个数return numvertex;int e()/获取边的个数return numedge;int first(int v) /访问所给顶点的第一个邻居int i;for(i=0;i

10、numvertex;i+)if(matrixvi!=0)return i;return i;int next(int v1,int v2) /访问当前邻居的下一个邻居int i;for(i=v2+1;inumvertex;i+)if(matrixv1i!=0)return i;return i;void setedge(int v1,int v2) /无向图中建立所给两顶点之间的边if(matrixv1v2=0)numedge+;matrixv1v2=1;matrixv2v1=1;void setmark(int v,int val) /给顶点做标记markv=val;int getmark(

11、int v) /获取顶点是否已做标记return markv;算法的具体步骤1、定义顺序表l、图g，还有存储课程名的字符串string city，city1，city2，输入顶点个数n和边数m。2、输入顶点city并将输入的顶点依次存入顺序表l中。for(int i=0;icity;l.append(city);3、输入有路连接的两个城市编号，即相互间存在边的两个顶点，找到这两个顶点在线性表中的位置，然后在图的二维数组相应的位置上存入1建立该条边。通过一个循环将所有的边都建完，完成图的存储。for(int i=0;icity1city2; g.setedge(find(l,n,city1),f

12、ind(l,n,city2);其中find函数即实现找到顶点在线性表中的位置的功能，具体如下：int find(alist l,int n,int& city)int i;string city1;l.setstart();for(i=0;in;i+)l.getvalue(city1);/获取当前位置的元素值if(city1=city)/若当前位置的元素值与所要找的顶点值相同return i;/则返回当前位置所在的位置elsel.next();/若不同，则在向右移一位再做判断4、 对图进行深度优先搜索int addr100;int num=-1;void dfs(graph& g,int v,

13、alist& l,int d) g.setmark(v,1);if (v = d) for(int i=0;i=num;i+) printout(l,addri); cout ; coutendl;g.setmark(d,0);num-;return;for (int w = g.first(v);w g.n();w = g.next(v,w)if (g.getmark(w) = 0) addr+num=w;dfs(g,w,l,d); num-;g.setmark(v,0);其中的输出函数为：void printout(alist l,int v)l.setstart();string s;

14、for(int i=0;iv;i+)l.next();l.getvalue(s);couts ;算法的时空分析 设v为顶点数，e为边数，（1）由于顺序表用来存储顶点，顺序队列用来存储入度为0的顶点，所以它们的空间代价都为（|v|）；而邻接矩阵的空间代价为（|v|2），故总的空间代价为（|v|2）。（2）由于顺序表的添加操作的时间复杂度为（1），故将所有结点存入顺序表的时间复杂度为（|v|）；在对无向图进行深度优先时，dfs从两个方向处理每条边，每个顶点都必须被访问，而且只能访问一次，故总的时间复杂度为（|v|+|e|）。输入和输出的格式输入：请输入结点总数和边数: /提示 等待输入 请输入城市

15、编号: /提示 等待输入 请输入有路连接的两个城市的编号: /提示 等待输入请输入要求取所有简单路径的两个城市编号: /提示 等待输入输出：这两个城市间的所有简单路径为：/提示 输出结果的位置四、调试分析 大部分是语法错误，看着错误提示都改过来了，今天又学到点新知识，就是如果执行的界面没关的话，连接时会出现错误。五、测试结果六、用户使用说明1、本程序的运行环境为dos操作系统2、运行程序时提示输入结点总数和边数 城市编号有路连接的两个城市的编号要求取所有简单路径的两个城市编号输出：两个城市间的所有简单路径七、实验心得这次实验感觉好难啊，搞了一天的预习报告，结果就得了1分，那种感觉真的好难受的！

16、八、程序#include#includeusing namespace std;#define elem string class alist private: int maxsize;/顺序表的最大长度 int listsize;/ 顺序表的实际长度 int fence;/指向当前位置 elem * listarray;/存储顺序表元素的数组public: alist(int size)/构造一个由用户指定最大长度的空顺序表 maxsize =size; listsize=fence=0; listarray= new elem maxsize; bool append(const elem

17、 & item)/添加 if(listsize=maxsize) return false; else listarraylistsize+=item; return true; bool remove()/删除 elem it; if(rightlength()=0) return false; it=listarray fence; for(int i=fence;ilistsize-1;i+) listarrayi= listarrayi+1; listsize-; return true; int rightlength() const/右边长度 return listsize-fen

18、ce; bool getvalue(elem& it) const/获取当前位置的元素值，若右边为空，返回false if(rightlength()=0) return false; else it=listarrayfence; return true; void setstart()/将当前位置置0 fence=0; void next()/右移一位 if(fence=0)&(pos=0)& (pos=listsize); ;class graphprivate:int numvertex,numedge;int *matrix;int *mark;public:graph(int nu

19、mvert)int i,j;numvertex=numvert;numedge=0;mark=new intnumvert;for(i=0;inumvertex;i+)marki=0;matrix=(int*) new int*numvertex;for(i=0;inumvertex;i+)matrixi=new intnumvertex;for(i=0;inumvertex;i+)for(j=0;jnumvertex;j+)matrixij=0;graph()delete mark;for(int i=0;inumvertex;i+)delete matrixi;delete matrix;

20、int n()return numvertex;int e()return numedge;int first(int v)int i;for(i=0;inumvertex;i+)if(matrixvi!=0)return i;return i;int next(int v1,int v2)int i;for(i=v2+1;inumvertex;i+)if(matrixv1i!=0)return i;return i;void setedge(int v1,int v2)matrixv1v2=1;matrixv2v1=1;void setmark(int v,int val)markv=val;int getmark(int v)return markv;int find(alist l,int n,string s)int i;string s1;l.setstart();for(i=0;in;i+)l.getvalue(s1);if(s1=s)return i;elsel.next();void