欧拉路径、欧拉回路、欧拉图傻傻分不清楚？看这一篇就够了！

upd 2024.10.24 ：补充了为什么求欧拉路径时不能正序存点。

欧拉路径、回路、图

前言

当一手标题党，快乐~

之前一直分不清楚，写篇笔记分辨一下。

欧拉路径

可以一笔画的路径，称为欧拉路径。不要求起点终点为同一点。

判定：

有向图：图中只有一个出度比入度大 \(1\) 的点（起点），与一个入度比出度大 \(1\) 的点（终点），其余点出入度相等。

无向图：图中只有两个奇点（起点和终点），其余点都是偶点。

当然，将有向边视作无向边后，路径必须连通。

欧拉回路

在欧拉路径的基础上，起点终点是同一点。

判定：

有向图：所有点的出入度相等。

无向图：所有点都是偶点。

欧拉图

欧拉图：具有欧拉回路的图。

半欧拉图：存在欧拉路径、但没有欧拉回路的图。

判断方法

判断一个图是否有欧拉路或欧拉回路，要用到 Fleury 算法。（虽然这不是文章的重点，重点是上文）

用 DFS 实现。

算法核心：除非都是桥，否则走桥边。

关于为什么不能倒序存点

先放张图：

正确顺序：\(1\to 3\to 4\to 1\to 2\)

如果先进栈会出现断层。

P7771 【模板】欧拉路径

code

#include

using namespace std;

#define int long long

const int MAXN=1e5+5;

int n,m;

int tmp[MAXN];

int rd[MAXN],cd[MAXN];

stack st;

vector G[MAXN];

void dfs(int S)

{

for(int i=tmp[S];i

tmp[S]=i+1,dfs(G[S][i]);

// tmp[S] : G[S][1,2,...,tmp[S]-1] 都已访问，下一次从 G[S][tmp[S]] 开始

st.push(S);

}

signed main()

{

scanf("%lld%lld",&n,&m);

for(int i=1,u,v;i<=m;i++)

{

scanf("%lld%lld",&u,&v);

G[u].push_back(v); // 注意有向图

cd[u]++,rd[v]++;

}

for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());

int S=1,c1=0,c2=0;

bool flg=1; // 是否所有点出入度相等

for(int i=1;i<=n;i++)

{

if(cd[i]!=rd[i])

{

flg=0;

if(cd[i]-rd[i]==1) c1++,S=i; // 出度比入度大 1

else if(rd[i]-cd[i]==1) c2++;

else return puts("No"),0;

}

}

if(flg==0&&!(c1==c2&&c1==1))

return puts("No"),0; // 不满足判定条件

dfs(S);

while(!st.empty())

printf("%lld ",st.top()),st.pop();

return 0;

}