欧拉回路

概念

1.经过图中所有边恰好一次的通路称为欧拉通路或欧拉路(起点终点可以不一致)
2.经过图中所有边恰好一次的回路称为欧拉回路(起点终点一致)
3.判别方法:对于无向图G,G中存在欧拉回路当且仅当G中所有度非0的点是连通的且没有奇数度数的点
对于无向图G,G中存在欧拉路当且仅当G中所有度非0的点是连通的且G中恰好有0个或2个奇数度数的点(0个表示存在欧拉回路)
对于有向图G,G中存在欧拉回路当且仅当G中所有度非0的点是强联通的且每个点的入度等于出度
对于有向图G,G中存在欧拉路当且仅当:
1)将G中所有有向边改为无向边后,G中所有度非0的点是连通的
2)最多只有一个点出度减入度为1;
3)最多只有一个点入度减出度为1;
4)其他所有点的入度等于出度

求欧拉图流程

首先从C开始:
C->D->E->F:走到头了,那么把F加入到路径中
回溯:C->D->E->B->A->D->G->H->E,走到头了
E加入到路径中,回溯H加入路径,G,D,A,B,E,D,C依次回溯加入到路径去
最终路径中存的是:
F <- E <- H <- G <- D <- A <- B <- E <- D <- C
倒序输出即为所求的欧拉通路
代码实现,有向图版本:

vector<int> edges[N+1];
int n,m,l,f[N+1],ind[N+1],outd[N+1],c[M+2];

void dfs(int x){
	int len=edge[x].size();
	//因为从头到尾一个点可能被枚举到很多次,所以可以记录这个点枚举到了哪里
	for(;f[x]<len;){ 
		int y=edge[x][f[x]]; 
		f[x]++;
		dfs(y);
		c[++l]=y;//记录路径信息(在c中倒序依次输出,即为欧拉路)
		/*
		比如c={1,2,3,4,1};
		那么 1->4->3->2->1即为要求的欧拉路径 
		*/ 
	}
}

void Euler(){
	int x=0,y=0,z=0;//x是起点,y是有多少个点的出度比入度大1,z表示有多少个点出度不等于入度 
	for(int i=1;i<=n;i++){
		if(ind[i]+1==outd[i]){
			x=i,++y;
		}
		if(ind[i]!=outd[i]){
			++z;
		}
	}
	//!z所有点的出度都能与入度或有一个点的出度比入度大1并且有两个点的出度不等于入度,这样就有欧拉路 
	if(!((y==1&&z==2)||!z)){
		cout<<"NO"<<endl;
		return ;
	} 
	//如果起点还没找到,随便找一个度非0的点就行了 
	if(!x){
		for(int i=1;i<=n;i++)
		if(ind[i]) x=i;
	}
	memset(f,0,sizeof f);
	l=0;
	dfs(x);
	c[++l]=x;//x为最终的起点,所以要加到路径里面去
	cout<<"YES"<<endl;
	for(int i=l;i;--i) cout<<c[i]<<" "; 
}