欧拉回路--数据结构与算法课程设计报告

1、合肥学院计算机科学与技术系课程设计报告2021 2021 学年第 2 学期课程 数据结构与算法设计课程设计课程设计名称欧拉回路学生姓名 学号 专业班级计算机科学与技术11级3班指导教师 2021 年 3月题目：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？一问题分析和任务定义：题目要求判断一个给定的图中是否存在欧拉回路。由欧拉图的定义，当一个图存在欧拉回路时，该图称为欧拉图。题目问是否存在欧拉回路即等价于问给定的图是否为欧拉图。所以，证明给定图是欧拉图就说明该图存在欧拉回路，否则不存在欧拉回路。根据高等教育出版社出版屈婉玲、耿素

2、云、张立昂主编的离散数学P.296定理15.1可知：无向图G是欧拉图当且仅当G是连通图且没有奇度顶点。要证明一个给定的图是否为欧拉图，证明给定的图是连通图且没有奇度顶点即可。所以，解决题目中的问题就转化为证明给定图是否是连通图且没有奇度顶点。首先要确定一给定的图是否为连通图。这里我们可以通过图的深度优先搜索遍历确定。从任意顶点出发，如果能深度优先遍历到所有的顶点就说明图中所有的顶点都是连图的即为连通图。然后再确定给定的图是否没有奇度顶点。我们可以以邻接矩阵的形式存储给定的图，对邻接矩阵的每行分别行进行扫描，记录每个顶点的度数，当每行扫描完后判断该顶点的度数是否为奇数，存在奇度顶点直接结束扫描，

3、说明存在奇度顶点，给定图不是欧拉图。即不存在欧拉回路。否则继续扫描，当扫描完所有的行没有发现奇度顶点，即说明给定图没有奇度顶点。当上述两个问题都确定以后根据定理，当且仅当给定图为连通图且没有奇度顶点时给定的图为欧拉图。由此可确定，给定的图是否存在欧拉回路。二数据结构的选择与概要设计：1 数据结构的选择：图在我们所学的数据结构与算法课程中有四种存储方式：邻接矩阵、邻接表、十字链表和邻接多重表。本问题比较简单，选用邻接矩阵或邻接矩阵就足够了。在本课程设计中需要判断是否有奇度顶点和是否为连通图，用用邻接表和邻接矩阵在时间繁杂度没有什么大的差别，在空间复杂度上，因为本题是无向图，如果如果用邻接表，储存

4、一条边要储存两次，存储指针比int型的空间消耗大，在图不是很大的情况下，邻接矩阵的空间复杂度要小。同时选用邻接矩阵很容易得到图中个顶点的度数。因为顶点只要求编号这一信息，所以就没有用结构体存储顶点信息，图用邻接矩阵要用结构体存储。结构体定义如下：typedef structint n;/顶点个数int e;/边的条数int vexsMAX_VERTEX_NUM;/一维数组储存顶点int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM;/二维数组储存边MGraph;/图2.概要设计首先将图转换为邻接矩阵存储起来，然后邻接矩阵的每一行进行搜索得图中到每个顶点的度数，如果有奇度顶

