Hierholzer 算法

用栈不断走未使用的边,回溯时把顶点追加到答案,反转后得到欧拉迹;时间与 n+m 成正比。

时间 O(n + m),空间 O(n + m) · 标签 图论 / 欧拉图 / 欧拉回路 / 欧拉路径 / 栈

问题形式

给定无向图或有向图 𝐺=(𝑉,𝐸),要求构造一条经过每条边恰好一次的迹。存在欧拉回路时,起点与终点相同;只存在欧拉迹时,起点必须是奇度顶点(无向图)或满足 𝑑+(𝑣)=𝑑−(𝑣)+1 的顶点(有向图)。

存在性条件见 欧拉图判定。若所有度非零顶点不在同一个连通分量内,则不存在欧拉迹。

核心思想

只在有边的连通分量上构造。维护一个栈,栈底是起点,栈中相邻顶点对应一条已经使用过的边。

记栈顶为 𝑣:

  • 若 𝑣 还有未使用的边,取一条 (𝑣,𝑢),标记这条边已使用,把 𝑢 入栈;
  • 若 𝑣 没有未使用的边,弹出 𝑣,把 𝑣 追加到答案序列末尾。

有向图中“未使用的边”指未使用的出边。栈空后,把答案序列反转,就得到一条欧拉迹。

正确性

开放欧拉迹可以先在终点与起点之间加一条虚边,化为欧拉回路;删去虚边即得原问题的解。因此只需说明回路情形;以下假设 𝐺 满足欧拉迹的存在性条件,且起点按上述规则选择。

栈中从栈底到栈顶始终是一条迹:每次入栈都沿一条未使用的边前进,因此不会重复边。

若栈顶 𝑣 没有未使用的边,弹出 𝑣 不会使剩余的未使用边消失;之后若栈中某个祖先还有未使用的边,就从该祖先继续走,在已有迹上拼接一段闭迹。反转答案时,后形成的闭迹会被接到先形成的闭迹前面,因此仍是一条连续迹。

每条边恰好被标记一次。若 𝐺 满足欧拉迹存在性条件且起点选择正确,算法使用所有边,反转后得到欧拉迹;若结束后仍有未使用的边,则 𝐺 不满足存在性条件、所有度非零顶点不在同一连通分量,或起点选择错误。

易错点

  • 存在开放欧拉迹时,起点必须是奇度顶点(无向图)或 𝑑+(𝑣)=𝑑−(𝑣)+1 的顶点(有向图);从其他顶点出发会留下未使用的边。
  • 无向图的一条边要从两个端点的邻接表中删除,或统一用边编号标记;只按端点删除会误删重边。
  • 自环也要占用一条边编号;它的两个端点相同,不能按“两个不同端点”处理。
  • 答案是弹出顺序的反转;直接输出弹出顺序会得到反向的迹,可能不满足指定起点或字典序。
  • 算法结束时要检查是否使用了 𝑚 条边;只检查栈空不够,非连通图可能只处理了一个分量。
  • 长链上递归可能溢出,使用显式栈。

与 Fleury 的取舍

Fleury 每次必须选一条不是桥的边(桥指删去后图不连通的边),需要反复判断桥,朴素实现较慢。

Hierholzer 只需邻接表和已使用标记,构造过程中自动拼接闭迹;代价是需要保存边编号,且无向图要处理两个方向。竞赛中通常使用 Hierholzer。

变式

  • 有向图:把“未使用的边”换成“未使用的出边”,起点按 𝑑+(𝑣)=𝑑−(𝑣)+1 选择。
  • 开放欧拉迹:也可以在终点与起点之间加一条虚边,先构造欧拉回路,再从答案中删去虚边。
  • 多重图与自环:用边编号标记已使用,不能只按端点删除。
  • 固定起点:先按存在性条件选起点;若题目指定起点,先确认它符合奇度或出入度条件。
源码位置