admin 管理员组

文章数量: 888299

欧拉回路（欧拉路径）

定义

给一个连通图，求一条每条边恰好走一次的路径，就叫欧拉路径，如果要求回到原点，就叫欧拉回路。（也叫一笔画问题）

推论

无向图

把度数为偶数的点叫偶点，度数为奇数的点叫奇点。

  • 如果一个图存在欧拉路径，则奇点的个数一定为0个或2个。
    白话证明：
    • 奇点个数为0个时，所有点都为偶点。
      则可以使得每个点的入边数量与出边数量相等，一定存在一个环。
      走完这个环后，每个点剩余的边一定是偶数，说明从这个点出发一定可以走出一个环再回到这个点，可以将这个新的环与原来的环拼接，形成新的路径，从而遍历所有边。
    • 如果奇点个数为2个，将这两个边连接，形成↑上面的样子，保证最后走新连的边，就可以完成欧拉路径。
  • 只有奇点为0个的图存在欧拉回路，证明同上。
  • 奇点有2个时，必然一个是起点，一个是终点。

有向图

  • 只有每个点的出度等于入度时才存在欧拉回路
    （回路必然有进有出，肯定要相等啊，，，）
  • 如果存在一个点的入度比出度大1，另一个点出度比入度大1，则存在欧拉路径。（证明通无向图）

求法

消圈法

如同前面无向图欧拉回路证明一样，找一个圈，中途把其它的圈并上来，并成一条路径，有递归版本和循环版本。
此算法只能计算确定有欧拉路径的图

代码

递归
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=505,MAXE=1100;
int E[MAXN][MAXN];
int ans[MAXE],cnt;
int deg[MAXN],n,m,S,T;
void euler(int id)
{for(int i=1;i<=n;i++)if(E[id][i]>0){E[id][i]--;E[i][id]--;euler(i);}ans[++cnt]=id;
}
int main()
{int a,b;scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);E[a][b]++;E[b][a]++;deg[a]++;deg[b]++;n=max(n,a);n=max(n,b);}S=0;T=0;for(int i=1;i<=n;i++)if(deg[i]&1){if(S){T=i;break;}S=i;}if(S)euler(S);elseeuler(1);for(int i=cnt;i>=1;i--)printf("%d\n",ans[i]);return 0;
}
循环
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=505,MAXE=1100;
int E[MAXN][MAXN];
int ans[MAXE],cnt;
int deg[MAXN],n,m;
int stack[MAXE],top;
void find_circle(int S)
{int x=S;bool flag=true;while(flag){stack[++top]=x;flag=false;for(int i=1;i<=n;i++)if(E[x][i]>0){E[x][i]--;E[i][x]--;x=i;flag=true;break;}}if(stack[top]==S)top--;
}
void euler(int S)
{find_circle(S);while(top){ans[++cnt]=stack[top];top--;find_circle(stack[top+1]);}
}
int main()
{int a,b,S,T;scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);E[a][b]++;E[b][a]++;deg[a]++;deg[b]++;n=max(n,a);n=max(n,b);}S=0;T=0;for(int i=1;i<=n;i++)if(deg[i]&1){if(S){T=i;break;}S=i;}if(S)euler(S);elseeuler(1);for(int i=cnt;i>=1;i--)printf("%d\n",ans[i]);if(!S)printf("1\n");return 0;
}

本文标签： 欧拉回路（欧拉路径）

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