Prüfer序列

What · 是什么

Prüfer 序列把「n 个带标号节点的树」与「长度为 n-2、每个元素在 [1,n] 的整数序列」建立一一对应（双射）。构造（树→序列）：重复 n-2 次——选出当前编号最小的叶节点删去，把与它相连的节点编号写入序列。重建（序列→树）：由序列统计各点度数（每个数出现次数+1），重复从叶集取最小叶与序列当前位置连边并更新度数，最后剩余两点连边。序列中节点 v 的出现次数恰为 deg(v)-1。由此立得 Cayley 公式：n 个节点的完全图生成树数为 n^(n-2)，并可推广到给定度数序列的树计数 n-2 项排列数，以及「把 k 个连通块加边连成树」的方案数 n^(k-2)·∏s_i。

Why · 为什么

How · 实现

伪代码

encode(tree):  # 树→序列, O(n log n)
  deg = 各点度数; leaf = 度1的点集(堆/最小优先)
  for i in 1..n-2:
    x = leaf.pop_min()
    y = x 的未删邻居
    code[i] = y
    deg[y] -= 1
    if deg[y] == 1: leaf.push(y)
decode(code):  # 序列→树, O(n log n)
  n = len(code)+2; deg[i]=1+code中出现次数
  leaf = 度1点集
  for y in code:
    x = leaf.pop_min(); 连边(x,y); deg[x]-=1; deg[y]-=1
    if deg[y]==1: leaf.push(y)
  最后连剩余两点

Python 实现

import heapq


def pruefer_encode(n, edges):
    adj = [[] for _ in range(n + 1)]
    deg = [0] * (n + 1)
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
        deg[a] += 1
        deg[b] += 1
    removed = [False] * (n + 1)
    leaves = [i for i in range(1, n + 1) if deg[i] == 1]
    heapq.heapify(leaves)
    code = []
    for _ in range(n - 2):
        x = heapq.heappop(leaves)
        removed[x] = True
        y = next(v for v in adj[x] if not removed[v])
        code.append(y)
        deg[y] -= 1
        if deg[y] == 1:
            heapq.heappush(leaves, y)
    return code


def pruefer_decode(code):
    n = len(code) + 2
    deg = [1] * (n + 1)
    for x in code:
        deg[x] += 1
    leaves = [i for i in range(1, n + 1) if deg[i] == 1]
    heapq.heapify(leaves)
    edges = []
    for y in code:
        x = heapq.heappop(leaves)
        edges.append((x, y))
        deg[x] -= 1
        deg[y] -= 1
        if deg[y] == 1:
            heapq.heappush(leaves, y)
    a, b = heapq.heappop(leaves), heapq.heappop(leaves)
    edges.append((a, b))
    return edges


def main():
    n = 7
    edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]
    code = pruefer_encode(n, edges)
    print("prufer code =", code)
    assert sorted(code) == sorted([2, 2, 1, 3, 3]), code
    back = pruefer_decode(code)
    # 解码得到的树应仍是一棵连通且边集等价（同构意义上）的树
    assert len(back) == n - 1
    adj = [[] for _ in range(n + 1)]
    for a, b in back:
        adj[a].append(b)
        adj[b].append(a)
    seen = [False] * (n + 1)
    stack = [1]
    seen[1] = True
    cnt = 0
    while stack:
        u = stack.pop()
        cnt += 1
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                stack.append(v)
    assert cnt == n, "not a tree"
    # Cayley: n=5 时生成树数应为 5^(5-2)=125，任意一棵树编码应长 3 且解码回 5 点
    code5 = pruefer_encode(5, [(1, 2), (2, 3), (3, 4), (4, 5)])
    assert len(code5) == 3
    print("OK")


if __name__ == "__main__":
    main()

易错点

• n=1 无定义，特判输出（通常 0 或按题意）
• 删叶时找「未删邻居」：需在删除时标记 removed，否则可能指向已删点
• 解码时最后剩余两个点都要度数为 1 且直接连边，别漏最后一对
• 统计度数：初值 1（每个点至少度为 1），序列中每个出现 +1
• Cayley 公式在模运算下注意取模；度数序列计数分母是阶乘，模质数下用逆元
• 堆元素重复：度数减到 1 后若再入堆会产生重复节点，需先判断是否已删

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/prufer/
• oiwiki_raw✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/prufer.md
• CP-Algorithms✓ https://cp-algorithms.com/graph/pruefer_code.html