一笔画与哈密尔顿环
程序员文章站
2022-06-11 15:11:09
...
若一个图存在一笔画,则一笔画的路径叫做欧拉路
若最后还回到起点,则这个路径为欧拉回路
(奇点: 跟这个点相连的边数目为奇数的点)
定理1:存在欧拉路的条件:图是连通的,有且只有2个奇点。
定理2:存在欧拉回路的条件:图是连通的,0个奇点
用DFS判断即可
#include<cstdio>
#include<vector>
#include<iostream>
#define MAXN 1005
using namespace std;
int n, m, g[MAXN][MAXN], val[MAXN];
vector <int> circuit;
void dfs(int cur){
for(int i=1;i<=n;i++)
if(g[cur][i]) g[cur][i] = 0, g[i][cur] = 0, dfs(i);
circuit.push_back(cur);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u, v;
scanf("%d%d",&u,&v);
g[u][v] = 1; g[v][u] = 1;
val[u]++; val[v]++;
}
int start = 1;
for(int i=1;i<=n;i++)
if(val[i]%2){
start = i; break;
}
dfs(start);
for(int i=0;i<circuit.size();i++) printf("%d ",circuit[i]);
return 0;
}
哈密尔顿环是不重复走过所有的点,还能回到起点的回路。
用简单的DFS求出一张图所有的哈密尔顿环。
#include<cstdio>
#include<iostream>
#define MAXN 1005
using namespace std;
int n, m, x, lenth, g[MAXN][MAXN], num[MAXN], ans[MAXN];
bool val[MAXN], visit[MAXN];
void print(){
for(int i=1;i<lenth;i++) printf("%d ",ans[i]);
printf("%d\n",ans[lenth]);
}
void dfs(int last, int cur){
visit[cur] = true;
val[cur] = true;
ans[++lenth] = cur;
for(int i=1;i<=num[cur];i++){
if(g[cur][i] == x && g[cur][i]!=last){
ans[++lenth] = g[cur][i];
print();
lenth--;
break;
}
if(!visit[g[cur][i]]) dfs(cur,g[cur][i]);
}
lenth--;
visit[cur] = false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u, v;
scanf("%d%d",&u,&v);
g[u][num[u]++] = v; g[v][num[v]++] = u;
}
for(x=1;x<=n;x++)
if(!val[x]) lenth = 0, dfs(0,x);
return 0;
}