OI-wiki 图论专题：欧拉图、欧拉回路与 Hierholzer 算法全解析
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
欧拉图是图论中"一笔画"问题的严格数学形式：是否存在一条恰好经过每条边一次、且能回到起点的路线。本篇以 OI-wiki 的 docs/graph/euler.md 为骨架，系统讲解欧拉路径与欧拉回路的定义、判定性质及其数学证明，并深入剖析最常用的 Hierholzer 算法——从伪代码、时间复杂度到可运行的 C++ 实现（euler_1.cpp）与配套测试样例（euler_1.in / euler_1.ans）。读完本篇，你将掌握欧拉图的等价判定条件，能够独立写出线性时间复杂度的欧拉回路构造程序，并理解其在计算机译码等场景中的实际应用。
定义：欧拉路径、欧拉回路与（半）欧拉图
本文档中讨论的均为有限图。在图论中：
- 欧拉路径（Eulerian path）：经过图中每条边恰好一次的路径；
- 欧拉回路（Eulerian circuit）：经过图中每条边恰好一次的回路；
- 欧拉图（Eulerian graph）：存在欧拉回路的图；
- 半欧拉图（semi-Eulerian graph）：不存在欧拉回路但存在欧拉路径的图。
需要注意一个容易混淆的细节：上述定义中虽然使用了「路径」一词，但严格说来此处使用的概念应该是「迹（trail）」——欧拉路径与欧拉回路只限制每条边恰好使用一次，对顶点经过次数没有任何限制。也就是说，同一个顶点可以在欧拉路中被反复经过，这与"简单路径"的概念有着本质区别。
性质：欧拉图的三个等价刻画
以下讨论均假设所讨论的图 $G$ 中不存在孤立顶点。该假设不失一般性：对于存在孤立顶点的图 $G$，以下性质对从 $G$ 中删除孤立顶点后得到的图 $G'$ 仍然成立。
对于连通图 $G$，以下三个性质是互相等价的：
- $G$ 是欧拉图；
- $G$ 中所有顶点的度数都是偶数（对于有向图，每个顶点的入度等于出度）；
- $G$ 可被分解为若干条不共边回路的并。
性质 1 ⇒ 性质 2：欧拉回路蕴含偶数度
若 $G$ 是欧拉图，考虑从任意顶点开始沿欧拉回路走一圈。对每个顶点 $v$，其度数等于"离开 $v$ 的次数 + 到达 $v$ 的次数"。由于行动轨迹是一条回路，对每个点 $v$，离开次数等于到达次数。因此每个点的度数都形如 $2k$，即偶数。
特别地，对有向图，根据同样的证明过程，每个顶点的入度等于出度。
性质 2 ⇒ 性质 3：偶数度可拆解为不共边回路
若 $G$ 中所有顶点度数都是偶数（或有向图的入度等于出度），则 $G$ 可被分解为若干条不共边回路的不交并。证明思路如下：
从任意顶点 $u$ 出发，选择任意出边 $(u, v)$，走到相邻顶点 $v$ 并删除$(u, v)$，重复直到返回最初出发点 $u$。可以证明该过程必定会最终回到 $u$：每当到达一个新顶点 $v \neq u$ 时，根据上一条性质，该顶点剩余的度数为奇数，因此必定还存在一条出边，过程不会在 $v$ 处终止——该过程只可能在回到 $u$ 时停止。又因为图 $G$ 的边数是有限的，过程必在有限步内停止，从而必然得到一条回路。
注意到证明过程仅使用了"点度数均为偶数"这一性质，且删除一条回路后剩余图仍满足该性质，故可不断重复直到图为空，从而将 $G$ 拆分为若干条不共边的回路。更进一步，每条回路都可以从被多次经过的顶点处分解成若干简单环的不交并，所以上述性质中的"简单回路"亦可替换为"简单环"。
性质 3 ⇒ 性质 1：不共边回路可合并为欧拉回路
若连通图 $G$ 可分解为若干条不共边回路的不交并，则 $G$ 是欧拉图。每次从中选出两条有共同顶点的回路将其合并为一条，重复直到不存在有共同顶点的两条回路，可以证明结束时剩下的回路唯一：
- 若两条不共边回路 $P_1, P_2$ 共点，可直接在共点处合并；
- 否则，任取 $P_1$ 上的点 $v_1$ 与 $P_2$ 上的点 $v_2$，由 $G$ 的连通性，存在连接 $v_1$ 和 $v_2$ 的路径 $e_1, e_2, \ldots, e_k$，其中每条边 $e_i$ 都被某个回路 $C_i$ 包含，且 $P_1$ 与 $C_1$、$C_i$ 与 $C_{i+1}$、$C_k$ 与 $P_2$ 均存在共点（或 $C_i = C_{i+1}$，不影响证明）。此情况下 $P_1$ 与 $P_2$ 可通过 $C_1, \ldots, C_k$ 合并。
由于任意两条回路都可以合并，最后剩下的回路必唯一，其边集是所有不共边回路的并，即 $E(G)$。这条回路就是 $G$ 上的欧拉回路，$G$ 为欧拉图。
判定条件与半欧拉图
以上性质构成了欧拉图的判断条件：一个图是欧拉图，当且仅当非零度顶点互相（强）连通，且所有顶点的度数都是偶数（或有向图每个顶点的入度等于出度）。
半欧拉图的性质与欧拉图相似：
- 半欧拉图具有恰好两个奇度数顶点，且这两个顶点正是欧拉路径的两个端点；
- 将这两个奇度点连接起来，可以将半欧拉图转化为欧拉图；
- 删除欧拉图中的任意一条边，可以得到一个半欧拉图。
由此导出半欧拉图的判别法：一个图是半欧拉图，当且仅当非零度顶点互相（强）连通，且奇度数顶点恰好有两个。对于有向图，第二个条件为恰存在两个顶点 $u, v$，满足 $\deg^+(u) - \deg^-(u) = 1$、$\deg^+(v) - \deg^-(v) = -1$，且其余顶点的入度等于出度。
Hierholzer 算法：欧拉回路/欧拉路径的构造
算法思想
构造欧拉回路最常用的是Hierholzer 算法，其核心思想正是利用上述性质中的第三点——欧拉图可以被拆解为若干条不共边回路的并。在欧拉图性质的证明中，其实已经给出了完整可行的"将不共边回路合并为欧拉回路"的操作，且在使用合适的数据结构储存时（如使用类链表的结构储存环）实现并不困难。
算法流程如下：
- 先从图中找到一条回路作为当前回路；
- 每次从当前回路中选取剩余度数不为零的点，从该点出发找到一条新的简单回路；
- 将该简单回路与当前回路合并；
- 重复上述过程，直到当前回路中的所有点均无剩余度数，此时的当前回路即为欧拉回路。
该算法同样适用于有向图。对于半欧拉图，可以从图中找到一条连接两个奇度数点的路径作为当前路径，每次选取度数非零的点寻找简单回路并将其与当前路径合并，最后得到欧拉路径。
伪代码
Hierholzer 算法的伪代码如下：
$$ \begin{array}{ll} 1 & \textbf{Input. } \text{The edges of the graph } e , \text{ where each element in } e \text{ is } (u, v) \ 2 & \textbf{Output. } \text{The vertex of the Euler Road of the input graph}.\ 3 & \textbf{Method. } \ 4 & \textbf{Function } \text{Hierholzer } (v) \ 5 & \qquad circle \gets \text{Find a Circle in } e \text{ Begin with } v \ 6 & \qquad \textbf{if } circle=\varnothing \ 7 & \qquad\qquad \textbf{return } v \ 8 & \qquad e \gets e-circle \ 9 & \qquad \textbf{for} \text{ each } v \in circle \ 10& \qquad\qquad v \gets \text{Hierholzer}(v) \ 11& \qquad \textbf{return } circle \ 12& \textbf{Endfunction}\ 13& \textbf{return } \text{Hierholzer}(\text{any vertex}) \end{array} $$
时间复杂度分析
Hierholzer 算法的时间复杂度为 $O(|E| + |V|)$。关键在于：在前述正确性分析中，在欧拉图或半欧拉图上寻找简单回路（或半欧拉图的初始路径）的过程是无需回溯的——只要沿着剩下的边一直走，就必定可以发现所求的回路或路径，且每条边仅会被访问一次。
为了利用这一性质，实现上应采取类链表的方式储存图中的边，如邻接表或链式前向星，以便每条边在被访问过后即刻删除。如果采用朴素的邻接矩阵进行储存，则每次寻边耗时 $O(|V|)$，总复杂度会退化为 $O(|V||E|)$，这正是许多初学者实现超时的根源。
实际上，该算法的准确复杂度应为 $O(|E|)$ 而非 $O(|V| + |E|)$：实现方式可以采取依赖于边而不依赖于点的方法，通过维护剩余边的总链表来进行下一步回路的寻找。
如果需要输出字典序最小的欧拉路或欧拉回路，则需要将边排序，时间复杂度为 $\Theta(|E|\log |E|)$，或使用计数排序/基数排序达到 $\Theta(|E|)$。
仓库源码剖析：P2731 骑马修栅栏的完整实现
OI-wiki 在 docs/graph/code/euler/euler_1.cpp 中提供了该算法的完整可运行实现，对应洛谷 P2731「骑马修栅栏」一题。题目要求：给定一张有 500 个顶点的无向图，求一条欧拉路或欧拉回路，有多组解时输出字典序最小的一组（欧拉路不要求经过所有顶点，边数 $m$ 满足 $1 \le m \le 1024$）。
存图结构与关键技巧
struct edge { int to; bool exists; int revref; bool operator<(const edge& b) const { return to < b.to; } }; vector<edge> beg[505]; int cnt[505];- 邻接表采用
std::vector<edge>，其中exists标记该边是否仍存在（实现"访问后删除"），revref记录该边在反向边所属邻接表中的下标，用于成对删除无向边的两个方向； operator<按终点排序，配合后文的sort实现字典序贪心；cnt[x]作为游标指针，记录顶点 $x$ 的邻接表已扫描到的位置，避免重复遍历已删除的边——这是保证线性复杂度的关键。
递归主体
void Hierholzer(int x) { for (int& i = cnt[x]; i < (int)beg[x].size();) { if (beg[x][i].exists) { edge e = beg[x][i]; beg[x][i].exists = beg[e.to][e.revref].exists = false; // 成对删除 ++i; Hierholzer(e.to); } else { ++i; } } ans.push(x); // 回溯时入栈 }实现采用了递归 + 回溯入栈的经典写法：从某个顶点出发尽可能深地沿着未删除的边前进（这个过程天然无回溯地找到回路），当某顶点无剩余出边时将其压入答案栈ans（std::stack<int>）。使用栈保存答案是必要的：如果找的不是回路，必须将那一部分放在最后，后进先出的栈结构恰好天然满足这一要求。
起点选择与字典序
int bv = 0; for (int i = 1; i <= dn; ++i) { if (!deg[bv] && deg[i]) { bv = i; } else if (!(deg[bv] & 1) && (deg[i] & 1)) { bv = i; } }起点bv的选取逻辑：优先选择奇度顶点（半欧拉图的欧拉路径端点）；若无奇度顶点（欧拉图），选择第一个有度数的顶点。由于所有邻接表已按终点升序排序，从最小可行起点出发并优先走向编号最小的相邻点，即可保证输出字典序最小。注意beg[i].reserve(1050)预分配空间以避免动态扩容开销，这也是竞赛实现中的常见优化。
示例输入输出验证
仓库附带了该题的一组测试数据（euler_1.in 与 euler_1.ans）：
输入（9 条边）： 1 2 / 2 3 / 3 4 / 4 2 / 4 5 / 2 5 / 5 6 / 5 7 / 4 6 输出（欧拉路径）： 1 → 2 → 3 → 4 → 2 → 5 → 4 → 6 → 5 → 7可以验证：图中奇度顶点为 1 和 7（均为度数 1），因此这是半欧拉图，路径从 1 出发到 7 结束；所有 9 条边恰好各出现一次，且输出按字典序最小。
应用：有向欧拉图与计算机译码
有向欧拉图的一个经典应用是计算机译码。设有 $m$ 个字母，希望构造一个有 $m^n$ 个扇形的圆盘，每个扇区放置一个字母，使得圆盘转动一周（$m^n$ 次）后，得到由 $m$ 个字母产生的长度为 $n$ 的 $m^n$ 个各不相同的符号串（见 译码圆盘示意图）。
构造如下有向欧拉图 $D$：设 $S = {a_1, a_2, \cdots, a_m}$，构造 $D=\langle V, E\rangle$：
- 顶点集 $V = {a_{i_1}a_{i_2}\cdots a_{i_{n-1}} \mid a_i \in S, 1 \le i \le n - 1}$，即所有长度为 $n-1$ 的符号串；
- 边集 $E = {a_{j_1}a_{j_2}\cdots a_{j_{n-1}}a_r \mid a_j \in S}$，即所有长度为 $n$ 的符号串；
- 关联关系：顶点 $a_{i_1}a_{i_2}\cdots a_{i_{n-1}}$ 引出 $m$ 条边 $a_{i_1}a_{i_2}\cdots a_{i_{n-1}}a_r$（$r = 1, 2, \cdots, m$）；边 $a_{j_1}a_{j_2}\cdots a_{j_{n}}$ 引入顶点 $a_{j_2}a_{j_3}\cdots a_{j_{n}}$。
这样的 $D$ 是连通的，且每个顶点的入度等于出度（均等于 $m$），因此 $D$ 是有向欧拉图（构造示意见 构造图 D 示例）。
任求 $D$ 中一条欧拉回路 $C$，取 $C$ 中各边的最后一个字母，按各边在 $C$ 中的顺序排成圆形放在圆盘上即可。这正是"以图论手段构造 de Bruijn 序列"的思路：圆盘旋转一周读出的恰好是全部 $m^n$ 个互不相同的 $n$ 位符号串。
解题要点与习题延伸
综合原文档与 euler_1.cpp 的实现，求解欧拉路类问题时有几点关键经验：
- 先判定再构造：检查连通性（非零度顶点是否连通）与奇度顶点数量（无向图 0 个为欧拉图、2 个为半欧拉图；有向图检查出入度差）；
- 避免邻接矩阵：邻接矩阵寻边耗时 $O(|V|)$，总复杂度退化为 $\Theta(nm)$，必须使用
std::vector或前向星等邻接表结构； - 成对删除无向边：无向图的边要同时标记两个方向为已删除（如
exists标记 +revref反向下标）； - 字典序最小：先对每个顶点的邻接表按终点排序，再从最小可行起点开始 DFS；
- 答案用栈保存：
std::stack<int>后进先出的特性天然适配"路径尾部最后入栈"的顺序要求。
原文档还给出了丰富的练习题目用于巩固：SGU 101 Domino（经典多米诺骨牌配对）、POJ 1780 Code（上文译码应用的直接题目）、洛谷 P1127 词链、洛谷 P1333 瑞瑞的木棍、洛谷 P1341 无序字母对、洛谷 P6066 [USACO05JAN]Watchcow S、洛谷 P6628 [省选联考 2020 B 卷] 丁香之路、洛谷 P3520 [POI 2011] SMI-Garbage 等。这些题目覆盖了从基础判定、字典序最小输出到"欧拉回路套欧拉回路"（先缩连通块再分层构造）的进阶技巧，是检验对欧拉图理解深度的良好训练集。
小结
欧拉图问题的核心链条非常清晰：定义（迹的意义）→ 三个等价性质（偶度、回路分解、欧拉回路）→ 判定条件（连通 + 奇度顶点数量）→ Hierholzer 线性构造。其中"回路分解与合并"既是性质证明的关键，也直接孕育了 Hierholzer 算法；而"每条边只访问一次、无需回溯"的特性，则决定了实现必须采用可即时删除边的邻接表结构。掌握这条链路后，无论是笔试中的欧拉图判定，还是竞赛中的字典序最小欧拉路，都能以 OI-wiki 提供的 euler_1.cpp 为模板快速解决。
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
