引入
首先这是个啥玩意呢？Prüfer 序列可以将带标号的 \(n\) 个节点的树用一个序列表示。可以理解为完全图生成树与Prüfer 序列构建了双射。
建立
每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 \(n-2\) 次后就只剩下两个结点，算法结束。
首先这是个啥玩意呢？Prüfer 序列可以将带标号的 \(n\) 个节点的树用一个序列表示。可以理解为完全图生成树与Prüfer 序列构建了双射。
每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 \(n-2\) 次后就只剩下两个结点，算法结束。