判斷一個(gè)圖中是否存在歐拉回路（每條邊恰好只走一次，并能回到出發(fā)點(diǎn)的路徑），在以下三種情況中有三種不同的算法：
一、無(wú)向圖
每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)，則存在歐拉回路。
二、有向圖（所有邊都是單向的）
每個(gè)節(jié)頂點(diǎn)的入度都等于出度，則存在歐拉回路。
以上兩種情況都很好理解。其原理就是每個(gè)頂點(diǎn)都要能進(jìn)去多少次就能出來(lái)多少次。
三、混合圖（有的邊是單向的，有的邊是無(wú)向的。常被用于比喻城市里的交通網(wǎng)絡(luò)，有的路是單行道，有的路是雙行道。）
找到一個(gè)給每條無(wú)向的邊定向的策略，使得每個(gè)頂點(diǎn)的入度等于出度，這樣就能轉(zhuǎn)換成上面第二種情況。這就可以轉(zhuǎn)化成一個(gè)二部圖最大匹配問(wèn)題。網(wǎng)絡(luò)模型如下：
1. 新建一個(gè)圖。
2. 對(duì)于原圖中每一條無(wú)向邊i，在新圖中建一個(gè)頂點(diǎn)e（i）；
3. 對(duì)于原圖中每一個(gè)頂點(diǎn)j，在新圖中建一個(gè)頂點(diǎn)v（j）。
4. 如果在原圖中，頂點(diǎn)j和k之間有一條無(wú)向邊i，那么在新圖中從e（i）出發(fā)，添加兩條邊，分別連向v（j）和v（k），容量都是1。
5. 在新圖中，從源點(diǎn)向所有e（i）都連一條容量為1的邊。
6. 對(duì)于原圖中每一個(gè)頂點(diǎn)j，它原本都有一個(gè)入度in、出度out和無(wú)向度un。顯然我們的目的是要把所有無(wú)向度都變成入度或出度，從而使它的入度等于總度數(shù)的一半，也就是(in + out + un) / 2（顯然與此同時(shí)出度也是總度數(shù)的一半，如果總度數(shù)是偶數(shù)的話(huà)）。當(dāng)然，如果in已經(jīng)大于總度數(shù)的一半，或者總度數(shù)是奇數(shù)，那么歐拉回路肯定不存大。如果in小于總度數(shù)的一半，并且總度數(shù)是偶數(shù)，那么我們?cè)谛聢D中從v（j）到匯點(diǎn)連一條邊，容量就是(in + out + un) / 2 – in，也就是原圖中頂點(diǎn)j還需要多少入度。
按照這個(gè)網(wǎng)絡(luò)模型算出一個(gè)最大流，如果每條從v（j）到匯點(diǎn)的邊都達(dá)到滿(mǎn)流量的話(huà)，那么歐拉回路成立。
這個(gè)算法可以用在ZJU#1992（http://acm.zju.edu.cn/show_problem.php?pid=1992）
弗羅萊(Fleury)算法求歐拉回路
算法輪廓：
（1）任取v0∈V(G)，令P0=v0.
（2）設(shè)Pi=v0e1v1e2…eivi已經(jīng)行遍，按下面方法來(lái)從E(G)-{e1,e2,…,ei}中選取ei+1：
（a）ei+1與vi相關(guān)聯(lián)；
（b）除非無(wú)別的邊可供行遍，否則ei+1不應(yīng)該為Gi=G-{e1,e2,…,ei}中的橋。
（3）當(dāng)（2）不能再進(jìn)行時(shí)，算法停止。
可以證明，當(dāng)算法停止時(shí)所得簡(jiǎn)單回路Pm=v0e1v1e2…emvm(vm=v0)為G中一條歐拉回路。
程序文件夾：33333
//輸入一個(gè)無(wú)向圖，先判斷是否存在歐拉路，若有求出一條歐拉路
/先輸入頂點(diǎn)數(shù)和邊數(shù)，之后輸入每條邊連接的2個(gè)點(diǎn)
//例如
//5 6 (5個(gè)點(diǎn)，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; //頂點(diǎn)的堆棧
7
8int a[201][201]; //圖的鄰接矩陣
9
10int n;
11
12void dfs(int x) //圖的深度優(yōu)先遍歷
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) //如果沒(méi)有點(diǎn)可以擴(kuò)展，輸出并出棧
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頂點(diǎn)數(shù) m邊數(shù)
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