5、点，输出：不存在欧拉回路，即可结束程序。否则继续判断给定的图是否为连通图，如果是连通图输出：存在欧拉回路；否则输出：不存在欧拉回路。结束程序。三详细设计和编码：1.将图转化为邻接矩阵存储：先输入图中顶点个个数和边的条数，对所有可能存在的边初始化为0，再依次输入边的信息，即如果顶点1,2存在相连的边，输入1 2 （1,2为自动给顶点分配的编码）。将边1,2的信息改为1。用函数MGraph *creat_MGraph();完成，返回邻接矩阵的首地址即可。MGraph *creat_MGraph()/建立邻接矩阵int i,j,k,n,e;MGraph *mg=malloc(sizeof(MGrap

6、h);printf("请输入顶点的个数：");scanf("%d",&n);printf("请输入边的条数：");scanf("%d",&e);mg->n=n;mg->e=e;getchar();for(i=1;i<=n;i+)for(j=1;j<=n;j+)mg->edgesij=0;/初始化邻接矩阵表示的所有边printf("请输入边的信息:n");for(i=1;i<=e;i+)scanf("%d%d",&j,

7、&k);mg->edgesjk=1;mg->edgeskj=1;/标记存在的边return mg;/返回邻接矩阵的首地址2.搜索有没有奇度顶点：对邻接矩阵的每一行进行搜索，用num记录顶点的度数（每次对新的顶点记录前都将num置为0）。为了排除顶点自身环对判断的影响，当遇到边的两顶点相同，忽略不计，这样不会对结果产生影响。如果搜索到奇度顶点则结束int Euleriancycle(MGraph *mg);函数，返回0，搜索完成且没有发现奇度顶点则返回1.int Euleriancycle(MGraph *mg)/判断是否存在欧拉回路int i,j,num;for(i=1;i

8、<=mg->n;i+)/从第一个顶点开始，判断顶点的度数num=0;/初始化每个顶点的度数为0for(j=1;j<=mg->n;j+)if(mg->edgesij!=0)&&(i!=j)/如果顶点i到j的边存在度数加1num=num+1;if(num%2=1)/如果有哪个顶点的度数为奇数，直接退出循环，返回0return 0;return 1;/当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回13. 判断给定的图是否为连通图：本程序的深度优先遍历是一个递归的过程。其中visitedMAX_VERTEX_NUM是一个辅助的全局变量

9、，初始值均为0.表示该顶点没有被访问。访问后用1表示。在深度优先搜索时。我们需要调用dfs_trave()函数。在dfs_trave()中，针对每个没有被访问过的顶点调用dfs()函数，它是一个递归函数，完成从该顶点开始的深度优先搜索。如果图是一个连通图，那么完成对visited数组的初始化后，在dfs_trave()中只需调用dfs()函数一次即可完成对图的遍历。当图不是一个连通图时，则在dfs_trave()中需要针对每个连通分量分别调用dfs()函数。根据dfs()函数被调用的次数就可以判断给定的图是否为连通图。如果dfs()函数被调用一次则给定的图是连通图，否则不是连通图。int df

10、s_trave(MGraph *mg)/深度优先搜索遍历int i,m=0;for(i=1;i<=mg->n;i+)/将辅助变量全部初始化为0，表明顶点没有被访问过visitedi=0;for(i=1;i<=mg->n;i+)if(visitedi=0)/对没有访问过的顶点，调用深度优先搜索函数dfs(mg,i);/深度优先搜索m=m+1;/如果是非连通图，要调用1次以上，m用来记录调用dfs函数的次数return m;/返回调用dfs函数的次数void dfs(MGraph *mg,int i)/深度优先搜索int j;visitedi=1;/访问该顶点for(j=1

11、;j<=mg->n;j+)if(visitedj=0)&&(mg->edgesij=1)/当顶点没有被访问过并且两顶点存在边dfs(mg,j);/对该顶点深度优先搜索4.根据上述2,3可知，必须为连通图且没有奇度顶点才是欧拉图即存在欧拉回路。5.流程图如下（图：1）：开始顶点数、边数、边信息将图转化为邻接矩阵搜索图中所有顶点的度数判断是否存在奇度顶点YN对图进行深度优先搜索遍历对图进行深度优先搜索遍历判断图是否为连通图NY不存在欧拉回路存在欧拉回路结束图：1流程图四上机调试过程：本次实验中也遇到了一些小问题，通过在适当的位置加一些printf语句即可确定出现问

12、题的语句大概的位置。加以分析、修改即可。在本次课程设计的第三组数据的测试时出现了不存在欧拉图的错误结果，仔细分析可知，在（2,2）邻接矩阵的对角线上，所以该点的度数在计算的时候就少1度。所以，在if(mg->edgesij!=0)&&(i!=j)/如果顶点i到j的边存在度数加1 的判断中增加了一个判断，当该点存在环，则在度数的计数时忽略不计，这样不会印象该点度数奇偶性的变化。这样就很好的解决了，存在环对判断结果的印象的问题。通过本次课程设计让我更加深刻的体会到调试程序需要平心静气，仔细分析、研究。要有一个严谨的态度，这样才能高效率的写出优质的代码。五测试结果与分析：测试数

13、据的选择：在测试中考虑到多种情况使用了多组数据，分别根据是否为连通图、是否没有奇度顶点设计了一下四组数据。第一组数据为连通图且没有奇度顶点，第二组数据为连通图且有奇度顶点，第三组数据为连通图、没有奇度顶点且有环，第四组数据为非连通图且有奇度顶点，第五组数据为非连通图且没有奇度顶点。每组数据进行多次测试。测试数据1：331 21 32 3测试结果：结果分析：测试数据表示一个3个顶点，3条边的图，顶点两两相连。如下:2-1所示：132图：2-1 测试1存在欧拉回路。测试结果正确。测试数据2：333 21 22 3测试结果：结果分析：测试数据表示一个3个顶点，3条边的图，1,、2相连，2、3相连。如

14、下图2-2所示：123图：2-2 测试2不存在欧拉回路。测试结果正确。测试数据:3：451 21 32 43 42 2测试结果： 结果分析：测试数据表示一个4个顶点，5条边的图，1、2相连，1、3相连,2、4相连,3、4相连，2、2相连。如下图2-3所示：2134图：2-3 测试3存在欧拉回路。测试结果正确。测试数据4：541 23 4 4 53 5测试结果：结果分析：测试数据表示一个5个顶点，4条边的图，1、2相连，3、4相连,4、5相连,3、5相连。如下:图2-4所示：31542不存在欧拉回路。测试结果正确。图：2-4 测试4测试数据5：661 2 1 32 34 54 65 6测试结果：

15、结果分析：测试数据表示一个6个顶点，6条边的图，1、2相连，1、3相连,2、3相连,4、5相连，4、6相连，5、6相连。如下图2-5所示：541632图：2-5不存在欧拉回路。测试结果正确。测试结果总结：通过对多种情况设计了多组数据多次测试如上，结果都得到了真确的结论。说明程序符合题目的要求，达到了实验的目的。六用户使用说明：首先本程序中的所有顶点编号为1-N的整数。(0<N<1000)先输入图顶点的个数要求为一个正整数n，然后输入图所有边的条数要求为正整数e，再图边数行整形数，每行两个数（用空格相隔）表示一条边所连接的两个顶点编号。输出结果即为题目的解。七参考文献：1 王昆仑，李

16、红. 数据结构与算法. 北京：高等教育出版社，2021 年6月第1版2 屈婉玲，耿素云，张立昂. 离散数学. 北京：高等教育出版社，2021年3月第1版八附录：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAX_VERTEX_NUM 1000/顶点的最大个数typedef structint n;/顶点个数int e;/边的条数int vexsMAX_VERTEX_NUM;/一维数组储存顶点int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM;/二维数组储存边

17、MGraph;/图int visitedMAX_VERTEX_NUM;/全局变量。在对顶点进行深度优先搜索遍历时的辅助变量数组int Euleriancycle(MGraph *mg);/判断顶点的度数是否全为偶数，有奇数时输出0，全为偶数时输出1MGraph *creat_MGraph();/将图转化为邻接矩阵储存起来，返回邻接矩阵的首地址int dfs_trave(MGraph *mg);/深度优先搜索遍历void dfs(MGraph *mg,int i);/深度优先搜索void main()int num,m;/num用来接收顶点度数判断的结果，m用来接收图是否为连通图的结果MGrap

18、h *mg;mg=creat_MGraph();/建立邻接矩阵num=Euleriancycle(mg);/判断顶点的度数是否全为偶数。全为偶数时num=1；否则num=0if(num!=1)printf("不存在欧拉图！n");getchar();exit(0);m=dfs_trave(mg);/判断图是否为连通图if(m!=1)printf("不存在欧拉图！n");elseprintf("存在欧拉图！n");getch();MGraph *creat_MGraph()/建立邻接矩阵int i,j,k,n,e;MGraph *mg=

19、malloc(sizeof(MGraph);printf("请输入顶点的个数：");scanf("%d",&n);printf("请输入边的条数：");scanf("%d",&e);mg->n=n;mg->e=e;getchar();for(i=1;i<=n;i+)for(j=1;j<=n;j+)mg->edgesij=0;/初始化邻接矩阵表示的所有边printf("请输入边的信息:n");for(i=1;i<=e;i+)scanf("

20、;%d%d",&j,&k);mg->edgesjk=1;mg->edgeskj=1;/标记存在的边return mg;/返回邻接矩阵的首地址int Euleriancycle(MGraph *mg)/判断是否存在欧拉回路int i,j,num;for(i=1;i<=mg->n;i+)/从第一个顶点开始，判断顶点的度数num=0;/初始化每个顶点的度数为0for(j=1;j<=mg->n;j+)If(mg->edgesij!=0)&&(i!=j)/如果顶点i到j的边存在度数加1num=num+1;if(num%2

21、=1)/如果有哪个顶点的度数为奇数，直接退出循环，返回0return 0;return 1;/当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回1int dfs_trave(MGraph *mg)/深度优先搜索遍历int i,m=0;for(i=1;i<=mg->n;i+)/将辅助变量全部初始化为0，表明顶点没有被访问过visitedi=0;for(i=1;i<=mg->n;i+)if(visitedi=0)/对没有访问过的顶点，调用深度优先搜索函数dfs(mg,i);/深度优先搜索m=m+1;/如果是非连通图，要调用1次以上，m用来记录调用dfs函数

22、的次数return m;/返回调用dfs函数的次数void dfs(MGraph *mg,int i)/深度优先搜索int j;visitedi=1;/访问该顶点for(j=1;j<=mg->n;j+)if(visitedj=0)&&(mg->edgesij=1)/当顶点没有被访问过并且两顶点存在边dfs(mg,j);/对该顶点深度优先搜索 教师见习报告总结期待已久的见习已经结束了，在龙岩三中高中部见习听课，虽然只是短短的两个星期，但感触还是蛮深的，以前作为一名学生坐在课室听课，和现在作为一名准教师坐在课室听课是完全不同的感受，感觉自己学到了一些在平时课堂上学

23、不到的东西。在这里，我获得的不仅是经验上的收获，更多是教学管理，课堂教学等的理念，以及他们带给我的种种思考。教育见习实践过程：听课。教育见习的主要目的是让学生在指导教师的引导下，观摩教师上课方法、技巧等。听课是教育见习的主要内容。我院规定在一周的见习中需完成至少6课的见习任务。我在教师的安排指导下，分别对高一、高二物理专业课型为主，其他课型齐头的方式，积极主动的完成了听课任务，收到良好的效果。我听的第一节课是高二（8）班，这是一个平衡班，水平不如实验班高。在上课前。科任老师已经跟我说了这个班的纪律是比较差的，而且成绩也不是很好。在我听课期间，确实有几个学生在课堂上说话，但是我发现了一个有趣的现

24、象，这个现象我在往后的几个班都发现了，就是绝大部分的学生的学习热情都好高涨，积极举手发言，积极参与课堂活动。我跟老师们提起这个现象的时候，科任老师就跟我说，一个班里不可能所有的学生都能全神贯注地听完一节课，所以作为一名教师，应该想办法吸引学生的注意力，调动的积极性，比如可以以小组为单位，以抢答计分的形式调动学生的积极性，这样课堂气氛就会活跃起来了。在为期两周的见习工作中，我真的有很大的感触，我第一次感受到自己已经从一名学生向一名教师靠近，走在校园里，每当有学生叫我一声老师，我在感到无比自豪的同时，还感受到了自己的责任。见习工作结束了，我要回到学校继续我的学习了，但是我会好好记住我从*中学学到的

25、一切，并应用于我的专业学习中去。一、教学管理理念 在龙岩三中，从领导阶层到一位普通的科任老师，都秉承以学生为主体的宗旨进行学校的管理，进行教学工作的开展。作为一个课程改革的示范学校，一个教育实验基地。这所学校鼓励着老师做各种研究，各种改革。每个班主任都有着自己的管理经验与管理宗旨。有了这种思想的自由，自然这里也就充满着探索与尝试，从而有所创造与进步。在我见习的班集体中，班主任对他的学生说：“我要让你们成为学习型的管理者，也是管理型的学习者。”这样一句简单的话，让我感到这里老师进行班级管理的良苦用心。他们关心的不只是学生的学习，更多的是从一个完整的人的概念出发，去培养学生多方面的素质。

26、二、教学理念 在见习期间，借着录课的机会，我听了很多的市级，校级的公开棵，还有理科实验班的课。在这些课堂上，让我看到教学改革正在悄然进行，有意识的老师正在努力体会“以学生为主体”的课堂模式。学生的创造也逐步成为教师追求的教学效果。其次，这里的老师也都在适应着多媒体教学，信息化教学，使得课堂更加生动，资源更加丰富，学生获取学习资源的渠道也就更多。尽管，这种教学理念、教学模式的推广仍然有很长的路，但似乎也并不遥远，相信，这股改革的浪潮会给教育领域带来很大的冲击。 三、实际工作经验 在上面，是我在这所学校感受最深刻，也是认为最有意义的收获。实际工作经验上，由于在指导老师的指导下，也获取了许多。 在班主任工作上，我认识到了一个老师的表率作用是很大的，学生时刻看老师，作为一个老师，应该从自己严格要求，并影响感染学生。这就要求师生