课前零食：从散步到欧拉回路

建议在正式学习欧拉路径前 5--7 天吃完。今天不做 OJ 题；我们只把“每条边走一次”这件事看懂，免得一上来就被 Hierholzer 这个名字唬住。

本节目标

学完后，你能：

分清“每个点一次”的哈密顿路径和“每条边一次”的欧拉路径（Eulerian trail）；
用“进入要有离开配对”的想法自己推出无向图的奇度点条件；
解释为什么不能只把普通 DFS 的访问顺序当作答案；
看懂栈版 Hierholzer 如何把小回路接回大回路，并带着这张地图进入正式课。

前置知识与课前自测

只需要：无向图、邻接表、栈，以及“每条边有两个端点”。先不要查答案，拿纸画一画。

三角形的三个点都已经访问过后，还有没有可能存在一条没有走过的边？
一条从 $S$ 到 $T$ 的路线经过中间点 $X$ 时，为什么 $X$ 用掉的边常常能两两配对？
图里有两个互不相连的三角形；每个点度数都是 2。能从某一点一笔走完所有边吗？

先核对想法

1. 有可能。欧拉问题把“边”当待完成的工作；普通 DFS 通常把“点”当待访问的对象。 2. 每一次从 $X$ 进入，若路线还没结束，就要从 $X$ 沿另一条未用边离开。 3. 不能。度数条件只管每个局部入口能否配对；非孤立点还必须处在同一连通块中。

互动规则：把边剪成卡片，再开始走

今天不要先在脑中想“DFS”。拿纸画点、把每条边编号成一张卡；每走一条边，就把那张卡翻面。你的纸上账本固定有四栏：

对象	状态	本轮动作	必须不变的事
路口与道路	当前站在哪、哪些边已用	选一张相连的未用边走过去	一张道路卡最多翻一次
正在形成的路线	路线首尾、尚未收尾的部分	继续走或把尾巴收起来	已收好的部分不应再需要新边

先写下预测，再看折叠答案。今天的目标不是记住 Hierholzer 的拼写，而是能回答：为什么“走过点”不够，为什么“无路可走”反而是好消息？

从零搭框架：先当一次笨拙的邮递员

第 0 步：点的任务和边的任务不是同一道题

画三角形 $A-B-C-A$。若任务是“每个点至少到一次”，从 $A$ 走到 $B$ 再到 $C$ 就可以停；若任务是“每条边恰好一次”，此时边 $C-A$ 还躺在地上。请在三条边旁分别写 已用/未用，不要只给点打访问标记。

停顿 0：普通 DFS 遇到已访问的 $A$ 时通常会怎样做？为什么这会误伤边 $C-A$？

展开：第一个状态修正

普通 DFS 往往不再递归到已访问点；但欧拉问题允许、甚至经常必须沿一条新边回到旧点。于是 `visited_vertex` 不是主要账本，真正的账本是 `used_edge[id]`。重边要有不同编号；自环也会在同一个点的邻接表里出现两次。

第 1 步：故意从错误的起点出发

画边：A-B, B-C, C-A, C-D, D-E。先从 $A$ 出发，并尽量“看到哪条未用边就走哪条”：

A -> B -> C -> D -> E

现在手上还有哪张边卡？当前站在哪里？还能回去拿它吗？

停顿 1：别立即改路线。请写出所有点的度数，并圈出奇数。你认为这条欧拉路径的两个端点被允许是谁？

展开：失败不是因为手气差

未用边是 `C-A`，但人已在 $E$，无法瞬移回去。度数为 $A:2,B:2,C:3,D:2,E:1$；奇度点只有 $C,E$，所以若存在欧拉路径，必须从 $C$ 或 $E$ 出发，而不是任意点。正确路线之一为 `E→D→C→A→B→C`。这让我们发明第一条框架规则：先检查局部的“进出账”是否能配平，再考虑如何构造。

第 2 步：把进出账写成一张表

对一条路线内部的点，每次沿边进入，都要沿另一条未用边离开。请给下表补上“未配对的动作”：

点的位置	进入次数与离开次数的关系	允许的度数奇偶
中间点
起点（非回路）
终点（非回路）
回路中的所有点

