欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一笔画与哈密尔顿环

程序员文章站 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;
}
相关标签: dfs