图解实验室 / 进阶 · 18 分钟 · 算法
Prüfer 编码：删去最小叶子，如何还原一棵树？
左边删一条边，右边添回同一条边。记下的是邻居，不是被删的叶子；最后两个顶点还要单独连接。
已完成 0/3 次边操作 · 标签固定，圆周位置不是叶子的优先顺序。
① 编码：剩余树
② 解码：已复原边
虚线淡边仅供对照，表示当前图中不存在的边；粗实线是下一条处理边。方位不参与算法。
步骤 0/3。下一步：选当前最小叶子 0，记录它的邻居 1；右侧用同一项复原这条边。 已复原边：无。
| 顶点 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 剩余次数 | 0 | 1 | 1 | 0 |
| 剩余度数 | 1 | 2 | 2 | 1 |
u = smallestActiveVertexWithZeroRemainingCount();
v = P[i]; // 先选叶，再消费当前项
addEdge(u, v);
active[u] = false; remainingCount[v]--; ← / → 单步，Home / End 首尾。无自动播放；减少动画偏好关闭边与节点过渡。输入仅在本页内使用。
自测：n=2，输入为空，为什么还有一步？
编码记录零个邻居，但树仍有 n−1=1 条边。解码必须把最后两个顶点 0、1 连接。
看完图，带走这些结论
Prüfer 编码每次删去标号最小的叶子，记录它唯一的邻居，共记录 n−2 项。解码时，选尚未处理且未在剩余序列出现的最小标号，把它与当前项相连。消费一项后继续，最后连接剩下两点。
适用条件与边界
讨论标号为 0..n−1 的简单无向树，n≥2。交互与本页模型限定 2≤n≤8；输入序列长度恰为 n−2，每项是范围内整数，允许重复。图中的圆周位置只为稳定布局，边的交叉不是额外顶点。n=1 不在此演示范围内。
始终保持的规律
处理 k 项后，尚未处理顶点的剩余树度数 = 剩余序列中该标号的出现次数 + 1；两边每步使用同一条边，但左图删边、右图添边。
逐步例子
- 原创路径 0—1—2—3：叶子先有 0、3，删 0 记邻居 1；再删 1 记 2，得到 [1,2]，最后边为 2—3。
- 反向读 [1,2]：初始缺席标号有 0、3，取最小的 0 接到 1；剩 [2]，从活动顶点中取最小缺席标号 1 接到 2；最后接 2—3。
- 原创五点星形中心为 0：依次删叶 1、2、3，编码为 [0,0,0]，最后剩 0—4。重复不是错误，反而揭示中心的高连接度。
- 一个活动顶点总会保留一条“最后离开”的边。其余每条相邻边先被叶子删掉时，都会记录它一次，所以剩余度数等于剩余出现次数加一。这个度数属于剩余树，不是右侧已经复原部分的度数。
- 每次选叶时，剩余序列还包含当前项。选好以后才消费当前项、移除叶子；反过来可能把当前邻居错当成叶子。已处理顶点即使计数为零也不可再次选择。
- n=2 的编码是空序列，但原树仍有一条边；演示单列“连接最后一条边”操作，不把空序列当作没有树。
- 每个合法序列都能复原一棵树，再编码得到原序列。因而 n≥2 时，有标号树数量为 n^(n−2)。例如四点共有 4²=16 棵有标号树，并不是 16 种忽略标号的形状。
扫描实现与教学轨迹成本
本页使用扫描最小叶子的朴素方法，不是堆或指针优化：单次编码、解码为 O(n²) 时间。解码额外空间 O(n)，矩阵编码空间 O(n²)。教学帧保存每步的边与顶点副本，当前生成方式至多 O(n³) 时间、O(n²) 存储，不能把整套动画轨迹称作 O(n) 空间。交互上限 8 只为可读性，不是 Prüfer 定理的上限。
常见误区
- 记录被删的叶子，而非它的邻居
- 按画面最左点选叶，而不是按标号最小
- 序列用完就停止，漏掉最后一条边
- 把剩余度数误当作已复原图的度数
- 删除当前项之后才选择叶子，或重新选择已处理顶点
- 把有标号树数量误认为不区分标号的树形数量
自测与答案
n=5 的序列 [0,0,0] 复原哪些边？为什么不是三个顶点？
标号集合是 0..4。依次得到 1—0、2—0、3—0，再补最后的 0—4；序列有 n−2=3 项，不代表树只有 3 个顶点。