当前位置: 代码迷 >> 综合 >> 欧拉图详解 (递归和非递归)(重新更改)
  详细解决方案

欧拉图详解 (递归和非递归)(重新更改)

热度:74   发布时间:2024-01-15 07:12:26.0

定义:

欧拉回路:每条边只经过一次,而且回到起点

欧拉图:具有欧拉回路的图

欧拉路径:每条边只经过一次,不要求回到起点

半欧拉图:具有欧拉通路而无欧拉回路的图

判定:

欧拉回路的判定

无向图:连通(不考虑度为 0 的点),每个顶点度数都为偶数。

有向图:基图连通(把边当成无向边,同样不考虑度为 0 的点),每个顶点出度等于入度。

混合图(有无向边和有向边):首先是基图连通(不考虑度为 0 的点),然后需要借助网络流(后续再补)

欧拉路径的判断:

无向图:连通(不考虑度为 0 的点),只有两个奇度顶点(它们分别是欧拉通路的两个端点)。

有向图:基图连通(把边当成无向边,同样不考虑度为 0 的点),每个顶点出度等于入度或 者有且仅有一个点的出度比入度多 1,有且仅有一个点的出度比入度少 1,其余出度等于入 度。

混合图:如果存在欧拉回路,一点存在欧拉路径了。否则如果有且仅有两个点的(出度 -入 度)是奇数,那么给这个两个点加边,判断是否存在欧拉回路。

欧拉图一般有两种求法模板:

Fleury(佛罗莱)算法(这里没有,没有题用到(做到的)),并查集和递归(打印路径)

并查集一般用来确定图是否连通,然后根据度来判断是否存在欧拉图,递归用来输出路路径,

但递归打印路径时候需要注意:必须先确定里面有欧拉路径,欧拉回路直接打印即可,欧拉通路需要找到起点

 

判断无向图是否为欧拉图并输出路径

欧拉回路:连通(不考虑度为 0 的点),每个顶点度数都为偶数。

欧拉通路:连通,只有两个奇度顶点(它们分别是欧拉通路的两个端点)

1:图连通:用并查集判断