展开：无向图的度数条件从账本长出来

中间点的进入和离开配对，度数为偶数；起点多一次离开、终点多一次进入，所以各是奇数；回路没有端点，所有度数为偶数。因此奇度点数只能为 0 或 2。它只是必要条件：两堆互不连通的三角形全为偶度，却仍无法用一条行走覆盖。

第 3 步：路线为什么不能只是一条向前的指针

重新画两个共用 $A$ 的三角形。先只绕左三角形得到 A→B→C→A。此时路线已经闭合，但右三角形的边还未用。请在这条路线中圈出一个还能出发的点，并试着把右三角形的回路写进原路线的哪个空隙。

停顿 3：如果你把新回路直接接在路线末尾，会得到一条连续路线吗？为什么必须“插入”而不是“追加”？

展开：把局部回路嵌进旧路线

右三角形也从 $A$ 出发并回到 $A$，可写成 `A→D→E→A`。把它替换旧路线里的那个 `A`，得到 `A→D→E→A→B→C→A`。追加在末尾也恰好可行是因为旧路线尾端是 A；一般剩余边连接的是旧路线中间某点，只有“在该点插入”才连续。

第 4 步：把“以后再插回去”交给栈

现在给框架命名之前，先写下需要记住什么：

current / stack：还没有收尾的一段行走
used_edge[id]：每张道路卡是否已翻面
ptr[u]：u 的邻接表已经翻到哪里
answer：已经确认应放在最终路线尾部的点

当栈顶还有未用边，就继续向下走；当它没有未用边，这个点以后不可能再接新道路，才可以从栈顶弹出、收进 answer。这不是“回溯撤销边”，而是终于知道一段路线的结尾应该放在哪里。

问题动机：把邮递员派去试路会怎样

想象每条边是一条必须巡查一次的小路。最暴力的想法是：站在当前点，枚举下一条尚未巡查的路；走不通就撤销，换一条。若有很多岔路，选择序列会像排列一样迅速爆炸。邮递员还没出门，搜索树已经开始长蘑菇了。

看这张图：两个三角形共用 $A$。从 $A$ 先绕完左三角形，仍然回到 $A$；右三角形并没有消失，只是应该被接到已有路线中间。

关键转变是：不猜整条路线，而是维护一条已经闭合、可以继续插入小回路的路线。

步步式引导

1. 先让每个路口把账算平

从路线内部的点 $X$ 看：每次进来都要出去，所以已使用的关联边成对出现。只有起点允许多一次离开，终点允许多一次进入。因此无向图中：

全部点度数为偶数时，可以期待一条回到起点的欧拉回路；
恰有两个奇度点时，它们只能分别是路径的两个端点；
奇度点超过两个时，账永远配不平，不用开始搜索。

停顿：一条自环给一个点贡献几度？请在纸上画“进”和“出”各一次。

展开

是 2 度。虽然边两端写的是同一个点，它仍提供一次进入和一次离开；实现邻接表时也要把它当作两份邻接记录。

2. 找到一个回路后，为什么可以放心收起来

从某个还有未用边的点出发，一直沿未用边走。若每个点的剩余度数仍是偶数，就不会在别处“只进不能出”；最后会回到出发点，得到一个小回路。若它的起点在旧路线里，把这个小回路插在该点的位置，旧路线和新回路都没有丢边，也没有重边。

这就是 Hierholzer 算法的发明思路：先走到无路可走，再把完成的尾巴反向收进答案。栈恰好替我们记住“回到哪里插”。

3. 把插回动作改写成栈

设 used[e] 表示边 e 是否已经领过巡查单，ptr[u] 表示邻接表中已经检查到的位置。每条边只会被 ptr 跳过一次、被标记一次。

# start 是奇度点之一；若没有奇度点，任取有边的点
stack = [start]
answer = []                 # 这里收集的是倒序路线
while stack is not empty:
    u = stack.top()
    advance ptr[u] past used edges
    if u still has an unused edge e = (u, v):
        used[e] = true
        stack.push(v)       # 先继续把一条小回路走深
    else:
        answer.append(stack.pop())
