一、算法介绍及实现过程：

1. 程序的输入为对应图的结点数和图中与各结点相连的点的编号。（注：无向图中的多重边和自环需多次输入；有向图中的多重边需多次输入）
2. 程序的第一步是求出图的邻接矩阵。邻接矩阵反映了点与点之间的关系，通过输入各结点相连的点的编号，建立邻接矩阵，并打印出来。
3. 程序的第二步是判断图的连通性。我主要采用了DFS，即暴力递归的方法。无向图中若存在欧拉回路，则必然是连通的；有向图中若存在欧拉回路，则必然是强连通的。因此，二者均可采用同种遍历方法：从一点出发向下遍历，标记经过的点（遇到标记过的点，则直接跳过），最后检查是否所有的点均被标记。区别在于，无向图选取任意一点作为起始点，结果相同；但有向图，从某一点开始未能标记全部点，只能说明该图不是强连通图（不能证明其不连通），但可以确定其不存在欧拉回路。
4. 程序的第三步是判断是否有欧拉回路。运用知识点：无向图有欧拉回路，则无奇度顶点；有向图有欧拉回路，则所有顶点的出度等于入度。使用双层循环遍历邻接矩阵，对无向图求每行的和，并判断是否为偶数；对有向图分别求第n行和第n列的和，并判断二者是否相等。
5. 程序的最后一步是在有欧拉回路的情况下，输出一条欧拉回路。这里，我同样采用了DFS，但准确的来说，是逐步插入回路法，也称Hierholzer 算法。该算法的核心思想是逐个寻找回路，过程中删除经过的路线，并通过回溯，从一个回路末端进入到下一个回溯的入口，并把相应的点加入到路线中。通俗的说，就是不断地寻找图中的回路，并把沿途路线删掉，找到了一个回路，就相当于从图中删除了这个回路，对欧拉图而言，删掉了一个回路，剩下部分的仍然构成欧拉图，然后回溯到上一个非末端点（把末端点加入路线），继续寻找回路。直到找到了所有的回路，这些回路的路线连起来就构成了一条欧拉回路，之后，开始回溯，把该路线记录下来。

二、算法的表示框图:

1、总体框架：

 2、判断连通性的算法示意图：

3、求欧拉回路的算法示意图：

 三、程序源代码

