欧拉回路/路径是图论中的经典问题：能否一笔画完所有边且不重复？从柯尼斯堡七桥问题到现代应用（DNA 测序、垃圾回收），欧拉算法无处不在。
| 条件 | 欧拉回路 | 欧拉路径 |
|---|---|---|
| 连通性 | 所有边所在顶点连通 | 同左 |
| 度数 | 所有顶点度数为偶数 | 恰好 0 或 2 个奇度顶点 |
| 条件 | 欧拉回路 | 欧拉路径 |
|---|---|---|
| 连通性 | 弱连通 | 同左 |
| 度数 | 每个顶点入度=出度 |
交互式动画演示，可调整参数并单步执行。
全屏打开| 一个出度-入度=1（起点），一个入度-出度=1（终点），其余相等 |
核心思想：DFS + 回溯时记录边（后序）。
// 无向图，邻接表 + 边删除
Map<Integer, Queue<Integer>> adj = new HashMap<>();
List<Integer> circuit = new ArrayList<>();
void hierholzer(int u) {
Queue<Integer> neighbors = adj.getOrDefault(u, new LinkedList<>());
while (!neighbors.isEmpty()) {
int v = neighbors.poll();
adj.get(v).remove(Integer.valueOf(u)); // 删除反向边
hierholzer(v);
}
circuit.add(u); // 后序加入
}
// 使用
hierholzer(start);
Collections.reverse(circuit); // 反转得到欧拉回路Map<Integer, Queue<Integer>> adj = new HashMap<>();
List<Integer> path = new ArrayList<>();
void dfs(int u) {
Queue<Integer> q = adj.getOrDefault(u, new LinkedList<>());
while (!q.isEmpty()) {
int v = q.poll();
dfs(v);
}
path.add(u);
}// 有向图欧拉路径
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> adj = new HashMap<>();
for (List<String> t : tickets) {
adj.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).add(t.get(1));
}
List<String> result = new ArrayList<>();
dfs("JFK", adj, result);
Collections.reverse(result);
return result;
}
void dfs(String u, Map<String, PriorityQueue<String>> adj, List<String> result) {
PriorityQueue<String> pq = adj.getOrDefault(u, new PriorityQueue<>());
while (!pq.isEmpty()) {
dfs(pq.poll(), adj, result);
}
result.add(u);
}每次选一条"非桥"的边走。判断桥需要 O(m) → 总 O(m²)，不如 Hierholzer 的 O(m)。
| 场景 | 说明 |
|---|---|
| 一笔画 | 判断能否一笔画完 |
| DNA 测序 | De Bruijn 图 → 欧拉路径 |
| 垃圾回收 | 扫描所有街道的最优路线 |
| 电路板布线 | 覆盖所有连线 |
| 字典序最小路径 | Hierholzer + 优先队列 |
| 算法 | 时间 | 空间 |
|---|---|---|
| 判定（度数） | O(V + E) | O(V) |
| Hierholzer | O(E) | O(E) |
| Fleury | O(E²) | O(E) |
以 LC 332 的机票 [[JFK,SFO],[JFK,ATL],[SFO,ATL],[ATL,JFK],[ATL,SFO]] 为例：
邻接表（按字典序排序）：
JFK: [ATL, SFO]
ATL: [JFK, SFO]
SFO: [ATL]
Hierholzer（后序记录）：
dfs(JFK):
走 ATL → dfs(ATL):
走 JFK → dfs(JFK):
走 SFO → dfs(SFO):
走 ATL → dfs(ATL):
无边可走 → 记录 ATL
记录 SFO
记录 JFK
记录 ATL
记录 JFK
记录顺序（后序）: [ATL, SFO, JFK, ATL, JFK]
反转 → [JFK, ATL, JFK, SFO, ATL] ✓ 欧拉路径
为什么“后序记录 + 反转”有效：当某个节点“无路可走”时它一定是当前路径的终点；先记录的总是路径末端，反转后即为从起点到终点的顺序。
练习推荐：先在练习题模块完成 岛屿数量 巩固图遍历，再挑战 LC 332 与 LC 753。