#include <cstdio>
#include <cstring>
#define N 1000using namespace std;int n, m;
int f[N],degree[N];//记录第i点的度数void init()
{for (int i = 1; i <= n; i++)f[i] = i;
}
int find(int x)
{return x == f[x] ? x : f[x] = find(f[x]);
}
void merge(int x, int y)
{int t1, t2;t1 = find(x); t2 = find(y);if (t1 != t2)	f[t2] = t1;else return;
}
int isEuler()
{int cnt=0;for (int i = 1; i <= n; i++){if (degree[i] & 1)	cnt++;if(cnt>2) return 0;}if(cnt==2||cnt==0) return 1;///cnt==2 欧拉通路 cnt==0欧拉回路return 0;
}
int isconnect()
{int cnt = 0;int ff=find_(1);for (int i=2; i <= n; i++){if (find_(i)!=ff)return 0;}return 1;
}
int main()
{while (scanf("%d", &n) != EOF && n){init();memset(degree, 0, sizeof(degree));scanf("%d", &m);int t1, t2;for (int i = 0; i < m; i++){scanf("%d%d", &t1, &t2);//输入有t1,t2相等的情况if (t1 == t2)continue;degree[t1]++; degree[t2]++;merge(t1, t2);}printf("%d\n", isEuler() && isconnect());}return 0;
}

输出路径

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<set>
#include<vector>
#include<sstream>
#include<queue>
#define ll long long
#define PI 3.1415926535897932384626
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=6000;
struct Edge
{int to,next,id;bool flag;
}edge[maxn];
int head[maxn];
int in[maxn];
int tot;void addedge(int u,int v,int w)
{edge[tot].to=v;edge[tot].next=head[u];edge[tot].id=w;edge[tot].flag=false;head[u]=tot++;
}
int start;
vector<int>ans;
void init()
{tot=0;memset(head,-1,sizeof(head));memset(in,0,sizeof(in));
}
void dfs(int x)
{for(int i=head[x];i!=-1;i=edge[i].next){if(!edge[i].flag){edge[i].flag=true;edge[i^1].flag=true;dfs(edge[i].to);ans.push_back(i);//记录边的号码}}
}
int main()
{int x,y,c;while(scanf("%d%d",&x,&y)){if(x==0&&y==0)break;init();scanf("%d",&c);addedge(x,y,c);addedge(y,x,c);in[x]++;in[y]++;start=min(x,y);while(scanf("%d%d",&x,&y)){if(x==0&&y==0)break;scanf("%d",&c);addedge(x,y,c);addedge(y,x,c);in[x]++;in[y]++;}int flag=1;for(int i=1;i<=maxn;i++)   //判断是否为欧拉回路{if(in[i]%2!=0){flag=0;break;}}if(flag==0){puts("Round trip does not exist.");continue;}ans.clear();dfs(start);for(int i=0;i<ans.size();i++){if(i==0)printf("%d",edge[ans[i]].id);elseprintf(" %d",edge[ans[i]].id);}cout<<endl;}return 0;
}

 

有向图判断并打印欧拉路径或回路

///有向图实现欧拉回路或通路的判断并输出字典序最小的路径
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<set>
#include<vector>
#include<sstream>
#include<queue>
#define ll long long
#define PI 3.1415926535897932384626
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2000;
struct Edge
{int to,next,id;bool flag;
}edge[maxn];
int head[maxn];
int tot;void addedge(int u,int v,int w)
{edge[tot].to=v;edge[tot].id=w;edge[tot].next=head[u];edge[tot].flag=false;head[u]=tot++;
}
int start,n;
int f[30],in[30],out[30];
vector<int>ans;
void init()
{tot=0;ans.clear();for (int i = 1; i <= 26; i++)f[i] = i;memset(head,-1,sizeof(head));memset(in,0,sizeof(in));memset(out,0,sizeof(out));
}
int find(int x)
{return x == f[x] ? x : f[x] = find(f[x]);
}
void merge(int x, int y)
{int t1, t2;t1 = find(x); t2 = find(y);if (t1 != t2)	f[t2] = t1;else return;
}
///判断是否存在欧拉通路径
///>=0:欧拉通路的起始位置
///-2:欧拉回路
///-1:无欧拉路劲
int isEluer()     //判断是否存在欧拉通路径
{int sum=0;for(int i=0;i<26;i++)      //保证是一个连通图{if((in[i]||out[i])&&find(i)==i)///in[i]||out[i]例题有的字母中这个没有用到sum++;if(sum>=2)return -1;}int ac=0,bc=0,pos=-1;for(int i=0;i<26;i++){if(in[i]==out[i]) continue;if(in[i]==out[i]+1){ac++;continue;}if(in[i]==out[i]-1){pos=i;bc++;continue;}return -1;}if(!ac&&!bc) return -2;if(ac==1&&bc==1) return pos;return -1;
}
void dfs(int x)
{for(int i=head[x];i!=-1;i=edge[i].next){if(!edge[i].flag){edge[i].flag=true;dfs(edge[i].to);ans.push_back(i);//记录边的号码}}
}
string word[maxn];
void print()
{for(int i=ans.size()-1;i>0;i--)cout <<word[ans[i]]<< '.';cout <<word[ans[0]] << endl;
}
bool cmp(const string a, const string b)
{if(a[0]==b[0])return a>b;return a<b;
}int main()
{int t;cin>>t;while(t--){init();scanf("%d",&n);for(int i=0;i<n;i++){cin>>word[i];}sort(word,word+n,cmp);for(int i=0;i<n;i++){int x,y;x=word[i][0]-'a';y=word[i][word[i].size()-1]-'a';addedge(x,y,i);merge(x,y);in[y]++;out[x]++;}int flag=isEluer();if(flag==-1)printf("***\n");else if(flag==-2){dfs(word[0][0]-'a');	print();}else{dfs(flag);print();}}return 0;
}

 

注解:算法进阶指南 上说求欧拉回来极其容易爆栈,建议使用非递归模板,题目待验证模板准确性(验证之后会更新),

非递归:

// 求出无向欧拉图中的一条欧拉回路
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int head[N], ver[N], Next[N], tot; // 邻接表
int stack[N], ans[N]; // 模拟系统栈,答案栈
bool vis[N];
int n, m, top, t;void add(int x, int y) {ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}void euler() {stack[++top] = 1;while (top > 0) {int x = stack[top], i = head[x];// 找到一条尚未访问的边while (i && vis[i]) i = Next[i];// 沿着这条边模拟递归过程,标记该边,并更新表头if (i) {stack[++top] = ver[i];head[x] = Next[i];vis[i] = vis[i ^ 1] = true;}		// 与x相连的所有边均已访问,模拟回溯过程,并记录于答案栈中else {top--;ans[++t] = x;}}
}int main() {cin >> n >> m;tot = 1;for (int i = 1; i <= m; i++) {int x, y;scanf("%d%d", &x, &y);add(x, y);add(y, x);}euler();for (int i = t; i; i--) printf("%d\n", ans[i]);
}

 

经典例题:

HDU 3018 Ant Trip           (并查集:欧拉回路的问题)

HDU 1878 欧拉回路        (并查集:简单欧拉回路判定)

POJ 1041John's trip    ( 无向图欧拉回路-路径输出)

POJ 1041John's trip   (无向图欧拉回路-路径输出)

POJ 1386 Play on Words (判定有向图图欧拉路径是否存在)

POJ 1300 Door Man      (无向图欧拉通路和回路的判定+并查集)

  相关解决方案