对于一张图G，若存在一条从S出发到T的路径，使得图中每条边都恰好只经过一次（点可以经过多次！），则该路径为S到T的欧拉路径。
若一条回路（从S出发最终回到S），使得图中每条边都恰好只经过一次，则该路径为图G的一条欧拉回路。
对于存在欧拉回路的无向图，称为欧拉图。
定理1：若无向图中存在欧拉路径，当且仅当无向图连通，且图中恰有两个点的度数为奇数（S和T），其他点的度数都是偶数。
定理2：若无向图中存在欧拉回路，当且仅当无向图连通，且图中每个点的度数都是偶数。
->若一个点的度数为偶数，说明只要到达该点，就必定可通过一条尚未走过的边离开该点。
Code：
一.邻接矩阵存图
int e[N][N];//两点间有多条边的情况 //bool e[N][N]; 两点间只有一条边的情况 bool vis[M<<1]; int ans[N<<2],top; //存储路径 P.S.数组开大些，因为每个点都可能经过多次 void dfs(int u){ for(int i=1;i<=n;i++){ //↑从小到大遍历，可以保证字典序最小！ if(e[u][i]){ e[u][i]--; e[i][u]--; //e[u][i]=e[i][u]=0; dfs(i); } } ans[++top]=u; } int deg[N];//记录每个点的度数，用来判断是否存在欧拉（回）路 int main(){ scanf.... for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); e[u][v]++; e[v][u]++; //e[u][v]=e[v][u]=1; } int cnt=0,root=inf; for(int i=1;i<=n;i++){ if(deg[i]%2){ cnt++; //root=min(root,i); 可以保证字典序最小 } } if(cnt&&cnt!=2) printf("有奇数度数的点的个数不为2 不存在欧拉路径"); if(!cnt) root=1;//所有点的度数都是偶数 存在欧拉回路 root=1保证字典序最小。 dfs(root); for(int i=top;i;i--){ printf("%d\n",ans[i]); } //欧拉（回）路是递归遍历的，因此路径是倒序存储的，所以输出时倒序输出。 }
二.邻接表存图（题目要求字典序最小时最好不要用邻接表存图，因为遍历的顺序不能保证字典序最小）
struct node{ int to,nxt; }e[M<<1]; int head[N],tot=1;//tot=1 成对变换 边i与边i^1互为反向边 void add(int u,int v){ e[++tot]=(node){v,head[u]}; head[u]=tot; } bool vis[M<<1]; int ans[N<<2],top; //存储路径 P.S.数组开大些，因为每个点都可能经过多次 void dfs(int u){ for(int i=head[u];i;i=e[i].nxt){ if(!vis[i]){ int v=e[i].to; vis[i]=vis[i^1]=1; head[u]=e[i].nxt; //遍历到边i时，前i-1条边都已遍历过，为避免重复操作，直接把head[u]变为next[i] dfs(v); } } ans[++top]=u; } int deg[N];//记录每个点的度数，用来判断是否存在欧拉（回）路 int main(){ scanf.... for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); add(u,v); deg[v]++; add(v,u); deg[u]++; } int cnt=0,root=inf; for(int i=1;i<=n;i++){ if(deg[i]%2){ cnt++; root=min(root,i) } } if(cnt&&cnt!=2) printf("有奇数度数的点的个数不为2 不存在欧拉路径"); if(!cnt) root=1;//所有点的度数都是偶数 存在欧拉回路 dfs(root); for(int i=top;i;i--){ printf("%d\n",ans[i]); } //欧拉（回）路是递归遍历的，因此路径是倒序存储的，所以输出时倒序输出。 }
原文：https://www.cnblogs.com/Loi-Brilliant/p/9124327.html