引言
在组合数学中，Prüfer 序列 提供了一种将带标号树（labeled tree）与序列一一对应的美妙方法。这一编码由 Heinz Prüfer 于1918年提出，不仅证明了 Cayley 公式（n 个顶点的完全图有 nⁿ⁻² 棵生成树），更为树的随机生成、动态树问题提供了实用工具。本文将用 Java 完整实现 Prüfer 序列的编码与解码算法，并展示其在树计数和随机树生成中的应用。
Cayley 公式与 Prüfer 序列
Cayley 公式：n 个带标号顶点的不同树共有 nⁿ⁻² 棵。
Prüfer 序列：长度为 n-2 的序列，每个元素取值于 [1, n]。关键定理：n 个顶点的带标号树与长度为 n-2 的 Prüfer 序列之间存在双射（一一对应）。
这意味着：
– 每棵树对应唯一的 Prüfer 序列
– 每个序列对应唯一的树
– 因此树的计数 = 序列的计数 = nⁿ⁻²
编码算法：树 → Prüfer 序列
算法步骤：
1. 找到当前树中标号最小的叶子节点（度为1的节点）
2. 记录该叶子的邻居节点标号，加入序列
3. 删除该叶子节点
4. 重复上述步骤，直到树中只剩2个节点
时间复杂度：O(n log n)（使用优先队列），或 O(n)（配合度数数组优化）
import java.util.*;
/**
* Prüfer 序列编码与解码实现
* 用于带标号树的编码、解码、计数与随机生成
*/
public class PruferSequence {
private int n; // 顶点数量
private List<int[]> edges; // 树的边集
public PruferSequence(int n) {
this.n = n;
this.edges = new ArrayList<>();
}
/**
* 添加无向边
*/
public void addEdge(int u, int v) {
edges.add(new int[]{u, v});
}
/**
* 树 → Prüfer 序列编码
* 时间复杂度: O(n log n)
* @return Prüfer 序列（长度为 n-2）
*/
public int[] encode() {
if (n <= 2) {
return new int[0];
}
// 构建邻接表和度数数组
List<Integer>[] adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}
int[] degree = new int[n + 1];
for (int[] e : edges) {
adj[e[0]].add(e[1]);
adj[e[1]].add(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
// 优先队列存储当前所有叶子节点（度为1的节点）
PriorityQueue<Integer> leaves = new PriorityQueue<>();
for (int i = 1; i <= n; i++) {
if (degree[i] == 1) {
leaves.offer(i);
}
}
int[] prufer = new int[n - 2];
for (int i = 0; i < n - 2; i++) {
// 取出标号最小的叶子
int leaf = leaves.poll();
// 找到其唯一邻居
int neighbor = -1;
for (int v : adj[leaf]) {
if (degree[v] > 0) {
neighbor = v;
break;
}
}
prufer[i] = neighbor;
degree[leaf]--;
degree[neighbor]--;
// 若邻居变为叶子，加入队列
if (degree[neighbor] == 1) {
leaves.offer(neighbor);
}
}
return prufer;
}
/**
* Prüfer 序列 → 树解码
* 时间复杂度: O(n log n)
* @param prufer Prüfer 序列
* @return 树的边集
*/
public static List<int[]> decode(int[] prufer, int n) {
List<int[]> resultEdges = new ArrayList<>();
if (n <= 1) return resultEdges;
if (n == 2) {
resultEdges.add(new int[]{1, 2});
return resultEdges;
}
// 统计每个顶点在序列中出现的次数
int[] degree = new int[n + 1];
Arrays.fill(degree, 1); // 每个顶点初始度数为1
for (int v : prufer) {
degree[v]++;
}
// 优先队列存储当前可用的叶子节点
PriorityQueue<Integer> leaves = new PriorityQueue<>();
for (int i = 1; i <= n; i++) {
if (degree[i] == 1) {
leaves.offer(i);
}
}
// 按序列依次连接叶子与序列中的顶点
for (int v : prufer) {
int leaf = leaves.poll();
resultEdges.add(new int[]{leaf, v});
degree[leaf]--;
degree[v]--;
if (degree[v] == 1) {
leaves.offer(v);
}
}
// 最后剩下两个节点，连接它们
int last1 = leaves.poll();
int last2 = leaves.poll();
resultEdges.add(new int[]{last1, last2});
return resultEdges;
}
/**
* 根据Prüfer序列计算每个顶点的度数
* 度数为 1 + 该顶点在序列中出现次数
*/
public static int[] calculateDegrees(int[] prufer, int n) {
int[] degree = new int[n + 1];
Arrays.fill(degree, 1);
for (int v : prufer) {
degree[v]++;
}
return degree;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("Tree edges:\n");
for (int[] e : edges) {
sb.append(" ").append(e[0]).append(" - ").append(e[1]).append("\n");
}
return sb.toString();
}
// ========== 演示与测试 ==========
public static void main(String[] args) {
System.out.println("===== Prüfer 序列编码解码演示 =====\n");
// 示例1: 编码一棵7个节点的树
System.out.println("【示例1】编码一棵7个节点的树");
PruferSequence tree1 = new PruferSequence(7);
tree1.addEdge(1, 4);
tree1.addEdge(2, 4);
tree1.addEdge(3, 4);
tree1.addEdge(4, 5);
tree1.addEdge(5, 6);
tree1.addEdge(6, 7);
System.out.println(tree1);
int[] prufer1 = tree1.encode();
System.out.println("Prüfer 序列: " + Arrays.toString(prufer1));
System.out.println();
// 示例2: 解码回树
System.out.println("【示例2】将上述序列解码回树");
List<int[]> decodedEdges = PruferSequence.decode(prufer1, 7);
System.out.println("解码后的边:");
for (int[] e : decodedEdges) {
System.out.println(" " + e[0] + " - " + e[1]);
}
System.out.println();
// 示例3: 验证 Cayley 公式
System.out.println("【示例3】验证 Cayley 公式");
for (int n = 2; n <= 6; n++) {
long treeCount = cayleyFormula(n);
System.out.println(" n=" + n + " 时，带标号树数量 = " + n + "^" + (n-2) + " = " + treeCount);
}
System.out.println();
// 示例4: 随机树生成
System.out.println("【示例4】随机生成一棵10个节点的树");
List<int[]> randomTree = generateRandomTree(10);
System.out.println("随机树边集:");
for (int[] e : randomTree) {
System.out.println(" " + e[0] + " - " + e[1]);
}
}
/**
* Cayley 公式: n^(n-2)
*/
public static long cayleyFormula(int n) {
if (n <= 1) return 1;
long result = 1;
for (int i = 0; i < n - 2; i++) {
result *= n;
}
return result;
}
/**
* 随机生成一棵 n 个节点的带标号树
* 先生成随机 Prüfer 序列，再解码为树
*/
public static List<int[]> generateRandomTree(int n) {
if (n <= 1) return new ArrayList<>();
if (n == 2) {
List<int[]> edges = new ArrayList<>();
edges.add(new int[]{1, 2});
return edges;
}
Random rand = new Random();
int[] prufer = new int[n - 2];
for (int i = 0; i < n - 2; i++) {
prufer[i] = rand.nextInt(n) + 1; // [1, n]
}
System.out.println(" 生成的随机 Prüfer 序列: " + Arrays.toString(prufer));
return decode(prufer, n);
}
}
线性时间优化版本
上述实现使用优先队列，时间复杂度为 O(n log n)。通过指针扫描可以优化到 O(n)：
/**
* O(n) 编码实现（不使用优先队列）
* 利用指针维护当前最小叶子，配合度数数组快速查找
*/
public int[] encodeLinear() {
if (n <= 2) return new int[0];
List<Integer>[] adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
int[] degree = new int[n + 1];
for (int[] e : edges) {
adj[e[0]].add(e[1]);
adj[e[1]].add(e[0]);
degree[e[0]]++;
degree[e[1]]++;
}
int ptr = 1; // 指针，指向当前最小的候选叶子
while (ptr <= n && degree[ptr] != 1) ptr++;
int[] prufer = new int[n - 2];
int leaf = ptr;
for (int i = 0; i < n - 2; i++) {
int neighbor = -1;
for (int v : adj[leaf]) {
if (degree[v] > 0) {
neighbor = v;
break;
}
}
prufer[i] = neighbor;
degree[leaf]--;
degree[neighbor]--;
if (degree[neighbor] == 1 && neighbor < ptr) {
leaf = neighbor;
} else {
ptr++;
while (ptr <= n && degree[ptr] != 1) ptr++;
leaf = ptr;
}
}
return prufer;
}
扩展应用：统计特定度数序列的树数量
由 Prüfer 序列的性质，度数为 dᵢ 的顶点在序列中恰好出现 dᵢ – 1 次。因此，给定度数序列 (d₁, d₂, …, dₙ)，对应的树数量为多重组合数：
$$\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}$$
/**
* 计算具有指定度数序列的带标号树数量
*/
public static long countTreesWithDegreeSequence(int[] degrees) {
int n = degrees.length;
int sum = 0;
for (int d : degrees) sum += d;
// 验证度数和是否为 2(n-1)
if (sum != 2 * (n - 1)) return 0;
long numerator = factorial(n - 2);
long denominator = 1;
for (int d : degrees) {
denominator *= factorial(d - 1);
}
return numerator / denominator;
}
private static long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) result *= i;
return result;
}
总结
Prüfer 序列揭示了树与序列之间深刻而简洁的对应关系。通过这一编码，我们不仅优雅地证明了 Cayley 公式，还获得了线性时间生成随机树、统计特定结构树数量等实用工具。掌握 Prüfer 序列，是理解组合数学中”编码-解码”思想的重要一步，也是解决图论计数问题的有力武器。
