判断一个图中是否存在欧拉回路（每条边恰好只走一次，并能回到出发点的路径），在以下三种情况中有三种不同的算法：
一、无向图
每个顶点的度数都是偶数，则存在欧拉回路。
二、有向图（所有边都是单向的）
每个节顶点的入度都等于出度，则存在欧拉回路。
以上两种情况都很好理解。其原理就是每个顶点都要能进去多少次就能出来多少次。
三、混合图（有的边是单向的，有的边是无向的。常被用于比喻城市里的交通网络，有的路是单行道，有的路是双行道。）
找到一个给每条无向的边定向的策略，使得每个顶点的入度等于出度，这样就能转换成上面第二种情况。这就可以转化成一个二部图最大匹配问题。网络模型如下：
1. 新建一个图。
2. 对于原图中每一条无向边i，在新图中建一个顶点e（i）；
3. 对于原图中每一个顶点j，在新图中建一个顶点v（j）。
4. 如果在原图中，顶点j和k之间有一条无向边i，那么在新图中从e（i）出发，添加两条边，分别连向v（j）和v（k），容量都是1。
5. 在新图中，从源点向所有e（i）都连一条容量为1的边。
6. 对于原图中每一个顶点j，它原本都有一个入度in、出度out和无向度un。显然我们的目的是要把所有无向度都变成入度或出度，从而使它的入度等于总度数的一半，也就是(in + out + un) / 2（显然与此同时出度也是总度数的一半，如果总度数是偶数的话）。当然，如果in已经大于总度数的一半，或者总度数是奇数，那么欧拉回路肯定不存大。如果in小于总度数的一半，并且总度数是偶数，那么我们在新图中从v（j）到汇点连一条边，容量就是(in + out + un) / 2 – in，也就是原图中顶点j还需要多少入度。
按照这个网络模型算出一个最大流，如果每条从v（j）到汇点的边都达到满流量的话，那么欧拉回路成立。
这个算法可以用在ZJU#1992（http://acm.zju.edu.cn/show_problem.php?pid=1992）
弗罗莱(Fleury)算法求欧拉回路
算法轮廓：
（1）任取v0∈V(G)，令P0=v0.
（2）设Pi=v0e1v1e2…eivi已经行遍，按下面方法来从E(G)-{e1,e2,…,ei}中选取ei+1：
（a）ei+1与vi相关联；
（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,…,ei}中的桥。
（3）当（2）不能再进行时，算法停止。
可以证明，当算法停止时所得简单回路Pm=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路。
程序文件夹：33333
//输入一个无向图，先判断是否存在欧拉路，若有求出一条欧拉路
/先输入顶点数和边数，之后输入每条边连接的2个点
//例如
//5 6 (5个点，6条边)
//1 2
//1 3
//2 3
//2 5
//2 4
//4 5
1
#include <stdio.h>
2#include <string.h>
3
4
5struct stack
6
{int top , node[210];} f; //顶点的堆栈
7
8int a[201][201]; //图的邻接矩阵
9
10int n;
11
12void dfs(int x) //图的深度优先遍历
13{
14
int i;
15
16f.top ++; f.node[f.top] = x;
17
18for (i = 1; i <= n; i ++)
19
20 if (a[i][x] > 0)
21
{
22 a[i][x] = 0; a[x][i] = 0; //删除此边
23
24 dfs(i);
25
26 break;
27
}
28
}
29
30void Euler(int x) //欧拉路算法
31{
32int i , b;
33
34f.top = 0; f.node[f.top] = x; //入栈
35
36while (f.top >= 0)
37{
38 b = 0;
39
40 for (i = 1; i <= n; i ++)
41 if (a[f.node[f.top]][i] > 0)
42 {b = 1; break;}
43
44 if (b == 0) //如果没有点可以扩展，输出并出栈
45 {
46 printf("%d " , f.node[f.top]);
47
48 f.top --;
49 }
50 else {f.top --; dfs(f.node[f.top+1]);} //如果有，就DFS
51 }
52}
53
54int main()
55{
56
57int m , s , t , num , i , j , start;
58
59 //input
60
61 scanf("%d %d" , &n , &m); //n顶点数 m边数
62
63 memset(a , 0 , sizeof(a));
64
65 for (i = 0; i < m; i ++)
66 {
67 scanf("%d %d" , &s , &t);
68 a[s][t] = 1; a[t][s] = 1;
69 }
70
71
72 //判断是否存在欧拉回路
73
74 s = 0; start = 1;
75
76 for (i = 1; i <= n; i ++)
77 {
78 num = 0;
79
80 for (j = 1; j <= n; j ++)
81 num += a[i][j];
82
83 if (num % 2 == 1)
84{start = i; s ++;}
85 }
86
87 if ((s == 0) || (s == 2))
88Euler(start);
89 else printf("No Euler path\n");
90
91 getchar(); getchar();
92 return 0;
93}
94