欧拉路径查找器

伪代码

存在性判定纯粹是计数，一趟即可完成。只有在判定通过之后，才用 Hierholzer 而不是朴素回溯去构造这条路径。

// 存在性判定（连通的无向图）：
//   0 个奇度结点 -> 存在欧拉回路
//   2 个奇度结点 -> 存在两者之间的欧拉路径
//   其他情况     -> 两者都不存在

Hierholzer(图, 起点):
    栈 = [起点]; 路径 = []

    当栈非空时:
        u = 栈.顶
        若 u 还有未使用的关联边 (u,v):
            把该边标记为已使用
            栈.压入(v)
        否则:
            路径.追加(栈.弹出())

    反转 路径

Hierholzer 之所以奏效，是因为它从不需要猜测。它一直走到走不动为止；在所有结点度数都为偶数的图上，这只可能发生在起点。随后它从仍有未使用边的结点处把绕行环拼接进来。每个结点被进入和离开的次数相同，而这正是偶数度所保证的，因此这些片段总能合并成一条闭合的路径。

分步示例演算

在两个共用一个结点的三角形上构造欧拉回路，邻居按字母顺序选取。

示例图: 无向边 A-B、B-C、C-A 构成一个三角形，C-D、D-E、E-C 构成第二个，两者在 C 处相连。

1. 先检查度数. A 的度为 2，B 为 2，C 为 4，D 为 2，E 为 2。所有度数都是偶数且图是连通的，因此欧拉回路存在，而且可以从任意结点出发。
2. 一直走到卡住. 从 A 出发走 A-B，再走 B-C，再从 C 走 C-A。此时回到 A，而它的两条边都已用过，于是走不动了。注意它恰好卡在起点上，这正是偶数度所导致的必然结果。
3. 把第二个三角形拼接进来. 回退栈时到达 C，它还有未使用的 C-D 与 C-E。依次走 C-D、D-E、E-C，此时 C 也被用尽。
4. 展开成路径. 既然任何地方都不再有未使用的边，栈便依次弹空，反转之后的结果就是这条回路。

欧拉回路是 A 到 B 到 C 到 D 到 E 到 C 到 A，恰好用完全部六条边并回到起点。注意 C 在路径中出现了两次，这是允许且预期之中的：欧拉路径可以自由地重复经过结点，唯一不允许的是重复使用某条边。这正是它与哈密顿路径的全部差别，后者要求每个结点只访问一次，而根本不关心边。

复杂度及其来源

时间: O(V + E) · 空间: O(V + E)

度数统计是对所有边扫一遍，为 O(E)；连通性检查是一次遍历，为 O(V + E)。Hierholzer 对每个结点出现只压栈一次、弹栈一次，并把每条边恰好标记为已使用一次，因此是 O(E)，前提是每个结点都保留一个指向其邻接表的指针，而不是每次都从头重扫。若没有这个指针，内层查找会退化为 O(V·E)。空间开销是已使用边的标记，再加上栈与路径，二者各持有 O(E) 个条目。与哈密顿路径的对比很值得一提：欧拉问题是线性的，哈密顿问题是 NP 完全的，原因纯粹在于边可以通过度数在局部计数，而结点不行。

何时使用欧拉路径（无向图），何时不宜

欧拉类问题很容易；表面上相似的哈密顿类问题却不是。先确认你面对的究竟是哪一个。

常见陷阱

• 忘掉连通性这一要求. 仅有偶数度是不够的。由两个互不相连的三角形构成的图，每个结点的度都是偶数，却不存在欧拉回路，因为没有任何路径能在分量之间跳跃。所有边都必须位于同一个连通分量中；度为零的孤立结点则可以放心忽略。
• 把欧拉与哈密顿混为一谈. 欧拉是每条边用一次、结点可以重复；哈密顿是每个结点访问一次、边可以不用。两者名字相近，难度却天差地别：线性与 NP 完全之别。
• 在 Hierholzer 中反复重扫邻接表. 如果每次寻找未使用边都从该结点邻接表的开头开始，算法就会变成平方级。请为每个结点维护一个只向前推进的迭代器，因为一条已用过的边此后永远不会再有用。
• 把无向图的度数规则套用到有向图上. 有向图要成回路，需要每个结点的入度等于出度；要成路径，则需恰好一个结点出度减入度为 1，另一个入度减出度为 1。去统计总度数会得到错误结论。
• 在错误的结点上开始一条路径. 当恰好有两个奇度结点时，路径必须从其中一个出发并在另一个结束。从别处开始，就意味着最终会带着剩余的边卡住。

常见问题

什么是欧拉路径？

欧拉路径是一条恰好使用图中每条边一次的路径。它可以多次访问同一个结点。如果它还回到出发结点，就称为欧拉回路。这一概念源自欧拉在 1736 年解决哥尼斯堡七桥问题，那也是图论的开端。

欧拉路径在什么条件下存在？

在连通的无向图中，当所有结点的度都是偶数时存在欧拉回路；当恰好有两个结点的度为奇数时存在欧拉路径，且该路径必须从其中一个出发、在另一个结束。奇度结点为其他数量时，两者都不存在。此外，所有边都必须位于同一个连通分量之中。

欧拉路径与哈密顿路径有什么区别？

欧拉路径每条边用一次，允许重复访问结点；哈密顿路径每个结点访问一次，允许不使用某些边。二者的难度差异极大：判定欧拉路径是否存在只需 O(V + E) 地统计度数，而哈密顿问题是 NP 完全的。

Hierholzer 算法是怎样工作的？

它沿未使用的边不断前进，直到走不动为止；在所有度数为偶的图上，这只会发生在起点。随后它沿栈回退，一旦发现某个结点还有未使用的边，就从那里走出一条新的闭合环并拼接进去。把栈弹空即可按逆序得到完整路径，整个过程为 O(E)。

寻找欧拉路径的时间复杂度是多少？

O(V + E)。统计度数为 O(E)，检查连通性是一次遍历，而 Hierholzer 把每条边恰好标记一次为已使用。关键的实现细节是为每个结点在邻接表中保留一个指针，使得寻找未使用边时永不重扫，这才让算法保持线性而非平方级。