判断一个图中是否存在欧拉回路(每条边恰好只走一次,并能回到出发点的路径),在以下三种情况中有三种不同的算法:
一、无向图
每个顶点的度数都是偶数,则存在欧拉回路。
二、有向图(所有边都是单向的)
每个节顶点的入度都等于出度,则存在欧拉回路。
以上两种情况都很好理解。其原理就是每个顶点都要能进去多少次就能出来多少次。
三、混合图(有的边是单向的,有的边是无向的。常被用于比喻城市里的交通网络,有的路是单行道,有的路是双行道。)
找到一个给每条无向的边定向的策略,使得每个顶点的入度等于出度,这样就能转换成上面第二种情况。这就可以转化成一个二部图最大匹配问题。网络模型如下:
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
struct stack
6![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{int top , node[210];} f; //顶点的堆栈
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
int a[201][201]; //图的邻接矩阵
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
int n;
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
void dfs(int x) //图的深度优先遍历
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
14
int i;
15![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
16
f.top ++; f.node[f.top] = x;
17![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
18
for (i = 1; i <= n; i ++)
19![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
20
if (a[i][x] > 0)
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
22
a[i][x] = 0; a[x][i] = 0; //删除此边
23![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
24
dfs(i);
25![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
26
break;
27
}
28
}
29![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
30
void Euler(int x) //欧拉路算法
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
32
int i , b;
33![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
34
f.top = 0; f.node[f.top] = x; //入栈
35![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
36
while (f.top >= 0)
37![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
38
b = 0;
39![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
40
for (i = 1; i <= n; i ++)
41
if (a[f.node[f.top]][i] > 0)
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{b = 1; break;}
43![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
44
if (b == 0) //如果没有点可以扩展,输出并出栈
45![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
46
printf("%d " , f.node[f.top]);
47![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
48
f.top --;
49
}
50![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{f.top --; dfs(f.node[f.top+1]);} //如果有,就DFS
51
}
52
}
53![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
54
int main()
55![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
56![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
57
int m , s , t , num , i , j , start;
58![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
59
//input
60![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
61
scanf("%d %d" , &n , &m); //n顶点数 m边数
62![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
63
memset(a , 0 , sizeof(a));
64![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
65
for (i = 0; i < m; i ++)
66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
67
scanf("%d %d" , &s , &t);
68
a[s][t] = 1; a[t][s] = 1;
69
}
70![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
71![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
72
//判断是否存在欧拉回路
73![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
74
s = 0; start = 1;
75![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
76
for (i = 1; i <= n; i ++)
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
78
num = 0;
79![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
80
for (j = 1; j <= n; j ++)
81
num += a[i][j];
82![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
83
if (num % 2 == 1)
84![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{start = i; s ++;}
85
}
86![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
87
if ((s == 0) || (s == 2))
88
Euler(start);
89
else printf("No Euler path\n");
90![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
91
getchar(); getchar();
92
return 0;
93
}
94![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)