欧拉回路 & 欧拉路径

欧拉路径 & 欧拉回路

概念

欧拉路径: 如果图 G 种的一条路径包括所有的边,且仅通过一次的路径.

欧拉回路: 能回到起点的欧拉路径.

混合图: 既有无向边又有无向边的图.

判定

无向图

一个无向图存在欧拉路径,当且仅当该图所有点度数为偶数或者仅有两个点度数为奇数,其余全为偶数.
有向图

所有的点出度等于入度,或者对于欧拉路径还可以是有一个点出度比入度多\(1\),另有一个点入度比出度多\(1\).

寻找欧拉路径/回路的方法 Hierholzer 算法

Hierholzer算法自动寻找欧拉回路，在找不到欧拉回路的情况下会找到欧拉路径。前提是得给它指定好起点。

算法流程（无向图）：

1.判断奇点数。奇点数若为0则任意指定起点，奇点数若为2则指定起点为奇点。

2.开始递归函数Hierholzer(x):

　　循环寻找与x相连的边(x,u):

　　　　删除(x,u)

　　　　删除(u,x)

　　　　Hierholzer(u);

　　将x插入答案队列之中

3.倒序输出答案队列

板子题

[USACO Section 3.3] 骑马修栅栏 Riding the Fences

Code

#include<bits/stdc++.h>

using namespace std;

int g[1501][1501];

int du[1501],sta[1501];

int n,e,top,i,j,x,y,st=1,m,mi,p;

void dfs(int i)

{

    for(int j=1;j<=m;++j)

        if(g[i][j])

        {

            g[i][j]--;

            g[j][i]--;

            dfs(j);

        }

    sta[++top]=i;

}

int main()

{

    scanf("%d",&e);

    for(i=1;i<=e;++i)

    {

        scanf("%d%d",&x,&y);

        ++g[y][x]; ++g[x][y];

        du[x]++; du[y]++;

       	m=max(max(x,y),m);

	}

    for(i=1;i<=m;++i)

        if(du[i]%2)

        {st=i;break;}

    dfs(st);

    for(i=top;i>=1;--i)

        printf("%d\n",sta[i]);

    return 0;

}

巴特西

欧拉回路 & 欧拉路径

欧拉路径 & 欧拉回路

概念

判定

寻找欧拉路径/回路的方法 Hierholzer 算法

最新文章

热门文章