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

《离散数学》实验报告（2015/2016学年第一学期）题目：图的随机生成及欧拉（回）路的确定专业信息安全学生姓名班级学号指导教师指导单位计算机学院计算机科学与技术系日期2015年12月29日图的随机生成及欧拉（回）路的确定一、实验内容和要求内容：编程随机生成n个结点的无向图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。要求：对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。二、实验目的对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。三、实验任务1、输入结点个数据生成随机图2、进行（半）欧拉图的判定3、若是则给出欧拉（回）路。四、实验内容#includeiostream#includectime#includecstdlibusingnamespacestd;classEuler{public:Euler(intnum);~Euler();voidDFS(intbegin);//公有的深度优先搜索函数voidinputEdge();//输入边voidPrintAM();//打印邻接矩阵voidPrintRM();//打印可达性矩阵voidWarshall();//Warshall算法求可达性矩阵boolIsConnected();//判断图是否连通intIsEorSE();//判断图是欧拉图还是半欧拉图boolisEuler;private:voidDFS(intu,intv,bool**visited);//私有的深度优先搜索函数intn;int**a;//定义动态二维数组int**p;//定义可达性矩阵int*b;//存储每个结点的度数};Euler::Euler(intnum)//构造函数{isEuler=false;n=num;inti,j;a=newint*[n];for(i=0;in;i++){a[i]=newint[n];for(j=0;jn;j++)a[i][j]=0;}p=newint*[n];for(i=0;in;i++){p[i]=newint[n];for(j=0;jn;j++)p[i][j]=0;}b=newint[n];for(i=0;in;i++)b[i]=0;}Euler::~Euler()//析构函数{inti;for(i=0;in;i++)delete[]a[i];delete[]a;for(i=0;in;i++)delete[]p[i];delete[]p;delete[]b;}voidEuler::inputEdge(){srand((unsigned)time(NULL));for(inti=0;in;i++){for(intj=i+1;jn;j++){a[i][j]=0+rand()%2;//随机生成无向图a[j][i]=a[i][j];}}for(intii=0;iin;ii++){for(intjj=0;jjn;jj++){if(a[ii][jj]==1){p[ii][jj]=1;p[jj][ii]=1;}}}}voidEuler::PrintAM(){cout随机生成的图为：endl;for(inti=0;in;i++){for(intj=0;jn;j++)couta[i][j];coutendl;}}voidEuler::Warshall(){for(inti=0;in;i++)for(intj=0;jn;j++)if(p[j][i]==1){for(intk=0;kn;k++){if(p[j][k]+p[i][k]0)p[j][k]=1;}}}voidEuler::PrintRM(){cout可达性矩阵：endl;for(inti=0;in;i++){for(intj=0;jn;j++)coutp[i][j];coutendl;}}boolEuler::IsConnected(){inti,j;boolflag=true;//flag标记是否连通for(i=0;in;i++){for(j=0;jn;j++)if(p[i][j]==0)//如果可达性矩阵中有一个元素为0，{//就跳出循环，表示该图不连通flag=false;break;}if(!flag)break;}if(!flag)cout该图不是连通的;else{for(i=0;in;i++)for(j=i;jn;j++){if(a[i][j]==1&&i!=j)//由边计算结点的度数{b[i]++;b[j]++;}}}returnflag;}intEuler::IsEorSE(){inti,count=0,begin=-1;cout每个结点的度数：endl;for(i=0;in;i++)couti:b[i]endl;for(i=0;in;i++)//计算奇数结点的个数if(b[i]%2!=0){count++;begin=i;//初始化开始结点，存在奇数结点，则将其中一个作为开始点}if(begin==-1)//不存在奇数结点则将0作为起始点begin=0;if(count==2){cout该图是半欧拉图endl;isEuler=true;//isEuler标记是否是（半）欧拉图}elseif(count==0){cout该图是欧拉图endl;isEuler=true;}returnbegin;}voidEuler::DFS(intbegin){inti,j;bool**visited=newbool*[n];//二维数组记录每条边是否被访问过for(i=0;in;i++)//初始化{visited[i]=newbool[n];for(j=0;jn;j++)if(a[i][j]==1)visited[i][j]=false;elsevisited[i][j]=true;}for(j=0;jn;j++)if(!visited[begin][j]){DFS(begin,j,visited);coutbegin;}for(i=0;in;i++)delete[]visited[i];//释放内存delete[]visited;}voidEuler::DFS(intu,intv,bool**visited){if(!visited[u][v])//判断边u,v是否访问过{visited[u][v]=true;visited[v][u]=true;//标记被访问for(inti=0;in;i++)DFS(v,i,visited);coutv;//输出结点}}intmain(){intn,m,begin;boolflag;cout输入结点个数:;cinn;Eulereuler(n);euler.inputEdge();euler.PrintAM();euler.Warshall();euler.PrintRM();flag=euler.IsConnected();if(flag){begin=euler.IsEorSE();if(euler.isEuler){cout具体路径为：;euler.DFS(begin);}}coutendl;return0;}五、测试数据及其结果分析六、调试过程中的问题可达性矩阵无法正确计算，调试后发现是算法中未正确定义循环变量七、程序设计总结1.掌握了与离散数学理论相关的编程实现思想和方法，掌握了欧拉图和半欧拉图的判定。2.利用邻接矩阵表示存在的边，通过Warshall算法求出无向图的可达性矩阵，如果是连通的话，那么可达性矩阵中每一个元素都应该为1，否则存在元素为0。3.多次利用动态二维数组，并养成了在程序结束时释放动态二维数组内存的习惯。4.明白了欧拉回路属于欧拉路的一种特殊情况，之前一直没有搞清这两者之间的关系。在判断是欧拉图还是半欧拉图时，首先判断是不是连通图，然后判断是否只存在零个或者两个奇数度结点，有两个则是半欧拉图，零个则是欧拉图。5.输出欧拉路时，利用递归深度搜索逆序输出结点，确保找到一条完整的路径，避免存在回路没有被遍历到。评分细则评分项优秀良好中等差遵守机房规章制度上机时的表现学习态度算法思想准备情况程序设计能力解决问题能力课题功能实现情况算法设计合理性算法效能评价报告书写认真程度内容详实程度文字表达熟练程度回答问题准确度简短评语教师签名：年月日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格