欧拉路/欧拉回路

What · 是什么

欧拉路径（Eulerian path）是经过图中每条边恰好一次的路径，欧拉回路（Eulerian circuit）是每条边恰好一次的回路。存在欧拉回路（且非零度顶点连通）当且仅当所有顶点度数为偶数（无向）或每个顶点入度等于出度（有向）。存在欧拉路径（半欧拉图）当且仅当连通且恰有两个奇度顶点（无向）或有向图恰有两个顶点满足出度−入度=±1 而其余平衡。Hierholzer 算法：从起点开始沿剩余边任意行走并删除走过的边，用栈记录，当走到死胡同（度数耗尽）时回溯，最终把得到的路径反转即为欧拉路径/回路。经典应用：单词接龙（每个单词是边）、邮递员问题、中文一笔画、de Bruijn 序列构造。输出字典序最小的欧拉路需将边排序（复杂度加 O(E log E)）。

Why · 为什么

How · 实现

伪代码

# 判定
非零度顶点组成的子图需连通（弱连通）
无向: 奇度顶点数 0 -> 回路, 2 -> 路径, 否则无
有向: 入度==出度全成立 -> 回路; 恰一个出-入=1 且一个入-出=1 -> 路径

# Hierholzer（迭代）
stack = [起点]; path = []
while stack:
    v = stack[-1]
    if v 仍有未用出边:
        (u,w) = 取下一条边; 删除它
        stack.append(w)
    else:
        path.append(v); stack.pop()
path 反转即为欧拉路径
# 若 path 长度 != 边数+1，图不连通无解

Python 实现

# -*- coding: utf-8 -*-
# Hierholzer 算法求有向图欧拉路径/回路（返回顶点序列；无解返回 None）
# 支持重边；字典序最小：把每个顶点的出边排序后依次取
def hierholzer_directed(edges, n):
    """edges: list of (u, v)。返回欧拉路径顶点序列（回路首尾相同）或 None。"""
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    outdeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        outdeg[u] += 1
        indeg[v] += 1
    for v in range(n):
        adj[v].sort()
    # 度数判定
    start = 0
    cnt_out_gt = cnt_in_gt = 0
    for v in range(n):
        if indeg[v] != outdeg[v]:
            if outdeg[v] - indeg[v] == 1:
                cnt_out_gt += 1
                start = v
            elif indeg[v] - outdeg[v] == 1:
                cnt_in_gt += 1
            else:
                return None
    if cnt_out_gt != cnt_in_gt or cnt_out_gt > 1:
        return None
    if cnt_out_gt == 0:          # 回路：从任意有边的顶点出发
        for v in range(n):
            if outdeg[v] > 0:
                start = v
                break
        else:
            return []
    # Hierholzer
    pos = [0] * n
    path = []
    stack = [start]
    while stack:
        v = stack[-1]
        if pos[v] < len(adj[v]):
            stack.append(adj[v][pos[v]])
            pos[v] += 1
        else:
            path.append(v)
            stack.pop()
    path.reverse()
    if len(path) - 1 != len(edges):   # 图不连通/未用完边
        return None
    return path


if __name__ == '__main__':
    # 三角形回路
    e = [(0, 1), (1, 2), (2, 0)]
    p = hierholzer_directed(e, 3)
    assert p is not None and len(p) == 4 and p[0] == p[-1], p
    # 链式欧拉路径 0->1->2
    p0 = hierholzer_directed([(0, 1), (1, 2)], 3)
    assert p0 == [0, 1, 2] or p0 == [0, 1, 2, None], p0
    assert p0 is not None and len(p0) == 3
    # 度数不平衡无解（0->1, 2->1）
    assert hierholzer_directed([(0, 1), (2, 1)], 3) is None
    # 链式欧拉路径：0->1, 1->2, 2->0, 0->3, 3->4
    e2 = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4)]
    p2 = hierholzer_directed(e2, 5)
    # 用边集合验证
    def valid_path(p, edges, n):
        if p is None:
            return False
        if len(edges) == 0:
            return len(p) == 0
        if len(p) - 1 != len(edges):
            return False
        from collections import Counter
        es = Counter((a, b) for a, b in zip(p, p[1:]))
        return es == Counter(edges)
    assert valid_path(p2, e2, 5)
    # 随机图对拍：暴力确认
    import random
    random.seed(0)
    for _ in range(200):
        n = random.randint(1, 6)
        m = random.randint(0, 12)
        edges = []
        for _ in range(m):
            edges.append((random.randrange(n), random.randrange(n)))
        got = hierholzer_directed(edges, n)
        # 暴力判定欧拉路径存在性
        indeg = [0] * n
        outdeg = [0] * n
        for u, v in edges:
            outdeg[u] += 1
            indeg[v] += 1
        d = [outdeg[i] - indeg[i] for i in range(n)]
        ok_deg = (all(x == 0 for x in d) or
                  (sum(1 for x in d if x == 1) == 1 and sum(1 for x in d if x == -1) == 1
                   and all(x in (0, 1, -1) for x in d)))
        # 弱连通性检查（忽略孤立点与自环）
        adj_u = [[] for _ in range(n)]
        for u, v in edges:
            adj_u[u].append(v); adj_u[v].append(u)
        seen = set()
        def dfs(x):
            seen.add(x)
            for y in adj_u[x]:
                if y not in seen: dfs(y)
        roots = [i for i in range(n) if indeg[i] + outdeg[i] > 0]
        if roots:
            dfs(roots[0])
        conn = set(roots) <= seen
        exists = ok_deg and conn
        if not exists:
            assert got is None, (edges, got)
        else:
            assert got is not None and valid_path(got, edges, n), (edges, got)
    print('euler-path tests passed')

易错点

• 不判连通：度数满足但非连通图无欧拉路（孤立点要排除）
• 无向图删除边时必须同时删除反向边，否则可能重复走
• 欧拉回路起点可选任意非零度顶点；路径起点必须选出-入=1 的顶点
• 迭代式 Hierholzer 输出顺序是栈弹出序，需整体反转
• 重边：边排序/计数不能用 set 去重
• 有向图判连通时用弱连通（忽略方向）即可

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/euler/
• CP-Algorithms✓ https://cp-algorithms.com/graph/euler_path.html
• 书籍✓ CPH ch19 pp183-190