Hierholzer 算法
用栈不断走未使用的边,回溯时把顶点追加到答案,反转后得到欧拉迹;时间与 n+m 成正比。时间 O(n + m),空间 O(n + m) · 标签 图论 / 欧拉图 / 欧拉回路 / 欧拉路径 / 栈
问题形式
给定无向图或有向图 ,要求构造一条经过每条边恰好一次的迹。存在欧拉回路时,起点与终点相同;只存在欧拉迹时,起点必须是奇度顶点(无向图)或满足 的顶点(有向图)。
存在性条件见 欧拉图判定。若所有度非零顶点不在同一个连通分量内,则不存在欧拉迹。
核心思想
只在有边的连通分量上构造。维护一个栈,栈底是起点,栈中相邻顶点对应一条已经使用过的边。
记栈顶为 :
- 若 还有未使用的边,取一条 ,标记这条边已使用,把 入栈;
- 若 没有未使用的边,弹出 ,把 追加到答案序列末尾。
有向图中“未使用的边”指未使用的出边。栈空后,把答案序列反转,就得到一条欧拉迹。
正确性
开放欧拉迹可以先在终点与起点之间加一条虚边,化为欧拉回路;删去虚边即得原问题的解。因此只需说明回路情形;以下假设 满足欧拉迹的存在性条件,且起点按上述规则选择。
栈中从栈底到栈顶始终是一条迹:每次入栈都沿一条未使用的边前进,因此不会重复边。
若栈顶 没有未使用的边,弹出 不会使剩余的未使用边消失;之后若栈中某个祖先还有未使用的边,就从该祖先继续走,在已有迹上拼接一段闭迹。反转答案时,后形成的闭迹会被接到先形成的闭迹前面,因此仍是一条连续迹。
每条边恰好被标记一次。若 满足欧拉迹存在性条件且起点选择正确,算法使用所有边,反转后得到欧拉迹;若结束后仍有未使用的边,则 不满足存在性条件、所有度非零顶点不在同一连通分量,或起点选择错误。
易错点
- 存在开放欧拉迹时,起点必须是奇度顶点(无向图)或 的顶点(有向图);从其他顶点出发会留下未使用的边。
- 无向图的一条边要从两个端点的邻接表中删除,或统一用边编号标记;只按端点删除会误删重边。
- 自环也要占用一条边编号;它的两个端点相同,不能按“两个不同端点”处理。
- 答案是弹出顺序的反转;直接输出弹出顺序会得到反向的迹,可能不满足指定起点或字典序。
- 算法结束时要检查是否使用了 条边;只检查栈空不够,非连通图可能只处理了一个分量。
- 长链上递归可能溢出,使用显式栈。
与 Fleury 的取舍
Fleury 每次必须选一条不是桥的边(桥指删去后图不连通的边),需要反复判断桥,朴素实现较慢。
Hierholzer 只需邻接表和已使用标记,构造过程中自动拼接闭迹;代价是需要保存边编号,且无向图要处理两个方向。竞赛中通常使用 Hierholzer。
变式
- 有向图:把“未使用的边”换成“未使用的出边”,起点按 选择。
- 开放欧拉迹:也可以在终点与起点之间加一条虚边,先构造欧拉回路,再从答案中删去虚边。
- 多重图与自环:用边编号标记已使用,不能只按端点删除。
- 固定起点:先按存在性条件选起点;若题目指定起点,先确认它符合奇度或出入度条件。