离散数学实验四报告

1、实 验 报 告（2016 / 2017 学年 第 一 学期）课程名称离散数学实验名称图的随机生成及欧拉（回）路的确定实 验 报 告实验名称图的随机生成及欧拉（回）路的确定指导教师实验类型验证实验学时4实验时间一、 实验目的和要求内容：编程随机生成n个结点的无向图并能进行（半）欧拉图的判定，若是则给出欧拉（回）路。要求：对给定n个结点，随机生成邻接矩阵以确定某无向简单图并进行欧拉图和半欧拉图的判定，若符合则给出至少一条欧拉回路或欧拉路。二、实验环境(实验设备)硬件：X64架构计算机一台系统：Windows 7 64位IDE：Codeblocks 16.01 64位编译器：GUN GCC Comp

2、iler三、实验原理及内容 程序的能够根据输入的n和m，随机生成具有n个结点m个边的简单无向图（能够判断n和m的合理性），然后判断图的连通性，如果这个图是个连通图，再计算图中度数是奇数的结点个数，判断是欧拉图还是半欧拉图，如果是欧拉图或者半欧拉图，然后根据输入打印一个欧拉(回)路,或者所有的欧拉(回)图。 图一：程序流程图 程序用到的全局变量（将数组定义成全局变量可以让数组开得更大）：int n,m; /图的结点数和边数int GSizeSize; /图的邻接矩阵FindLu函数(打印欧拉路)用到的全局变量int choice;/告诉函数当前选择的是打印一条欧拉路还是所有欧拉路int has;

3、/记录是否已经打印过欧拉路int visSizeSize; /标记已经走过的路int recordSize; /保存当前的欧拉路，用结点表示int cnt; /当前已经走过的边的总数程序宏定义了所有二维数组的大小。#define Size 1000main函数代码：int main() do printf("请输入无向图的结点个数:"); scanf("%d",&n); printf("请输入边的个数:"); scanf("%d",&m); if(m>n*(n-1)/2) printf(&qu

4、ot;%d个结点的无向图最多有%d条边n",n,n*(n-1)/2); while(m>n*(n-1)/2); /判断n和m的合理性 Generate(); /随机生成图 if(JudgeLianTong()=0) /判断连通性 printf("这个图不是一个连通图，所以也不是欧拉图和半欧拉图n"); else printf("n这个图是连通图n"); int tmp=Judge(); /判断(半)欧拉图 if(tmp=0) printf("这个图是一个 欧拉图n"); printf("-1.打印一个欧拉回路

5、-n"); printf("-2.打印所有欧拉回路-n"); printf(" 输入你的选择:"); scanf("%d",&choice); if(choice=1) printf("其中一条欧拉回路为:n"); recordcnt+=0; FindLu(0); /找出回路 cnt-; else if(choice=2) printf("所有的欧拉回路为:n"); for(int i=0;i<n;i+) recordcnt+=i; FindLu(i); cnt-; el

