图的随机生成及欧拉(回)路的确定

1、 AU蹴空/身实验报告（/学年第一学期）课程名称离散数学实验名称图的随机生成及欧拉（回）路的确定实验时间年月日指导单位指导教师班级学号专业学生姓名学院（系）实验报告实验名称图的随机生成及欧拉（回）路的确定指导教师实验类型上机实验实验学时4实验时间一、实验目的和要求目的：编程随机生成n个结点的无向图或者有向图并能判定该无向图或者有向图是否存在欧拉（回）路，若是则给出欧拉（回）路。要求：对给定n个结点，随机生成邻接矩阵以确定某无向或者有向简单图并进行是否存在欧拉（回）路的判定，若符合则给出至少一条欧拉回路或欧拉路。二、实验环境（实验设备）硬件:PC机。软件:Code:Blocks（C+）三、实验原

2、理及内容内容：Q图的随机生成：首先由用户选择是生成无向图还是有向图，再读入用户输入的结点个数，然后调用对应的无向图类或者有向图类的构造函数，在构造函数中随机生成邻接矩阵，计算可达性矩阵并且输出这两种矩阵。Q欧拉（回）路的确定：调用对应的无向图类或者有向图类中的判定是否存在欧拉路的函数和判定是否存在欧拉回路的函数，如果存在，输出欧拉（回）路存在，并且调用遍历欧拉路或者欧拉回路的函数。原理：建立一个图类（父类），在图类中用n储存结点个数，用*a指向一个二维数组存储邻接矩阵，用*p指向的二维数组储存可达性矩阵，建立图类的构造函数、析构函数、输出邻接矩阵的函数、输出可达性矩阵的函数、判断是否连通的函数

3、。由于两种图中的判断是否存在欧拉（回）路的原理不同，所以建立图类的两个派生类一无向图类和有向图类，在类中分别建立各自的判断是否存在欧拉（回）路的函数，以及遍历欧拉（回）路的函数。这些函数的原理就是欧拉（回）路判定的充要条件，结合邻接矩阵和可达性矩阵的特点编写即可。程序：#include#include#include#includeusingnamespacestd;classgraph/图类protected:intn;结点数int*a;/储存邻接矩阵int*p;储存可达性矩阵public:graph(intsize);graph();voidPrint_linjie();输出邻接矩阵voi

4、dPrint_keda();输出可达性矩阵boolLiantong_or_not();判断图是否连通；graph:graph(intsize)n=size;srand(time(NULL);a=newint*n;for(inti=0;in;i+)ai=newintn;for(intj=0;ji;j+)aij=aji=rand()%2；aii=0;p=newint*n;for(inti=0;in;i+)pi=newintn;for(intj=0;jn;j+)pij=0；graph:graph()for(inti=0;in;i+)deleteai;delete口a;for(inti=0;in;i+

5、)deletepi;deletep;1_,coutaij:一一coutpijclassYgraph:publicgraph有向图类public:Ygraph(intsize);Ygraph()boolOulalu_or_not(int&begin);判断有向图是否存在单向欧拉路boolOulahuilu_or_not();/判断有向图是否存在单向欧拉回路voidDFS(intbegin);private:voidDFS(intbegin,intk,bool*visit);Ygraph:Ygraph(intsize):graph(size)srand(time(NULL);for(inti=0;

6、in;i+)for(intj=0;jn;j+)this-aij=rand()%2;this-aii=0;_)if(this-aij=1)1if(this-aikllthis-ajk);:o-returntrue;boolYgraph:Oulalu_or_not(int&begin)if(!Liantong_or_not()returnfalse;intcount=0;int*r=newintthis-n;储存入度与初度不同的结点的出度int*s=newintthis-n;/储存入度与初度不同的结点的入度for(inti=0;in;i+)intcount1=0,count2=0;for(intj

7、=0;jn;j+)if(this-aij)count1+;if(this-aji)count2+;if(count1!=count2)rcount=count1;scount=count2;if(count1count2)begin=i;count+;if(count!=2)returnfalse;elseif(r0-s0=1&s1-r1=1lls0-r0=1&r1-s1=1)returntrue;elsereturnfalse;voidYgraph:DFS(intbegin)bool*visit=newbool*this-n;for(inti=0;in;i+)visiti=newboolth

8、is-n;for(intj=0;jn;j+)if(aij)；elsevisitij=false;out一for(intk=0;kn;k+)DFS(begin,k,visit);deletevisit;voidY-if(visitjk)visitjk=false;coutk;if(i!=k)DFS(k,i,visit);.Wg.g无仆public:Wgraph(intsize);Wgraph()boolOulalu_or_not(int&begin);判断是否存在欧拉路boolOulahuilu_or_not();/判断是否存在欧拉回路voidDFS(intbegin);private:void

9、DFS(intbegin,intk,bool*visit);；Wgraph:Wgraph(intsize):graph(size)s_for(intj=0;jaij=this-aji=rand()%2;this-aii=0;1_if(this-aij=1):“,+if(this-aikllthis-ajk)/boolWgraph:Oulalu_or_not(int&begin)igornot()jfalse;intnumber=0;bool*visit=newbool*this-n;_)visiti=newboolthis-n;f-if(aij),-elsevisitij=false;:一wh

10、ile(flag=1)system(cls);intflag_2=0;intsize,choose,begin=0;coutchoose;coutendlsize;Ygraphg(size);Wgraphh(size);switch(choose)case1:coutendl该图的邻接矩阵为：endl;g.Print_linjie();cout该图的可达性矩阵为：endl;g.Print_keda();if(g.Oulalu_or_not(begin)cout该图存在欧拉路！endl;8世欧拉路为：；g.DFS(begin);elsecout该图不存在欧拉路！endl;if(g.Oulahui

11、lu_or_not()cout该图存在欧拉回路！endl;8世欧拉回路为：”；g.DFS(begin);elsecout该图不存在欧拉回路！endl;break;case2:coutendl该图的邻接矩阵为：endl;h.Print_linjie();cout该图的可达性矩阵为：endl;h.Print_keda();if(h.Oulalu_or_not(begin)cout该图存在欧拉路！endl;8世欧拉路为：”；h.DFS(begin);elsecout该图不存在欧拉路！endl;if(h.Oulahuilu_or_not()cout该图存在欧拉回路！endl;8世欧拉回路为：”；h.D

12、FS(begin);elsecout该图不存在欧拉回路！endl;break;default:coutendl图的类型输入有误！endl;break;3a0口41是否继续使用？(继续使用请输入1,否则输入0)：举例使用：1、无向图不存在欧拉路和欧拉回路的例子ED:sdeblcx厄文件离散实脆四、图的随机生皮及嫩回避的肆定上咫-,选择要生成的图的类型（1、有向图2、无向图）：2请输入要生成的图的节獭：4 J433 四、实验小结这次实验是要做图的随机生成及欧拉（回）路的确定，由于没有明确的要求，我最开始决定做无向图的随机生成及只判断是否存在欧拉（回）路而不给出具体的欧拉（回）路，这样简单一点。我运用了类的继承与派生的知识，先建立一个图类，再将无向图类建立为其派生类，类的成员函数只需根据定义及判定定理并结合两个矩阵的特点来建立即可，在生成可达性矩阵时，为了加快系统的运算，我通过查阅资料运用了Warshall算法的原理建立这个函数。这些完成之后，我利用课后的时间将这个程序进一步完善，增加了有向图类及其成员函数，