树与森林的性质

可视化演示

树是无环连通图，森林是无环图。本文详解树的多种等价定义、生成树与最小生成树的Kruskal与Prim算法、树的... 切换模式查看不同维度。

树的定义：无环连通

老周在岛上规划道路，要求很简单：每个村庄都能到达其他村庄，但不要出现绕圈的死循环。于是他只修“刚好够用”的路——这就是树的直觉。数学上，树是一个连通且无环的无向图。所谓连通，就是任意两个村庄之间都有路可走；所谓无环，就是你从任意一个村子出发，永远不可能沿着一条不重复的小路绕回自己。

把村庄看成顶点、小路看成边，树有一个极漂亮的性质：若树有 n 个顶点，则一定有 n-1 条边。这个性质反过来也成立：一个连通图只要边数等于顶点数减一，就必然是树。更进一步，在树中，任意两个顶点之间的路径存在且唯一。多修一条会成环，少修一条会断掉，不多不少正好 n-1。

这些等价定义就像老周的修路原则：只要满足“连通且无环”，无论先看边数、路径还是连通性，结论都是同一张树状路网。掌握了树的等价定义，后面所有树相关的算法都有了判断的依据。

森林结构：无环图与连通分量

老周管辖的不只一座岛。群岛之间没有跨海大桥，每座岛内部各有自己的树状路网。这些互不相连的树放在一起，就是森林。数学上，森林是一个无环的图，它的每个连通分量都是一棵树。换句话说，森林就是若干棵树的并集。

因为每座岛内部都是一棵树，岛内边数等于该岛顶点数减一。把所有岛加在一起，总边数就等于总顶点数减去连通分量数。假设一个森林有 n 个顶点、c 个连通分量，那么边数 m 满足：

森林的结构让老周意识到：只要把每个岛内部修成树，整个群岛就是无环的。反过来，如果一张图没有环，但分成好几个互不相连的部分，它仍然叫做森林。判断森林时，我们既要看“有没有环”，也要数“有几个连通块”。

生成树与最小生成树

老周的岛上原有不少旧路，其中有环路，也有多余的歧路。他想在保留全部村庄连通的前提下，删掉一些路，使得最终道路网络是一棵树。这种包含原图所有顶点、又恰好是无环连通子图的树，就叫原图的生成树。一个有 n 个顶点的连通图，任取一条生成树，边数都是 n-1。

如果每条路还标了造价，问题就变成：在所有生成树中，选一棵总造价最小的树。这就是最小生成树（MST）。它可以写成：

求最小生成树有两大经典算法。Kruskal 算法像老周“先修便宜路”：把所有边按造价从低到高排序，每次选一条不会成环的最便宜边加入；Prim 算法则像“从村口向外扩散”：从任意一个村庄出发，每次选择连接已修路网和未修路网的最便宜边。两条路殊途同归，都能得到总造价最小的最简路网。

Cayley公式：标号树计数

老周在整理图纸时发现：同样 4 个村庄，可以画出不止一种最简路网。为了统计到底有多少种不同方案，他给每个村庄编了号。我们把顶点编号过的树称为带标号树，编号不同就算不同的树。德国数学家 Cayley 给出了一个惊人的公式：n 个带标号顶点上共有 n^(n-2) 棵不同的树。

Cayley 公式让人惊讶：看似结构复杂的树，数量只由一个简单的幂函数决定。它一方面说明了带标号树比我们想象中更“规整”，另一方面也为随机生成树提供了理论支撑——只要随机生成一个 n-2 长度的序列，就能等概率对应一棵标号树。

Prufer序列：树的编码

图纸太多，老周想找一个更省空间的存档方式。德国数学家 Prufer 发现：任意一棵 n 个带标号顶点的树，都可以唯一编码成一个长度为 n-2 的序列，序列里的每个数字都是 1 到 n 之间的顶点编号。反过来，任意一个这样的序列也都能唯一还原成一棵树。这种编码就叫 Prufer 序列。

Prufer 序列最漂亮的应用是推导度数：一个顶点在序列中出现的次数，加上 1，就是它在树中的度数。

从编码到解码，Prufer 序列给出了树与序列之间的一一对应。老周不再需要保存厚厚一叠图纸，只需记下一串数字，随时能重建整个路网。这既是组合计数的钥匙，也是图数据压缩与随机树生成的利器。

二叉树与有序树性质

后来岛上立了新规定：每个路口最多分出两条岔路，并且区分左支路和右支路。这种每个节点最多两个孩子的有序树，就是二叉树。二叉树在计算机里地位极高，因为它的层级结构可以直接映射到数组、栈和搜索逻辑。

二叉树有几个关键计数性质。如果把根节点看作第 0 层，那么第 i 层最多有 2^i 个节点；一棵高度为 h 的二叉树，最多能容纳：

还有一种特殊的满二叉树：每个内部节点都恰好有两个孩子。满二叉树中，叶子节点数 L 总比内部节点数 I 多 1。这就像家族谱系中，所有“分叉”的祖辈人数总和，总比最底层的“叶子”后辈人数少一个。

二叉树不是老周路网的全部，但它是有序树中最重要的一种特例。通过左孩子右兄弟等方式，任何有序森林都可以转换成二叉树，这也让树结构在计算机中有了统一、高效的存储方式。

AI 应用场景

Python 演示

class DSU:    def __init__(self, n):        self.parent = list(range(n))        self.rank = [0] * n     def find(self, x):        while self.parent[x] != x:            self.parent[x] = self.parent[self.parent[x]]            x = self.parent[x]        return x     def union(self, a, b):        ra = self.find(a)        rb = self.find(b)        if ra == rb:            return False        if self.rank[ra] < self.rank[rb]:            ra, rb = rb, ra        self.parent[rb] = ra        if self.rank[ra] == self.rank[rb]:            self.rank[ra] += 1        return True  def kruskal(n, edges):    edges = sorted(edges, key=lambda x: x[2])    dsu = DSU(n)    mst = []    total = 0    for u, v, w in edges:        if dsu.union(u, v):            mst.append((u, v, w))            total += w    return mst, total  if __name__ == "__main__":    edges = [        (0, 1, 5), (0, 2, 3), (1, 2, 1),        (1, 3, 2), (2, 3, 4), (3, 4, 4), (2, 4, 6)    ]    mst, total = kruskal(5, edges)    print("MST edges:", mst)    print("Total weight:", total)

1. class DSU:并查集，用来快速判断两条路是否已经连通，避免成环。
2. def find(self, x):查找顶点所在连通块，路径压缩让后续查询更快。
3. def union(self, a, b):尝试合并两个连通块，合并成功说明这条边不会成环。
4. edges = sorted(edges, key=lambda x: x[2])把全部边按边权从小到大排序，对应“先修便宜路”。
5. for u, v, w in edges:从最便宜到最贵逐条尝试。
6. if dsu.union(u, v):只有加入后仍然无环，才把它选进最小生成树。

常见误区

面试题