Prufer序列

· · 个人记录

Prufer序列是用于表示无根树的，与每棵树有唯一对应关系的序列。

无根树->Prufer序列

对于一棵树，每次选出一个叶子节点（度数为1），将其父节点加入Prufer序列，再将该节点删除，直到整棵树剩下两个节点。

如：对于一棵树

构建过程如下：

选取的叶子节点 对应的父节点
1 5
2 5
4 3

其Prufer序列为5,5,3

Prufer序列->无根树

依次选择序列中最前的节点，将其和点集中 不在序列中的 标号最小的节点连接，再把序列中的节点移出序列，点集中的节点移出点集，最后将点集中剩下的两个节点连接。

如：序列5,5,3(下表从1开始），其对应的树构建过程如下 从点集选取 从序列选取 点集中剩余 序列中剩余
1、2、4 5、5、3
1 5 2、4 5、3
2 5 4、5 3
4 3 3、5

最后将3、5连接，得到原树。

应用

用来枚举给定点集的生成树，对于有限制条件的生成树（如限制每个节点的度），考虑限制节点在Prufer序列中出现次数后DP。