离散数学实验四报告

《离散数学实验四报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、ntchoice;//告诉函数当前选择的是打印一条欧拉路还是所有欧拉路inthas;//记录是否已经打印过欧拉路intvis[Size][Size];//标记已经走过的路intrecord[Size];//保存当前的欧拉路，用结点表示intcnt;//当前已经走过的边的总数程序宏定义了所有二维数组的大小。#defineSize10002main函数代码：intmain(){do{printf("请输入无向图的结点个数:");scanf("%d",&n);printf("请输入边的个数:");scanf("%d",&m);if(m>n

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

5、----------1.打印一个欧拉回路---");printf("-----------------2.打印所有欧拉回路---");printf("输入你的选择:");scanf("%d",&choice);if(choice==1){printf("其中一条欧拉回路为:");record[cnt++]=0;FindLu(0);//找出回路cnt--;}elseif(choice==2){printf("所有的欧拉回路为:");for(inti=0;i

6、i);cnt--;}}else{printf("-----------------输入有误-----------------");system("pause");}}elseif(tmp==1){printf("这个图是一个半欧拉图");printf("-----------------1.打印一个欧拉路------------------");printf("-----------------2.打印所有欧拉路------------------");printf("输入你的选择:");scanf("%d",&ch

7、oice);if(choice==1){for(inti=0;i

8、++]=i;FindLu(i);cnt--;}}}else{printf("-----------------输入有误-----------------");}}else{printf("这个图既不是欧拉图，也不是半欧拉图")