# include <iostream>
# include <algorithm>
# define maxn 101
using namespace std;int n, m, g; //n为点数，m为边数，g为图的类型（1.无向图 2.有向图）
int Matrix[maxn][maxn] = { {0} }; //图的邻接矩阵(初始化为0)(从1开始)
int Path[maxn] = { 0 };          //欧拉回路
int total = 0;                   //加入欧拉回路的点
void Get_Matrix();  //求图的邻接矩阵
void Print_Matrix();     //打印图的邻接矩阵
bool Judge_Connect();    //判断图是否连通
bool Judge_Path();  //判断图是否有欧拉回路
void Find_Path();   //从图中任找一条欧拉回路int main()
{bool temp;cout << "图的类型：1.无向图 2.有向图" << endl;cout << "请输入:";cin >> g;cout << "请输入结点的数目：";cin >> n;Get_Matrix();          //求图的邻接矩阵Print_Matrix();         //打印图的邻接矩阵temp=Judge_Connect();   //判断图是否连通if (temp) {temp = Judge_Path();    //判断图是否有欧拉回路if (temp) {cout << "\n该图中共有" << m << "条边" << endl;Find_Path();        //从图中任找一条欧拉回路}}return 0;
}void Get_Matrix()  //求图的邻接矩阵
{if (g == 1) {cout << "请输入无向图中各点所连接的点的编号：（有重边、自环则多次输入，输入0代表结束）" << endl;}else {cout << "请输入有向图中各点所指向的点的编号：（有重边则多次输入，输入0代表结束）" << endl;}for (int i = 1; i <= n; i++) {int j;cout << "v" << i << ":";cin >> j;while (j != 0) {Matrix[i][j]++;cin >> j;}}
}void Print_Matrix() //打印图的邻接矩阵
{cout << "\n该图的邻接矩阵为：" << endl;cout << "  ";for (int i = 1; i <= n; i++) {cout << " v" << i;}cout << endl;for (int i = 1; i <= n; i++) {cout << "v" << i << " ";for (int j = 1; j <= n; j++) {cout << Matrix[i][j]<<"  ";}cout << endl;}
}void DFS1(int x,int *p) //用递归搜寻各点，检验是否连通
{p[x] = 1;for (int i = 1; i <= n; i++) {if (p[i] == 1) {  //点已被记录过，跳过continue;}if (Matrix[x][i] > 0) { DFS1(i, p); //进入与该点连通的未记录的下一个点}}
}bool Judge_Connect()  //判断图是否连通
{int t = 1;int Point[maxn] = { 0 }; //判断点是否连通DFS1(1, Point); //连通，则所有的点均会被置为1for (int i = 1; i <= n; i++) { //检查各点是否均被记录if (!Point[i]) {  //存在未记录的点，说明不连通t = 0;break;}}if (t) {cout << "\n连通性：该图连通" << endl;return true;}else {if (g == 1) {cout << "\n连通性：该无向图不连通" << endl;}else {cout << "\n连通性：该有向图不强连通" << endl;}return false;}
}bool Judge_Path()   //判断图是否有欧拉回路
{int t = 1, sum = 0;if (g == 1) { //无向图int d;for (int i = 1; i <= n; i++) { d = 0;for (int j = 1; j <= n; j++) {d += Matrix[i][j]; //求度数}if (d % 2 != 0) { //检验度数是否为偶数t = 0;break;}sum += d;}m = sum / 2; //无向图的边数}else {  //有向图int d1, d2;for (int i = 1; i <= n; i++) {d1 = 0;d2 = 0;for (int j = 1; j <= n; j++) {d1 += Matrix[i][j];  //求出度}for (int j = 1; j <= n; j++) {d2 += Matrix[j][i];  //求入读}if (d1 != d2) { //检验出度和入读是否相等t = 0;break;}sum += d1;}m = sum; //有向图的边数}if (t) {cout << "\n该图存在欧拉回路" << endl;return true;}else {cout<< "\n该图不存在欧拉回路" << endl;return false;}
}void DFS2(int x) //用递归通过各边(插入回路法)
{for (int i = 1; i <= n; i++) {if (Matrix[x][i] > 0) { //点x存在到点i的通路Matrix[x][i]--;     //消去走过的路if (g == 1) {Matrix[i][x]--;}DFS2(i);         //继续向下遍历}}total++;  Path[total] = x;  //回溯到无法继续走的点，则加入回路
}void Find_Path()   //从图中任找一条欧拉回路
{DFS2(1);cout << "其中一条欧拉回路为：";int i;for (i = m + 1; i > 1; i--) { //倒序输出cout << "v" << Path[i] << "->";}cout << "v" << Path[1];cout << endl;
}

四、测试用例

示例1：

图的类型：1.无向图 2.有向图
请输入:1
请输入结点的数目：6
请输入无向图中各点所连接的点的编号：（有重边、自环则多次输入，输入0代表结束）
v1:2 5 6 3 0
v2:1 5 4 3 0
v3:1 6 4 2 0
v4:2 5 6 3 0
v5:1 2 4 6 0
v6:1 5 4 3 0该图的邻接矩阵为：v1 v2 v3 v4 v5 v6
v1 0  1  1  0  1  1
v2 1  0  1  1  1  0
v3 1  1  0  1  0  1
v4 0  1  1  0  1  1
v5 1  1  0  1  0  1
v6 1  0  1  1  1  0连通性：该图连通该图存在欧拉回路该图中共有12条边
其中一条欧拉回路为：v1->v2->v3->v1->v5->v2->v4->v3->v6->v4->v5->v6->v1

示例2： 

图的类型：1.无向图 2.有向图
请输入:2
请输入结点的数目：4
请输入有向图中各点所指向的点的编号：（有重边则多次输入，输入0代表结束）
v1:4 0
v2:1 4 0
v3:2 0
v4:2 3 4 0该图的邻接矩阵为：v1 v2 v3 v4
v1 0  0  0  1
v2 1  0  0  1
v3 0  1  0  0
v4 0  1  1  1连通性：该图连通该图存在欧拉回路该图中共有7条边
其中一条欧拉回路为：v1->v4->v2->v4->v4->v3->v2->v1

五、程序的时间复杂度和空间复杂度

时间复杂度：矩阵的输入、遍历操作的时间复杂度都为O(n^2)，检查矩阵是否连通和找出一条欧拉回路操作的时间复杂度约为O(n+m)。所以，程序总体的时间复杂度约为O(n^2)。

空间复杂度：一维数组Path的空间复杂度为O(n)，二维数组Matrix的的空间复杂度为O(n^2)；另外，程序中还涉及递归，两个递归操作所占的空间复杂度都为O(n)。所以，程序总体的空间复杂度约为O(n^2)。

六、心得体会

由人分析图像找欧拉回路在相对简单的图中并不困难，但图像一旦较为复杂，就会非常麻烦。所以，我觉得用程序实现欧拉回路算法是很有意义的。要依据离散数学的知识点来选择合适的算法。例如，在判断是否有欧拉回路时，就用到了书上无向图和有向图中欧拉回路存在的判别定理。

程序编写的过程中，我写了大量的注释，这为我之后的修改带来了不少便利。我把输入设置为点的数量和点之间的关联，最后输出邻接矩阵、边数、欧拉回路等，以最低限量的输入来获取最大量的输出。另外，在我的程序中，有多处代码是无向图和有向图共用的，将两者放在一起来写，寻找其一些共同点，虽然有些困难，但避免了程序的冗余，使程序尽可能的精简。

由于知识的匮乏，有许多可以优化的地方，我可能并没有考虑到。欢迎各位指正。