欧拉通路 回路

自用笔记算法

欧拉回路

知识点详解

欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路
欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路
有向图的基图：忽略有向图所有边的方向，得到的无向图称为该有向图的基图。

无向图
（1）设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；
（2）如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路是欧拉回路
（2）具有欧拉回路的无向图G成为欧拉图
有向图
（1）设D是有向图，D的基图连通，则称经过D的每条边一次并且仅有一次的有向路径为有向欧拉通路
（2）如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路
（3）具有有向欧拉回路的图D称为有向欧拉图

定理&推论

无向图
定理
　　无向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。
推论
（1） 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点；
（2）当G是无奇度结点的连通图时，G必有欧拉回路
（3）G为欧拉图（存在欧拉回路）的充分必要条件是 G为无奇度结点的连通图

有向图
定理
有向图D存在欧拉通路的充要条件是：D为有向图，D的基图连通，并且所有顶点的出度与入度相等；或者 除两个顶点外，其余顶点的出度与入度都相等
，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1.
推论
（1）当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度相等时，D的有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点。
（2）当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。
（3）有向图D为有向欧拉图的充要条件是 D的基图为连通图，并且所有顶点的出、入度都相等。

欧拉回路求解

（1）DFS
DFS搜索 思想求解欧拉回路的思路为：利用欧拉定理判断出一个图存在欧拉通路或欧拉回路后，选择一个正确的起始顶点，用DFS算法遍历所有的边
（每条边只遍历一次），遇到走不通就回退。在搜索前进方向上将遍历过的边按顺序记录下来。这组边的排列就组成了一条欧拉通路或回路。
（2）Fleury（佛罗莱算法）
设G为一个无向欧拉图，求G中一条欧拉回路的算法如下：
1 ）
任取G中一顶点v0，令P0=v0；
2）
假设沿Pi=v0e1v1e2v2……eivi走到顶点vi，按下面方法从E(G)-{e1,e2,…,ei}中选ei+1。
ei+1与vi相关联
除非无别的边可供选择，否则ei+1不应该是Gi=G-{e1,e2,…,ei}中的桥。
3）
当2）不能再进行时算法停止。
可以证明的是，当算法停止时，所得到的简单回路Pm=v0e1v1e2v2……emvm，（vm=v0）为G中一条欧拉回路。

欧拉回路判定例题

题目要求

判定一个图是否是欧拉回路
在联通图的基础上判断每个点的度即可

参考代码(HDU 1878)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m;    //n:点  m:边
vector<int>e[1050];
int count;
int vis[1050],num;
void dfs(int x)
{
	vis[x]=1;
	num++;
	for(int i=0;i<e[x].size();i++)
		if(!vis[e[x][i]])
			dfs(e[x][i]);
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(cin>>n>>m)
	{
		if(n==0)
			break;
		for(int i=1;i<=n;i++)
			e[i].clear();
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		memset(vis,0,sizeof(vis));
		num=0,count=0;
		dfs(1);
		for(int i=1;i<=n;i++)
			if(e[i].size()&1)
				count++;
		if(num==n)
		{
			if(count==0)
				cout<<"1"<<endl;
			else
				cout<<"0"<<endl;
		}
		else
			cout<<"0"<<endl;
	}
	return 0;
}

思路

无向图：
欧拉回路需满足两个条件：连通性+无奇度结点
若题目改为欧拉通路 则需要满足：连通性+无奇度结点或有两个奇度结点

欧拉回路的顺序求解

题目要求

求出任一个欧拉回路的顺序
使用Fleury模版

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int n,m;         //n:点  m:边
int e[5050][5050];
int degree[5050],count;
stack<int>s;
void dfs(int x)
{
	s.push(x);
	for(int i=1;i<=n;i++)
	{
		if(e[x][i]==1)
		{
			e[x][i]=e[i][x]=0;
			dfs(i);
			break;
		}
	}
}
void Fleury(int x)
{
	s.push(x);
	while(!s.empty())
	{
		int flag=0;
		for(int i=1;i<=n;i++)
		{
			if(e[x][i]==1)
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			cout<<s.top();
			s.pop();
		}
		else
		{
			int y=s.top();
			s.pop();
			dfs(y);
		}
	}
	cout<<endl;
}
int main()
{
	while(cin>>n>>m)
	{
		int flag=1;
		memset(e,0,sizeof(e));
		memset(degree,0,sizeof(degree));
		while(!s.empty())
			s.pop();
		count=0;
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			e[u][v]=e[v][u]=1;
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				if(e[i][j]==1)
					degree[j]++;
			}
		for(int i=1;i<=n;i++)
			if(degree[i]&1)
			{
				count++;
				flag=i;
			}
		if(count==0||count==2)
			Fleury(flag);
		else
			cout<<"No Euler Path"<<endl;
	}
	return 0;
}

有向欧拉回路的裸搜（POJ 2230）

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstring>
#include<vector>
#define maxn 50000+50
using namespace std;
int n,m;
struct node
{
	int v,vis;
	node(int v,int vis):v(v),vis(vis){}
};
vector<node>e[maxn];
void dfs(int x)
{
	for(int i=0;i<e[x].size();i++)
		if(!e[x][i].vis)
		{
			e[x][i].vis=1;
			dfs(e[x][i].v);
		}
	cout<<x<<endl;
}
int main()
{
	//freopen("input.txt","r",stdin);
	while(cin>>n>>m)
	{
		for(int i=1;i<=n;i++)
			e[i].clear();
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			e[u].push_back(node(v,0));
			e[v].push_back(node(u,0));
		}
		dfs(1);
	}
	return 0;
}

简单欧拉路判定(POJ 1300)

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int door[105];
string s1;
char s2[1050],s3[1050];
int m,n;
int main()
{
	freopen("input.txt","r",stdin);
	while(cin>>s1)
	{
		if(s1=="ENDOFINPUT")
			break;
		cin>>m>>n;
		getchar();
		int cnt=0;
		memset(door,0,sizeof(door));
		for(int i=0;i<n;i++)
		{
			gets(s2);
			int len=strlen(s2);
			for(int j=0;j<len;j++)
			{
				if(s2[j]!=' ')
				{
					int d=s2[j]-'0';
					cnt++;
					door[i]++;
					door[d]++;
				}
			}
		}
		gets(s3);
		int count=0;
		for(int i=0;i<n;i++)
			if(door[i]&1)
				count++;
		if(count==0&&m==0)
			cout<<"YES "<<cnt<<endl;
		else if(count==2&&m!=0)
			cout<<"YES "<<cnt<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}

思路

若是欧拉回路 无奇度点
若是欧拉通路非回路 有两个奇度点
本题的cnt需要每加一条边时+1

本文标题:欧拉通路 回路

文章作者:Hippopmonkey

发布时间:2017-02-01, 22:34:42

最后更新:2017-02-02, 14:13:56

原始链接:http://xuboming8.github.io/2017/02/01/欧拉通路-回路/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 欧拉回路
    1. 1.1. 知识点详解
    2. 1.2. 定理&推论
    3. 1.3. 欧拉回路求解
    4. 1.4. 欧拉回路判定例题
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考代码(HDU 1878)
      3. 1.4.3. 思路
    5. 1.5. 欧拉回路的顺序求解
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考代码
    6. 1.6. 有向欧拉回路的裸搜（POJ 2230）
      1. 1.6.1. 参考代码
    7. 1.7. 简单欧拉路判定(POJ 1300)
      1. 1.7.1. 参考代码
      2. 1.7.2. 思路
|