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

h

合肥学院

计算机科学与技术系

课程设计报告

2012～2013学年第2学期

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

课程设计名称欧拉回路

学生姓名陶飞

学号1104012039

专业班级计算机科学与技术11级3班

指导教师李红，何立新，华珊珊，陈艳平

2013年3月

h

h

题目：

欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现

给定一个图，问是否存在欧拉回路？

一．问题分析和任务定义：

题目要求判断一个给定的图中是否存在欧拉回路。由欧拉图的定义，当一个图存在欧拉

回路时，该图称为欧拉图。题目问是否存在欧拉回路即等价于问给定的图是否为欧拉图。所

以，证明给定图是欧拉图就说明该图存在欧拉回路，否则不存在欧拉回路。根据高等教育出

版社出版屈婉玲、耿素云、张立昂主编的《离散数学》P.296定理15.1可知：无向图G是

欧拉图当且仅当G是连通图且没有奇度顶点。要证明一个给定的图是否为欧拉图，证明给定

的图是连通图且没有奇度顶点即可。所以，解决题目中的问题就转化为证明给定图是否是连

通图且没有奇度顶点。

首先要确定一给定的图是否为连通图。这里我们可以通过图的深度优先搜索遍历确定。

从任意顶点出发，如果能深度优先遍历到所有的顶点就说明图中所有的顶点都是连图的即为

连通图。

然后再确定给定的图是否没有奇度顶点。我们可以以邻接矩阵的形式存储给定的图，对

邻接矩阵的每行分别行进行扫描，记录每个顶点的度数，当每行扫描完后判断该顶点的度数

是否为奇数，存在奇度顶点直接结束扫描，说明存在奇度顶点，给定图不是欧拉图。即不存

在欧拉回路。否则继续扫描，当扫描完所有的行没有发现奇度顶点，即说明给定图没有奇度

顶点。

当上述两个问题都确定以后根据定理，当且仅当给定图为连通图且没有奇度顶点时给定

的图为欧拉图。由此可确定，给定的图是否存在欧拉回路。

二．数据结构的选择与概要设计：

1．数据结构的选择：

图在我们所学的数据结构与算法课程中有四种存储方式：邻接矩阵、邻接表、十字链表

和邻接多重表。本问题比较简单，选用邻接矩阵或邻接矩阵就足够了。在本课程设计中需要

判断是否有奇度顶点和是否为连通图，用用邻接表和邻接矩阵在时间繁杂度没有什么大的差

别，在空间复杂度上，因为本题是无向图，如果如果用邻接表，储存一条边要储存两次，存

储指针比int型的空间消耗大，在图不是很大的情况下，邻接矩阵的空间复杂度要小。同时

选用邻接矩阵很容易得到图中个顶点的度数。因为顶点只要求编号这一信息，所以就没有用

结构体存储顶点信息，图用邻接矩阵要用结构体存储。结构体定义如下：

typedefstruct

{

intn;//顶点个数

inte;//边的条数

intvexs[MAX_VERTEX_NUM];//一维数组储存顶点

intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组储存边

}MGraph;//图

2.概要设计

首先将图转换为邻接矩阵存储起来，然后邻接矩阵的每一行进行搜索得图中到每个顶点

h

h

的度数，如果有奇度顶点，