欧拉路径与回路

一句话说明

欧拉路径要求每条边恰好走一次；Hierholzer 的核心不是“怎么走”，而是“走不动时再把点记入答案”。

先和哈密顿路径分清

问题	恰好一次经过什么
欧拉路径	每条边
哈密顿路径	每个顶点

所以题目里如果强调：

• 所有机票都要用掉
• 所有边都要恰好走一遍

这通常是在提示欧拉路径，不是遍历所有点。

先看存在条件

无向图

• 欧拉回路：所有点度数都是偶数
• 欧拉路径：恰好有 0 或 2 个奇度点

如果有 2 个奇度点，那么：

• 起点必须是其中一个
• 终点必须是另一个

有向图

• 欧拉回路：每个点入度等于出度
• 欧拉路径：
  • 起点满足 out = in + 1
  • 终点满足 in = out + 1
  • 其余点入度等于出度

还有一个前提不能漏

忽略孤立点之后，相关点必须连通。
很多人只检查度数，不检查连通性，这会直接误判。

Hierholzer 为什么有效

它的思路不是“提前规划一条完整路径”，而是：

1. 沿未使用边一直走
2. 走不动了，再把当前点加入答案
3. 一路回退，继续补别的分支

这和后序遍历的感觉很像：

• 不是一进入就记
• 而是走到底、回退时才记

Go 代码：有向图欧拉路径模板

func EulerPathDirected(edges [][2]string, start string) []string {
    graph := map[string][]string{}
    for _, e := range edges {
        u, v := e[0], e[1]
        graph[u] = append(graph[u], v)
        if _, ok := graph[v]; !ok {
            graph[v] = nil
        }
    }
 
    for node := range graph {
        sort.Sort(sort.Reverse(sort.StringSlice(graph[node])))
    }
 
    stack := []string{start}
    route := []string{}
 
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        if len(graph[node]) > 0 {
            next := graph[node][len(graph[node])-1]
            graph[node] = graph[node][:len(graph[node])-1]
            stack = append(stack, next)
        } else {
            route = append(route, node)
            stack = stack[:len(stack)-1]
        }
    }
 
    reverseStrings(route)
    return route
}
 
func reverseStrings(arr []string) {
    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
}

为什么答案最后要反转

因为节点是“走不动时”才加入答案的。
也就是说，记录顺序其实是：

终点方向 -> 起点方向

所以最后必须整体反转，才得到真正的欧拉路径。

为什么常常要给邻接表排序

像“重新安排行程”这类题，除了要求存在欧拉路径，还要求：

字典序最小

这时常见做法是：

• 先把邻接表逆序排序
• 每次 pop 末尾元素

这样既方便实现，又能保证取到当前最小可用边。

无向图要额外注意什么

无向边会在两个方向都出现。
所以不能只靠“删掉邻居值”判断一条边是否用过，而要：

• 给每条边编号
• 标记边是否已使用

否则同一条无向边很容易被算两次。

常见题型

• 重新安排行程
• 一笔画问题
• 把数对重排成合法链
• 判断图是否存在欧拉回路

易错点

欧拉路径最容易错的地方

• 只看度数不看连通性，会误判。
• 结果是在回退时生成的，最后一定要反转。
• 无向图必须避免同一条边被双向各走一次。
• 如果题目要求字典序最小，邻接表顺序必须提前处理。

复杂度

场景	时间复杂度	空间复杂度
不排序邻接表	O(V + E)	O(V + E)
需要排序	O(E \log E)	O(V + E)

相关主题

• DFS基础模板
• DFS 与 BFS
• 图算法

---

返回：图算法 | 算法学习导航