数据结构与算法课程设计报告.doc

合肥学院计算机科学与技术系课程设计报告2012 2013 学年第 2 学期课程 数据结构与算法设计课程设计课程设计名称欧拉回路学生姓名陶飞学号1104012039专业班级计算机科学与技术11级3班指导教师李红，何立新，华珊珊，陈艳平2013 年 3月题目：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？一问题分析和任务定义：题目要求判断一个给定的图中是否存在欧拉回路。由欧拉图的定义，当一个图存在欧拉回路时，该图称为欧拉图。题目问是否存在欧拉回路即等价于问给定的图是否为欧拉图。所以，证明给定图是欧拉图就说明该图存在欧拉回路，否则不存在欧拉回路。根据高等教育出版社出版屈婉玲、耿素云、张立昂主编的离散数学P.296定理15.1可知：无向图G是欧拉图当且仅当G是连通图且没有奇度顶点。要证明一个给定的图是否为欧拉图，证明给定的图是连通图且没有奇度顶点即可。所以，解决题目中的问题就转化为证明给定图是否是连通图且没有奇度顶点。首先要确定一给定的图是否为连通图。这里我们可以通过图的深度优先搜索遍历确定。从任意顶点出发，如果能深度优先遍历到所有的顶点就说明图中所有的顶点都是连图的即为连通图。然后再确定给定的图是否没有奇度顶点。我们可以以邻接矩阵的形式存储给定的图，对邻接矩阵的每行分别行进行扫描，记录每个顶点的度数，当每行扫描完后判断该顶点的度数是否为奇数，存在奇度顶点直接结束扫描，说明存在奇度顶点，给定图不是欧拉图。即不存在欧拉回路。否则继续扫描，当扫描完所有的行没有发现奇度顶点，即说明给定图没有奇度顶点。当上述两个问题都确定以后根据定理，当且仅当给定图为连通图且没有奇度顶点时给定的图为欧拉图。由此可确定，给定的图是否存在欧拉回路。二数据结构的选择与概要设计：1 数据结构的选择：图在我们所学的数据结构与算法课程中有四种存储方式：邻接矩阵、邻接表、十字链表和邻接多重表。本问题比较简单，选用邻接矩阵或邻接矩阵就足够了。在本课程设计中需要判断是否有奇度顶点和是否为连通图，用用邻接表和邻接矩阵在时间繁杂度没有什么大的差别，在空间复杂度上，因为本题是无向图，如果如果用邻接表，储存一条边要储存两次，存储指针比int型的空间消耗大，在图不是很大的情况下，邻接矩阵的空间复杂度要小。同时选用邻接矩阵很容易得到图中个顶点的度数。因为顶点只要求编号这一信息，所以就没有用结构体存储顶点信息，图用邻接矩阵要用结构体存储。结构体定义如下：typedef structint n;/顶点个数int e;/边的条数int vexsMAX_VERTEX_NUM;/一维数组储存顶点int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM;/二维数组储存边MGraph;/图2.概要设计首先将图转换为邻接矩阵存储起来，然后邻接矩阵的每一行进行搜索得图中到每个顶点的度数，如果有奇度顶点，输出：不存在欧拉回路，即可结束程序。否则继续判断给定的图是否为连通图，如果是连通图输出：存在欧拉回路；否则输出：不存在欧拉回路。结束程序。三详细设计和编码：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(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;jedgesij=0;/初始化邻接矩阵表示的所有边printf(请输入边的信息:n);for(i=1;iedgesjk=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;in;i+)/从第一个顶点开始，判断顶点的度数num=0;/初始化每个顶点的度数为0for(j=1;jn;j+)if(mg-edgesij!=0)&(i!=j)/如果顶点i到j的边存在度数加1num=num+1;if(num%2=1)/如果有哪个顶点的度数为奇数，直接退出循环，返回0return 0;return 1;/当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回13. 判断给定的图是否为连通图：本程序的深度优先遍历是一个递归的过程。其中visitedMAX_VERTEX_NUM是一个辅助的全局变量，初始值均为0.表示该顶点没有被访问。访问后用1表示。在深度优先搜索时。我们需要调用dfs_trave()函数。在dfs_trave()中，针对每个没有被访问过的顶点调用dfs()函数，它是一个递归函数，完成从该顶点开始的深度优先搜索。如果图是一个连通图，那么完成对visited数组的初始化后，在dfs_trave()中只需调用dfs()函数一次即可完成对图的遍历。当图不是一个连通图时，则在dfs_trave()中需要针对每个连通分量分别调用dfs()函数。根据dfs()函数被调用的次数就可以判断给定的图是否为连通图。如果dfs()函数被调用一次则给定的图是连通图，否则不是连通图。int dfs_trave(MGraph *mg)/深度优先搜索遍历int i,m=0;for(i=1;in;i+)/将辅助变量全部初始化为0，表明顶点没有被访问过visitedi=0;for(i=1;in;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;jn;j+)if(visitedj=0)&(mg-edgesij=1)/当顶点没有被访问过并且两顶点存在边dfs(mg,j);/对该顶点深度优先搜索4.根据上述2,3可知，必须为连通图且没有奇度顶点才是欧拉图即存在欧拉回路。5.流程图如下（图：1）：开始顶点数、边数、边信息将图转化为邻接矩阵搜索图中所有顶点的度数判断是否存在奇度顶点YN对图进行深度优先搜索遍历对图进行深度优先搜索遍历判断图是否为连通图NY不存在欧拉回路存在欧拉回路结束图：1流程图四上机调试过程：本次实验中也遇到了一些小问题，通过在适当的位置加一些printf语句即可确定出现问题的语句大概的位置。加以分析、修改即可。在本次课程设计的第三组数据的测试时出现了不存在欧拉图的错误结果，仔细分析可知，在（2,2）邻接矩阵的对角线上，所以该点的度数在计算的时候就少1度。所以，在if(mg-edgesij!=0)&(i!=j)/如果顶点i到j的边存在度数加1 的判断中增加了一个判断，当该点存在环，则在度数的计数时忽略不计，这样不会印象该点度数奇偶性的变化。这样就很好的解决了，存在环对判断结果的印象的问题。通过本次课程设计让我更加深刻的体会到调试程序需要平心静气，仔细分析、研究。要有一个严谨的态度，这样才能高效率的写出优质的代码。五测试结果与分析：测试数据的选择：在测试中考虑到多种情况使用了多组数据，分别根据是否为连通图、是否没有奇度顶点设计了一下四组数据。第一组数据为连通图且没有奇度顶点，第二组数据为连通图且有奇度顶点，第三组数据为连通图、没有奇度顶点且有环，第四组数据为非连通图且有奇度顶点，第五组数据为非连通图且没有奇度顶点。每组数据进行多次测试。测试数据1：331 21 32 3测试结果：结果分析：测试数据表示一个3个顶点，3条边的图，顶点两两相连。如下:2-1所示：132图：2-1 测试1存在欧拉回路。测试结果正确。测试数据2：333 21 22 3测试结果：结果分析：测试数据表示一个3个顶点，3条边的图，1,、2相连，2、3相连。如下图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测试结果：结果分析：测试数据表示一个6个顶点，6条边的图，1、2相连，1、3相连,2、3相连,4、5相连，4、6相连，5、6相连。如下图2-5所示：541632图：2-5不存在欧拉回路。测试结果正确。测试结果总结：通过对多种情况设计了多组数据多次测试如上，结果都得到了真确的结论。说明程序符合题目的要求，达到了实验的目的。六用户使用说明：首先本程序中的所有顶点编号为1-N的整数。(0N1000)先输入图顶点的个数要求为一个正整数n，然后输入图所有边的条数要求为正整数e，再图边数行整形数，每行两个数（用空格相隔）表示一条边所连接的两个顶点编号。输出结果即为题目的解。七参考文献：1 王昆仑，李红. 数据结构与算法. 北京：高等教育出版社，2007年6月第1版2 屈婉玲，耿素云，张立昂. 离散数学. 北京：高等教育出版社，2008年3月第1版八附录：#include#include#include#define MAX_VERTEX_NUM 1000/顶点的最大个数typedef structint n;/顶点个数int e;/边的条数int vexsMAX_VERTEX_NUM;/一维数组储存顶点int edgesMAX_VERTEX_NUMMAX_VERTEX_NUM;/二维数组储存边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用来接收图是否为连通图的结果MGraph *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=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;jedgesij=0;/初始化邻接矩阵表示的所有边printf(请输入边的信息:n);for(i=1;iedgesjk=1;mg-edgeskj=1;/标记存在的边return mg;/返回邻接矩阵的首地址int Euleriancycle(MGraph *mg)/判断是否存在欧拉回路int i,j,num;for(i=1;in;i+)/从第一个顶点开始，判断顶点的度数num=0;/初始化每个顶点的度数为0for(j=1;jn;j+)If(mg-edgesij!=0)&(i!=j)/如果顶点i到j的边存在度数加1num=num+1;if(num%2=1)/如果有哪个顶点的度数为奇数，直接退出循环，返回0return 0;return 1;/当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回1int dfs_trave(MGraph *mg)/深度优先搜索遍历int i,m=0;for(i=1;in;i+)/将辅