【算法】欧拉（回）路与哈密尔顿环

概念

“哈密尔顿回路问题”是访问除原出发结点以外的每个结点一次且仅一次，而“欧拉回路问题”是访问每条边一次且仅一次

欧拉回路与欧拉路

PS：已经判断此图有欧拉路或欧拉回路

#include<iostream> using namespace std; int g[101][101]; int du[101]; int lu[101]; int n,e,l,start,x,y; int maxn,minn=99999; int find(int i) { for(int j=1;j<=n;j++) { if(g[i][j]==1) { g[i][j]=0;//删除边 避免走第二次 g[j][i]=0;//如果有重边改为-- find(j); } } lu[++l]=i;//记录路径 } int main() { cin>>n>>e; for(int i=1;i<=e;i++) { cin>>x>>y; g[x][y]=1;//如果有重边改为＋＋ g[y][x]=1; du[x]++; du[y]++; maxn=max(maxn,max(x,y));//点编号的最大值 minn=min(minn,min(x,y));//点编号的最小值 } start=1; for(int i=1;i<=n;i++) if(du[i]%2==1)//判断如果有奇点从奇点开始 start=i; find(start); for(int i=l;i>=1;i--) cout<<lu[i]; }

哈密尔顿环

#include<iostream> #include<cstring> using namespace std; bool flag[101]; bool v[101]; int n,e,start,x,l; int a[101][101]; int lu[101]; int num[101]; void print() { for(int i=1;i<=l;i++) cout<<lu[i]<<" "; cout<<endl; } void dfs(int last,int i) { flag[i]=1;//标记走过 v[i]=1;//出现在图中 lu[++l]=i;//记录路径 for(int j=1;j<=num[i];j++) { if(a[i][j]==x&&a[i][j]!=last)//它可以回到头且不是第二个点就是一个环 { lu[++l]=a[i][j]; print(); l--; break; } if(flag[a[i][j]]==0) dfs(i,a[i][j]); } l--;//回溯部分 v[i]=0; } int main() { cin>>n>>e; for(int i=1;i<=e;i++) { int x,y; cin>>x>>y; a[x][++num[x]]=y;//每个点可以到达几个点 a[y][++num[y]]=x; } for(x=1;x<=n;x++) { if(v[x]==0)//如果没有出现在图中 { l=0; dfs(0,x); } } }

转载于:https://www.cnblogs.com/BrokenString/p/9279541.html