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

合肥学院 计算机科学与技术系 课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 报告 2012 ～2013 学年第 2 学期 课程 数据结构与算法设计课程设计 课程设计名称 欧拉回路 学生姓名 陶飞 学号 1104012039 专业班级 计算机科学与技术11级3班 指导教师 李红，何立新，华珊珊，陈艳平 2013 年 3月 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目： 欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？ 一．问题分析和任务定义： 题目 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 判断一个给定的图中是否存在欧拉回路。由欧拉图的定义，当一个图存在欧拉回路时，该图称为欧拉图。题目问是否存在欧拉回路即等价于问给定的图是否为欧拉图。所以，证明给定图是欧拉图就说明该图存在欧拉回路，否则不存在欧拉回路。根据高等教育出版社出版屈婉玲、耿素云、张立昂主编的《离散数学》P.296定理15.1可知：无向图G是欧拉图当且仅当G是连通图且没有奇度顶点。要证明一个给定的图是否为欧拉图，证明给定的图是连通图且没有奇度顶点即可。所以，解决题目中的问题就转化为证明给定图是否是连通图且没有奇度顶点。 首先要确定一给定的图是否为连通图。这里我们可以通过图的深度优先搜索遍历确定。从任意顶点出发，如果能深度优先遍历到所有的顶点就说明图中所有的顶点都是连图的即为连通图。 然后再确定给定的图是否没有奇度顶点。我们可以以邻接矩阵的形式存储给定的图，对邻接矩阵的每行分别行进行扫描，记录每个顶点的度数，当每行扫描完后判断该顶点的度数是否为奇数，存在奇度顶点直接结束扫描，说明存在奇度顶点，给定图不是欧拉图。即不存在欧拉回路。否则继续扫描，当扫描完所有的行没有发现奇度顶点，即说明给定图没有奇度顶点。 当上述两个问题都确定以后根据定理，当且仅当给定图为连通图且没有奇度顶点时给定的图为欧拉图。由此可确定，给定的图是否存在欧拉回路。 二．数据结构的选择与概要设计： 1． 数据结构的选择： 图在我们所学的数据结构与算法课程中有四种存储方式：邻接矩阵、邻接表、十字链表和邻接多重表。本问题比较简单，选用邻接矩阵或邻接矩阵就足够了。在本课程设计中需要判断是否有奇度顶点和是否为连通图，用用邻接表和邻接矩阵在时间繁杂度没有什么大的差别，在空间复杂度上，因为本题是无向图，如果如果用邻接表，储存一条边要储存两次，存储指针比int型的空间消耗大，在图不是很大的情况下，邻接矩阵的空间复杂度要小。同时选用邻接矩阵很容易得到图中个顶点的度数。因为顶点只要求编号这一信息，所以就没有用结构体存储顶点信息，图用邻接矩阵要用结构体存储。结构体定义如下： typedef struct { int n;//顶点个数 int e;//边的条数 int vexs[MAX_VERTEX_NUM];//一维数组储存顶点 int edges[MAX_VERTEX_NUM][MAX_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;j<=n;j++) mg->edges[i][j]=0;//初始化邻接矩阵表示的所有边 printf("请输入边的信息:\n"); for(i=1;i<=e;i++) { scanf("%d%d",&j,&k); mg->edges[j][k]=1;mg->edges[k][j]=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<=mg->n;i++)//从第一个顶点开始，判断顶点的度数 { num=0;//初始化每个顶点的度数为0 for(j=1;j<=mg->n;j++) { if((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1 num=num+1; } if(num%2==1)//如果有哪个顶点的度数为奇数，直接退出循环，返回0 return 0; } return 1;//当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回1 } 3. 判断给定的图是否为连通图： 本程序的深度优先遍历是一个递归的过程。其中visited[MAX_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;i<=mg->n;i++)//将辅助变量全部初始化为0，表明顶点没有被访问过 visited[i]=0; for(i=1;i<=mg->n;i++) if(visited[i]==0)//对没有访问过的顶点，调用深度优先搜索函数 { dfs(mg,i);//深度优先搜索 m=m+1;//如果是非连通图，要调用1次以上，m用来记录调用dfs函数的次数 } return m;//返回调用dfs函数的次数 } void dfs(MGraph *mg,int i)//深度优先搜索 { int j; visited[i]=1;//访问该顶点 for(j=1;j<=mg->n;j++) if((visited[j]==0)&&(mg->edges[i][j]==1))//当顶点没有被访问过并且两顶点存在边 dfs(mg,j);//对该顶点深度优先搜索 } 4.根据上述2,3可知，必须为连通图且没有奇度顶点才是欧拉图即存在欧拉回路。 5.流程图如下（图：1）： Y N N Y 图：1流程图 四．上机调试过程： 本次实验中也遇到了一些小问题，通过在适当的位置加一些printf语句即可确定出现问题的语句大概的位置。加以分析、修改即可。 在本次课程设计的第三组数据的测试时出现了不存在欧拉图的错误结果，仔细分析可知，在（2,2）邻接矩阵的对角线上，所以该点的度数在计算的时候就少1度。所以，在if((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1 的判断中增加了一个判断，当该点存在环，则在度数的计数时忽略不计，这样不会印象该点度数奇偶性的变化。这样就很好的解决了，存在环对判断结果的印象的问题。 通过本次课程设计让我更加深刻的体会到调试程序需要平心静气，仔细分析、研究。要有一个严谨的态度，这样才能高效率的写出优质的代码。 五．测试结果与分析： 测试数据的选择： 在测试中考虑到多种情况使用了多组数据，分别根据是否为连通图、是否没有奇度顶点设计了一下四组数据。第一组数据为连通图且没有奇度顶点，第二组数据为连通图且有奇度顶点，第三组数据为连通图、没有奇度顶点且有环，第四组数据为非连通图且有奇度顶点，第五组数据为非连通图且没有奇度顶点。 每组数据进行多次测试。 测试数据1： 3 3 1 2 1 3 2 3 测试结果： 结果分析：测试数据表示一个3个顶点，3条边的图，顶点两两相连。如下:2-1所示： 图：2-1 测试1 存在欧拉回路。测试结果正确。 测试数据2： 3 3 3 2 1 2 2 3 测试结果： 结果分析：测试数据表示一个3个顶点，3条边的图，1,、2相连，2、3相连。如下图2-2所示： 图：2-2 测试2 不存在欧拉回路。测试结果正确。 测试数据:3： 4 5 1 2 1 3 2 4 3 4 2 2 测试结果： 结果分析：测试数据表示一个4个顶点，5条边的图，1、2相连，1、3相连,2、4相连,3、4相连，2、2相连。如下图2-3所示： 图：2-3 测试3 存在欧拉回路。测试结果正确。 测试数据4： 5 4 1 2 3 4 4 5 3 5 测试结果： 结果分析：测试数据表示一个5个顶点，4条边的图，1、2相连，3、4相连,4、5相连,3、5相连。如下:图2-4所示： 不存在欧拉回路。测试结果正确。 图：2-4 测试4 测试数据5： 6 6 1 2 1 3 2 3 4 5 4 6 5 6 测试结果： 结果分析：测试数据表示一个6个顶点，6条边的图，1、2相连，1、3相连,2、3相连,4、5相连，4、6相连，5、6相连。如下图2-5所示： 图：2-5 不存在欧拉回路。测试结果正确。 测试结果总结：通过对多种情况设计了多组数据多次测试如上，结果都得到了真确的结论。说明程序符合题目的要求，达到了实验的目的。 六．用户使用说明： 首先本程序中的所有顶点编号为1-N的整数。(0 #include #include #define MAX_VERTEX_NUM 1000//顶点的最大个数 typedef struct { int n;//顶点个数 int e;//边的条数 int vexs[MAX_VERTEX_NUM];//一维数组储存顶点 int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组储存边 }MGraph;//图 int visited[MAX_VERTEX_NUM];//全局变量。在对顶点进行深度优先搜索遍历时的辅助变量数组 int Euleriancycle(MGraph *mg);//判断顶点的度数是否全为偶数，有奇数时输出0，全为偶数时输出1 MGraph *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=0 if(num!=1) { printf("不存在欧拉图！\n"); getchar(); exit(0); } m=dfs_trave(mg);//判断图是否为连通图 if(m!=1) printf("不存在欧拉图！\n"); else printf("存在欧拉图！\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;j<=n;j++) mg->edges[i][j]=0;//初始化邻接矩阵表示的所有边 printf("请输入边的信息:\n"); for(i=1;i<=e;i++) { scanf("%d%d",&j,&k); mg->edges[j][k]=1;mg->edges[k][j]=1;//标记存在的边 } return mg;//返回邻接矩阵的首地址 } int Euleriancycle(MGraph *mg)//判断是否存在欧拉回路 { int i,j,num; for(i=1;i<=mg->n;i++)//从第一个顶点开始，判断顶点的度数 { num=0;//初始化每个顶点的度数为0 for(j=1;j<=mg->n;j++) { If((mg->edges[i][j]!=0)&&(i!=j))//如果顶点i到j的边存在度数加1 num=num+1; } if(num%2==1)//如果有哪个顶点的度数为奇数，直接退出循环，返回0 return 0; } return 1;//当所有的顶点都判断完成还没有退出本函数说明所有顶点度数均为偶数，返回1 } int dfs_trave(MGraph *mg)//深度优先搜索遍历 { int i,m=0; for(i=1;i<=mg->n;i++)//将辅助变量全部初始化为0，表明顶点没有被访问过 visited[i]=0; for(i=1;i<=mg->n;i++) if(visited[i]==0)//对没有访问过的顶点，调用深度优先搜索函数 { dfs(mg,i);//深度优先搜索 m=m+1;//如果是非连通图，要调用1次以上，m用来记录调用dfs函数的次数 } return m;//返回调用dfs函数的次数 } void dfs(MGraph *mg,int i)//深度优先搜索 { int j; visited[i]=1;//访问该顶点 for(j=1;j<=mg->n;j++) if((visited[j]==0)&&(mg->edges[i][j]==1))//当顶点没有被访问过并且两顶点存在边 dfs(mg,j);//对该顶点深度优先搜索 } 1 2 3 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 开始 顶点数、边数、边信息 将图转化为邻接矩阵 判断是否存在奇度顶点 判断图是否为连通图 对图进行深度优先搜索遍历 搜索图中所有顶点的度数 对图进行深度优先搜索遍历 存在欧拉回路 不存在欧拉回路 结束