[算法学习笔记] 欧拉路

免责声明：本文定义并不严谨，笔者是从“浅显易懂”的角度出发写本文。若您需要严谨定义请移步至其他学术文章。

基本定义

欧拉路径，即 能不重不漏经过图上所有边的路径。也可以说 “一笔画问题”。特殊地，如果这条路径的起点和终点一致，则这条路径叫做“欧拉回路”。

其他的定义：

• 欧拉图：具有欧拉回路的图。
• 半欧拉图：具有欧拉通路但不具有欧拉回路的图。

一条路径是欧拉路（非欧拉回路），则它一定满足 只有一个点的出度比入度多1（该点路径起点），只有一个点的入度比出度多1（该点为路径终点）。 对于欧拉回路，所有点的入度 = 出度。

以上性质推导显然。根据以上性质，我们来求欧拉路径。

求解

判定欧拉路径

求解前，我们一般需要判定图中是否存在欧拉路径。这很简单，依据欧拉路径的定义即可。

对于有向图，存图的时候记录一下每个点的入度和出度。判定 是否只有一个点的出度比入度多1，只有一个点的入度比出度多1。（当然所有点的入度 = 出度也可）。

对于无向图，只有两个点的度为奇数，我们称之为 “奇点”。这两个点分别为起点，终点。

注意到在判定的同时，我们可以得到欧拉路径的起点（如果存在路径）。

求解欧拉路径

欧拉路径的求解这里主要介绍 Hierholzer 算法。 其他算法感兴趣的请移步 OI-Wiki。

Hierholzer 算法实质就是 DFS 遍历。遍历前我们需要找到起点。上文已经提到一部分，这里再说明一下。

对于欧拉路径（非回路），我们找到出度比入度多 1 的那个点。对于欧拉回路，任意一个点都可。

找到起点后，我们进行 DFS 遍历。DFS 遍历的时候，每遍历一条边就把它删去，防止重复遍历。

可以证明如果存在欧拉路径，那么无论如何顺序遍历都可以。即欧拉路径不唯一。所以这样 DFS 遍历是正确的。当然有的题目要求输出顺序最小的，这需要特殊处理。

最后输出顺序的时候倒序输出，原因显然。我们进行的是 DFS。这可以用栈实现。

提供 Hierholzer 算法模板，如下：

void dfs(int u)
{
    for(int i = vis[u];i < Edge[u].size();i = vis[u]) // 使用 vector 建图，这里采取了懒惰删除的方法。从vis_u 开始枚举，也就是从0-vis_u-1 的边都被删除了
    {
        vis[u] = i + 1;
        dfs(Edge[u][i]);
    }
    S.push(u);
}

（对于懒惰删除，可以参考 dijkstra 堆优化的处理）

例题

模板 欧拉路径

骑马修栅栏

实际上在求解欧拉路径的时候，邻接矩阵存图更常用，因为它在删边的时候更加方便。