6、se printf("-输入有误-n"); system("pause"); else if(tmp=1) printf("这个图是一个 半欧拉图n"); printf("-1.打印一个欧拉路-n"); printf("-2.打印所有欧拉路-n"); printf(" 输入你的选择:"); scanf("%d",&choice); if(choice=1) for(int i=0;i<n;i+) int t=0; for(int j=0;j&

7、lt;n;j+) if(Gij=1) t+; if(t%2=1) recordcnt+=i; FindLu(i); cnt-; break; else if(choice=2) printf("所有的欧拉路为:n"); for(int i=0;i<n;i+) int t=0; for(int j=0;j<n;j+) if(Gij=1) t+; if(t%2=1) recordcnt+=i; FindLu(i); cnt-; else printf("-输入有误-n"); else printf("这个图既不是欧拉图，也不是半欧拉图n

8、"); return 0;（一）随机生成图根据主函数输入的n和m，随机生成具有n个结点和m条边的简单无向图。思路为：每次随机生成一条从结点x到结点y的边，如果这条边不是自环并且这条边之前没有添加过，就将这条边添加到无向图中，并且将已经有的边数+1，当已经有的边数达到m的时候，停止添加边。具体做法为：首先要在头文件包含ctime和cstdlib，调用srand函数产生随机数种子，给变量x和y进行随机数赋值，然后判断这条边是不是自环并且这条边之前有没有添加过，如果符合让Gxy=Gyx=1，并且让保存当前已有的边数的变量cnt加1，当cnt为m时，结束。代码：void Generate()

9、 /随机生成图 printf("正在生成%d个结点%d条边的简单无向图.n",n,m); int cnt=0; srand(time(NULL); while(cnt<m) int x=rand()%n; int y=rand()%n; if(x!=y && Gxy=0)/如果这条边不是自环并且这条边之前没有添加过 Gxy=1; Gyx=1; cnt+; printf("生成完成nn");if(n<=10) /如果结点数少，将邻接矩阵打印出来 printf("图的邻接矩阵为:n"); for(int i=0

10、;i<n;i+) for(int j=0;j<n;j+) printf("%d ",Gij); printf("n"); printf("n");（二）判断连通性 判断一个图的连通性本来可以用图的深度优先遍历(或者宽度优先遍历)，看能不能在一次DFS中访问所有的结点，这样反而更简单，且时间复杂度只有n的平方。但是为了巩固书上的知识点，这里采用了计算可达性矩阵的方法(时间复杂度n的4次方)。 由于数据量大的时候多个二维数组可能会占用太大的空间，所以采用的方法是每计算一次G(图的邻接矩阵) 的n次方，就将计算结果与当前保存可达

11、性矩阵的P进行或运算。矩阵的相乘运算直接用循环就可以完成。并且用一个矩阵T来保存当前G的n次方，计算G的n+1次方只要将T与G相乘即可。代码：全局变量：int PSizeSize; /可达性矩阵int TSizeSize; /临时存放G的n次方的矩阵int TTSizeSize; /临时保存计算结果的矩阵int JudgeLianTong() /判断连通性 for(int i=0;i<n;i+) for(int j=0;j<n;j+) Pij=Gij; Tij=Gij; for(int k=2;k<=n;k+) /n的4次方复杂度,计算可达性矩阵 for(int i=0;i&

12、lt;n;i+) for(int j=0;j<n;j+) int t=0; for(int a=0;a<n;a+) t+=Tia*Gaj; if(t=0) TTij=0; else TTij=1; for(int i=0;i<n;i+) for(int j=0;j<n;j+) Tij=TTij; for(int i=0;i<n;i+) for(int j=0;j<n;j+) if(Tij>0 | Pij>0 ) Pij=1; for(int i=0;i<n;i+) for(int j=0;j<n;j+) if(i!=j &&a

13、mp; Pij =0)/可达性矩阵在非对角线发现了0元素 return 0; return 1;（三）判断(半)欧拉图如果上面一步的连通性判断中，判断出图是一个连通图，那么就要根据奇数度结点个数判断是不是(半)欧拉图。判断的思路是计算出图中奇数度结点的个数，如果奇数度结点个数是0，函数返回0，表示是欧拉图。如果奇数度结点是2，函数返回1，表示是半欧拉图。如果奇数度结点个数大于2，返回-1，表示既不是欧拉图也不是半欧拉图。计算每一个结点的度的时候，由于是邻接矩阵的无向图，结点i的度数就是第i行中元素值是1的个数，for循环扫描一下即可，时间复杂度n的平方。代码：int Judge() /判断(半

14、)欧拉图 int flag=0; for(int i=0;i<n;i+) int cnt=0; for(int j=0;j<n;j+) if(Gij=1) cnt+; if(cnt%2=1) flag+; if(flag=0) return 0; /欧拉回路 else if(flag=2) return 1; /欧拉路 else return -1; /不是欧拉路也不是欧拉回路 （四）打印当前欧拉(ui 回)路如果是打印欧拉回路，那么可以以任意结点作为起点。如果是打印欧拉路，就要以奇数度结点作为起点。采用回溯法找出欧拉(回)路，将DFS做一些改进，用回溯法进行试探，一旦找到一条没有

15、重复的m条边的路，就是欧拉(回)路，然后将其打印，如果试探失败，就返回上一层，改回相应的标记信息，重新试探下一种可能。如果是只需要打印一条路，那么打印完就将全局变量has标记为1，结束。如果是打印所有的路，最外层调用的时候要从所有可能的起点分别调用，每一个起点都要打印所有可能的路。代码：全局变量：int choice;/告诉函数当前选择的是打印一条欧拉路还是所有欧拉路int has;/记录是否已经打印过欧拉路int visSizeSize; /记录已经走过的路int recordSize; /保存当前的欧拉路，用结点表示int cnt; /当前已经走过的边的总数void FindLu(int

16、cur) if(choice=1 && has=1) return; if(cnt=m+1) for(int i=0;i<cnt;i+) if(i=0) printf("%d",recordi); else printf("->%d",recordi); printf("n"); has=1; else for(int i=0;i<n;i+) if(Gcuri=1 && viscuri=0 ) visicur=viscuri=1; recordcnt+=i; FindLu(i); cn

17、t-; visicur=viscuri=0; 如果是欧拉图，main函数最外层的调用为： int tmp=Judge(); /判断(半)欧拉图，用tmp保存结果 if(tmp=0) printf("这个图是一个 欧拉图n"); printf("-1.打印一个欧拉回路-n"); printf("-2.打印所有欧拉回路-n"); printf(" 输入你的选择:"); scanf("%d",&choice); if(choice=1) printf("其中一条欧拉回路为:n&quo

18、t;); recordcnt+=0; FindLu(0); /找出回路 cnt-; else if(choice=2) printf("所有的欧拉回路为:n"); for(int i=0;i<n;i+) recordcnt+=i; FindLu(i); cnt-; else printf("-输入有误-n"); system("pause"); 如果是半欧拉图，main函数最外层的调用为： else if(tmp=1) printf("这个图是一个 半欧拉图n"); printf("-1.打印一个欧拉路-n"); printf("-2.打印所有欧拉路-n"); printf(" 输入你的选择:"); scanf("%d",&choice); if(choice=1) for(int i=0;i<n;i+) int t=0; for