NUAA离散数学课设报告，包含源代码 （一专业96分）

目录

实现求欧拉回路算法 ........................................................................................................................................2

162110304 李欣彤....................................................................................................................................2

一些前情提要： ........................................................................................................................................2

输入......................................................................................................................................................2

算法 ........................................................................................................................................................................2

无向图 ..........................................................................................................................................................3

时间复杂度与空间复杂度.............................................................................................................4

框图（无向图） ...............................................................................................................................5

全部源代码........................................................................................................................................................22

无向图........................................................................................................................................................22

有向图........................................................................................................................................................26

已答辩

实现求欧拉回路算法

162110304 李欣彤

一些前情提要：

1. 无向图和有向图都用邻接矩阵存储，该邻接矩阵不是正好的，多出来一行一

列（第一行和第一列），这样提高了可读性。

2. 创建一维 vector 容器 degree，用于存放每个顶点的度数（无向图用到，有向

7. 变量 n 是无向图的总顶点数，m 是总边数。

输入

1. 首先输入 n 和 m，然后根据图输入每条边关联的两个顶点，注意：无向图不

用注意输入顶点的次序，有向图需根据边的方向依次输入与其关联的顶点。

2. 一边输入一边形成邻接矩阵。

算法

上面讲的都是有向图和无向图共同拥有的，下面讲不同的

无向图

1. 输入完成之后，先判断该图是不是平凡图，是平凡图输出“平凡图也是欧拉

图”，结束程序运行；若不是，程序继续运行。

（2） 接下来我们用 while 循环语句来进行连通图的判断，循环条件为队列 q

不为空，此时令 start=q.front()，然后删除 q 最前面的元素，这一步骤

是为了删除已经走过的顶点。

（3） 接下来用 for 循环遍历，如果此时对应的顶点 start 存在邻接的顶点

（vec[start][i]!=0），并且 B[i]==false（没走过这个顶点），那我们将顶

点 i 插入队列中，并让 B[i]=true，代表已经走过该顶点。

（4） 重复（2），（3）步骤直至队列为空。

（5） 此时我们回到 main 函数中，用 for 循环语句进行判断，如果存在任意

顶点 b[i]==false，证明该图不是连通的，结束程序运行。

4. 紧接着我们判断每个顶点的度数，遍历所有顶点：

（2） for 循环遍历无向图的邻接矩阵，如果当前对应 vec[node][i] 的值不为

0，那么证明 node 与 i 点之间存在一条边，将 vec[node][i]与 vec[i][node]

的值都减 1 后，我们递归调用该函数，此时参数 node=i，参数

num=n。

（3） 在递归调用下面的语句是将本次的 i 值插入栈中，注意，该语句不能

写在 for 循环外面，必须写在 for 循环里面，不然每次插入栈中的值都

是 5。

（4） 重复步骤（2），直至结束，此时我们也找出了欧拉回路。

6. 打印欧拉回路。程序运行结束。

时间复杂度与空间复杂度