欧拉路径（Hierholzer 一笔画）

图算法 · 边走边消 · 图论的起点

从七桥问题说起

1736 年柯尼斯堡的市民想一次走遍七座桥、每座恰走一次——欧拉证明了不可能，图论就此诞生。「每条边恰走一次」的路线叫欧拉路径（起终相同则叫欧拉回路），也就是小学的一笔画。判定出奇地简单，只看度数：

连通图存在欧拉路径 ⟺ 奇度点恰 0 个（回路，随处起笔）或 2 个（路径，必须从一个奇度点起笔、终于另一个）。
直觉：中途路过一个点，总是「进一条边、出一条边」成对消耗——度数得是偶数；只有起点（只出不进一次）和终点（只进不出一次）允许奇数。七桥的四个点全是奇度，所以无解。

Hierholzer：走到卡住，弹栈接环

判定过了怎么把路线画出来？Hierholzer 用栈边走边消：沿未用过的边一路贪心走（走过就消掉、当前点压栈）；走到卡住（当前点无未用边）就弹栈、把它收进路径；若弹完后栈顶还有余边，就从它接着走——走出的子环自动插进路径。栈清空后把弹出序反转，就是欧拉路径，整个过程每条边恰进出栈一次，O(E)。下图徽标是每个点的剩余未用边数——减到 0 就走不动；虚线环表示在栈上。

一笔画：每条边恰好走一次，笔不离纸——能不能画完这 7 条边？这就是欧拉路径（起点终点可以不同；相同则叫欧拉回路）。Hierholzer 算法边走边消，O(E) 一次搞定

1function eulerPath(n: number, edges: [number, number][]): number[] {
const adj = Array.from({ length: n }, () => [] as { v: number; eid: number }[]);
edges.forEach(([u, v], i) => { adj[u].push({ v, eid: i }); adj[v].push({ v: u, eid: i }); });
const deg = adj.map((a) => a.length);
const odd = [...Array(n).keys()].filter((u) => deg[u] % 2 === 1);  // 判定：奇度点 0/2
if (odd.length !== 0 && odd.length !== 2) return [];
const start = odd.length ? odd[0] : 0;         // 有奇度点必须从它出发
const used = new Array(edges.length).fill(false);
const stack = [start];
const path: number[] = [];
while (stack.length) {
  const u = stack[stack.length - 1];
  const next = adj[u].find((e) => !used[e.eid]);
  if (next) {
    used[next.eid] = true;                     // 还有未用边：消边 + 压栈
    stack.push(next.v);
  } else {
    stack.pop();                               // 卡住：弹栈进路径
    path.push(u);
  }
}
return path.reverse();                         // 反转弹出序即欧拉路径
23}

栈（空）

路径（空）

目标7 条边各走一次

1 / 12

为什么子环插得进去

第一段路在终点卡住时，剩下没走的边（如果有）一定挂在栈上某个点的周围，而且这些残边每个点的度数都是偶数（进出成对）——所以从栈顶那个有余边的点出发，必然能走一个环回到它自己。弹栈的顺序恰好把这个环「缝」在正确的位置。应用远不止一笔画：DNA 测序把读段重叠建成 de Bruijn 图后找欧拉路径拼接基因组；扫雪车/邮递员要走遍每条街，是它的加权推广（中国邮递员问题）。与强连通分量、LCA 一样，都是「一遍 DFS/栈」榨干图结构的经典。

算法可视化

欧拉路径（Hierholzer 一笔画）

从七桥问题说起

Hierholzer：走到卡住，弹栈接环

为什么子环插得进去