return reverse(answer)

纸上模拟：先预测弹栈顺序，再看答案顺序

对边编号：0:A-B, 1:B-C, 2:C-A, 3:A-D, 4:D-E, 5:E-A，从 $A$ 出发。请填写前六次“向下走”的栈；之后不要急着反转，先预测谁最先进入 answer。

动作	走的边	栈（底到顶）	倒序 `answer`
开始	—	`A`	`[]`
向下走	0
向下走	1
向下走	2
向下走	3
向下走	4
向下走	5
无边可走，弹栈	—

展开：为什么答案反过来

六次向下走后栈为 `A,B,C,A,D,E,A`。最后一个 $A$ 没有未用边，最先进入倒序答案；随后依次是 `E,D,A,C,B,A`。反转得到 `A,B,C,A,D,E,A`。每个点被收进答案时，以它为栈顶的未用边已经清空，所以它恰应位于尚未收好路线的末端。

answer 的一个点被加入时，说明从它出发的所有未用边都已经处理完；它正好该排在剩余路线的末尾。倒过来以后，每相邻两个点对应一条已走边。

核心知识：小回路不会把大路线弄乱

算法维护两个不变量：

栈中相邻顶点之间恰对应一条不同的已使用边，因此栈代表当前尚未收尾的一段行走；
只有栈顶已经没有未用边时才弹出，所以被写入 answer 的顶点之后不再需要插入新的边。

每次前进恰新增一条边；每次回退只收集已经走完的部分。若所有非孤立点连通且奇度数为 0 或 2，最终会用尽全部边。反向答案的长度应为 $E+1$；这是很实用的验收器：少了说明漏边，多了说明某条边重复使用。

时间复杂度是 $O(V+E)$，空间是 $O(V+E)$。它比回溯快的原因不是“栈很神奇”，而是它完全不撤销已确定的边：每条边只有一次职业生涯。

实现指南

无向边必须有边编号。不能只标记 used[u][v]：重边会互相误伤，自环也会变得尴尬。
只检查度数还不够；从任意非孤立点 DFS/BFS 后，所有度数非零的点都应被看见。
输出前检查答案长度是否为 edge_count + 1。正式课会进一步处理有向边、字典序和建模。
ptr[u] 是防止反复扫描陈旧边的关键。没有它，表面上像 $O(E)$ 的代码可能变成不停翻旧抽屉。

互动小实验室

运行从散步到欧拉回路.py。直接回车使用“双三角形”预设；程序会：

列出每个点的度数和奇度点；
检查非孤立点连通性；
一步步打印“沿边前进”与“栈顶无边、收进答案”；
最后核对路线是否刚好包含 $E+1$ 个顶点。

试着把一条边删掉，再预测奇度点会怎样变化。不要害怕把图弄坏：程序不会给图记仇。

扩展与联系

有向图把“度数偶偶配对”换成“入度与出度配对”：内部点要求 in = out，两个端点分别允许相差 1。若任务要求访问每个点一次，则它已经是另一个世界的哈密顿问题，不能把今天的度数结论搬过去。

正式课会把“词尾接词首”“给边定向”等题面翻译成边的使用问题；零食课先帮你练出识别信号：题目反复强调“每条关系/道路/相邻窗口恰好一次”时，先想到欧拉，而不是对点做普通 DFS。

总结与自检

为什么两个奇度点只能是端点，而不能是任意中间点？
answer 为什么要反转？
两个不连通的偶度环为什么仍无解？
重边为何迫使我们按边编号标记？

自检答案

中间点的进入和离开必须配对；栈回退先得到终点；一条路线不能跨连通块；两条同端点边是不同工作，不能共用一个布尔标记。

一周预热安排

第 1 天：手画两个三角形，标出“点访问”和“边使用”的不同。
第 2 天：对三张小图数度数，故意加入自环和重边。
第 3 天：在纸上执行一次栈版伪代码。
第 4 天：运行互动程序并改一条边，解释输出变化。
第 5 天：复述两个不变量，再进入正式课。

00-课前零食-从散步到欧拉回路.md 13 KB Түүх Анхны өгөгдөл