admin 管理员组

文章数量: 888299

【算法】欧拉回路

欧拉路径

在一个图中，由i点出发，将每个边遍历一次最终到达j点的一条路径。
欧拉回路：i=j时的欧拉路径。

一些概念

图中的度：就是指和该顶点相关联的边数

在有向图中，度又分为入度和出度。
入度 (in-degree) ：以某顶点为弧头，终止于该顶点的弧的数目称为该顶点的入度。
出度 (out-degree) ：以某顶点为弧尾，起始于该顶点的弧的数目称为该顶点的出度。

在某顶点的入度和出度的和称为该顶点的度

无向图

存在欧拉回路的充要条件是所有的点的度数均为偶数
因为每个点的度数为偶数，所以可以将整个图看做由数个环嵌套而成，因为环一定能找到一条欧拉回路，所以整个图也能找到欧拉回路。

存在欧拉路径的充要条件是度数为奇数的点的数量为0个或者2个
给一欧拉回路，切断回路中的任一条边，被切断的边的两个顶点即可作为这条欧拉路径的终点起点。

有向图

存在欧拉回路的充要条件是所有的点的出度均等于入度
对于每一个点，每次进入这个节点，就一定有一条路可以出去，因此必定存在一条欧拉回路。

存在欧拉路径的充要条件是
①：欧拉回路的情况 ②：所有点中出度比入度大1的点有一个，入度比出度大1的点有一个，不允许有大几个的情况

此处讨论均是基于存在欧拉回路的情况（存在条件上面已给出）

算法 的朴素表达：

对于欧拉图，从一个节点出发，随便往下走（走过之后需要标记一下，下次就不要来了），必然也在这个节点终止（因为除了起始节点，其他节点的度数都是偶数，只要能进去就能出来）。这样就构成了一个圈，但因为是随便走的，所以可能会有些边还没走过就回来了。我们就从终止节点逆着往前查找，直到找到第一个分叉路口，然后从这个节点出发继续上面的步骤，肯定也是可以找到一条回到这个点的路径的，这时我们把两个圈连在一起。当你把所有的圈都找出来后，整个欧拉回路的寻找就完成了。

套圈法找欧拉回路

实现：
任取一个起点,开始下面的步骤
如果该点没有相连的点，就将该点加进路径中然后返回。
如果该点有相连的点，就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点，删除一个点）
处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中.

例题 欧拉回路

题目链接：
欧拉回路的模板题

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int M=2e5+10;
int head[M],nex[M*2],to[M*2],w[M*2];
int cnt=1,vis[M],in[M],out[M];
int n,m,t,xx;
stack<int>k;
void add(int x,int y,int c)
{nex[++cnt]=head[x];to[cnt]=y;w[cnt]=c;head[x]=cnt;
}
void dfs(int x)
{//这里要加上&，不然会超时（我也不知道为什么）for(int &i=head[x];i;i=nex[i]){int tt=to[i];int gg=i;if(!vis[i/2]){vis[i/2]=1;xx++;dfs(tt);k.push(w[gg]);}}
}
int main()
{cin>>t;cin>>n>>m;int u,v;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);add(u,v,i);if(t==1)add(v,u,-i);else cnt++;out[u]++,in[v]++;}bool flag=true;if(t==1){for(int i=1;i<=n;i++)if((in[i]+out[i])%2){flag=false;break;}}else {for(int i=1;i<=n;i++)if(in[i]!=out[i]){flag=false;break;}}if(flag){dfs(u);if(xx==m){cout<<"YES"<<endl;while(!k.empty()){cout<<k.top()<<" ";k.pop();}}else cout<<"NO\n"<<endl;}else cout<<"NO\n"<<endl;return 0;
}

本文标签： 算法欧拉回路

版权声明：本文标题：【算法】欧拉回路 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686635446h20014.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。