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_{i1}$、$C_k$ 与 $P_2$ 均存在共点或 $C_i C_{i1}$不影响证明。此情况下 $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; } }; vectoredge beg[505]; int cnt[505];邻接表采用std::vectoredge其中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); // 回溯时入栈 }实现采用了递归 回溯入栈的经典写法从某个顶点出发尽可能深地沿着未删除的边前进这个过程天然无回溯地找到回路当某顶点无剩余出边时将其压入答案栈ansstd::stackint。使用栈保存答案是必要的如果找的不是回路必须将那一部分放在最后后进先出的栈结构恰好天然满足这一要求。起点选择与字典序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::stackint后进先出的特性天然适配路径尾部最后入栈的顺序要求。原文档还给出了丰富的练习题目用于巩固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），仅供参考