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

1、离散数学实验报告（2015 / 2016 学年 第 一 学期）题 目： 图的随机生成及欧拉（回）路的确定 专 业 信息安全 学 生 姓 名 班 级 学 号 指 导 教 师 指 导 单 位 计算机学院计算机科学与技术系 日 期 2015年12月29日 图的随机生成及欧拉（回）路的确定一、 实验内容和要求内容：编程随机生成n个结点的无向图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。要求：对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。2、 实验目的对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的

2、判定，若符合则给出至少一条欧拉回路或欧拉路。三、实验任务 1、输入结点个数据生成随机图2、进行（半）欧拉图的判定3、若是则给出欧拉（回）路。四、实验内容 #include #include #include using namespace std;class Eulerpublic:Euler(int num);Euler();void DFS(int begin); /公有的深度优先搜索函数void inputEdge(); /输入边void PrintAM(); /打印邻接矩阵void PrintRM(); /打印可达性矩阵void Warshall(); /Warshall算法求可达性矩

3、阵bool IsConnected(); / /判断图是否连通int IsEorSE(); /判断图是欧拉图还是半欧拉图bool isEuler;private:void DFS(int u,int v,bool *visited); / /私有的深度优先搜索函数int n;int *a; /定义动态二维数组int *p; /定义可达性矩阵int *b; /存储每个结点的度数;Euler:Euler(int num) /构造函数isEuler=false;n=num;int i,j;a=new int*n;for(i=0;in;i+)ai=new intn;for(j=0;jn;j+)aij=

4、0;p=new int*n;for(i=0;in;i+)pi=new intn;for(j=0;jn;j+)pij=0;b=new intn;for(i=0;in;i+)bi=0;Euler:Euler()/析构函数int i;for(i=0;in;i+) delete ai;delete a;for(i=0;in;i+) delete pi;delete p;delete b;void Euler:inputEdge()srand(unsigned)time(NULL); for(int i = 0; i n; i+) for(int j = i + 1; j n; j+) aij = 0+

5、rand()%2; /随机生成无向图 aji=aij; for(int ii=0;iin;ii+)for(int jj=0;jjn;jj+)if(aiijj=1)piijj=1;pjjii=1;void Euler:PrintAM()cout随机生成的图为：endl;for(int i=0;in;i+)for(int j=0;jn;j+)coutaij ;coutendl;void Euler:Warshall()for(int i=0;in;i+)for(int j=0;jn;j+)if(pji=1)for(int k=0;k0)pjk=1;void Euler:PrintRM()cout可

6、达性矩阵：endl;for(int i=0;in;i+)for(int j=0;jn;j+)coutpij ;coutendl;bool Euler:IsConnected()int i,j;bool flag=true; / /flag标记是否连通for(i=0;in;i+)for(j=0;jn;j+)if(pij=0) /如果可达性矩阵中有一个元素为0， /就跳出循环，表示该图不连通flag=false;break;if(!flag)break;if(!flag)cout该图不是连通的;elsefor(i=0;in;i+)for(j=i;jn;j+)if(aij=1&i!=j) /由边计算

7、结点的度数bi+;bj+;return flag;int Euler:IsEorSE()int i,count=0,begin=-1;cout每个结点的度数：endl;for(i=0;in;i+)couti:biendl;for(i=0;in;i+)/计算奇数结点的个数if(bi%2!=0)count+;begin=i;/初始化开始结点，存在奇数结点，则将其中一个作为开始点if(begin=-1)/不存在奇数结点则将0作为起始点begin=0;if(count=2)cout该图是半欧拉图endl;isEuler=true;/isEuler标记是否是（半）欧拉图else if(count=0)c

8、out该图是欧拉图endl;isEuler=true;return begin;void Euler:DFS(int begin)int i,j;bool *visited=new bool*n;/二维数组记录每条边是否被访问过for(i=0;in;i+)/初始化visitedi=new booln;for(j=0;jn;j+)if(aij=1)visitedij=false;elsevisitedij=true;for(j=0;jn;j+)if(!visitedbeginj) DFS(begin,j,visited);coutbegin ;for(i=0;in;i+) delete visi

9、tedi;/释放内存delete visited;void Euler:DFS(int u,int v,bool *visited)if(!visiteduv)/判断边是否访问过visiteduv=true;visitedvu=true;/标记被访问for(int i=0;in;i+)DFS(v,i,visited);coutv ; /输出结点int main()int n,m,begin;bool flag;coutn;Euler euler(n);euler.inputEdge();euler.PrintAM();euler.Warshall();euler.PrintRM();flag=

10、euler.IsConnected();if(flag) begin=euler.IsEorSE();if(euler.isEuler)cout具体路径为：;euler.DFS(begin);coutendl;return 0;五、测试数据及其结果分析6、 调试过程中的问题可达性矩阵无法正确计算，调试后发现是算法中未正确定义循环变量七、程序设计总结1.掌握了与离散数学理论相关的编程实现思想和方法，掌握了欧拉图和半欧拉图的判定。2.利用邻接矩阵表示存在的边，通过Warshall算法求出无向图的可达性矩阵，如果是连通的话，那么可达性矩阵中每一个元素都应该为1，否则存在元素为0。3.多次利用动态二维数组，并养成了在程序结束时释放动态二维数组内存的习惯。4.明白了欧拉回路属于欧拉路的一种特殊情况，之前一直没有搞清这两者之间的关系。在判断是欧拉图还是半欧拉图时，首先判断是不是连通图，然后判断是否只存在零个或者两个奇数度结点，有两个则是半欧拉图，零个则是欧拉图。5.输出欧拉路时，利用递归深度搜索逆序输出结点，确保找到一条完整的路径