普通图 vs 树

概述

普通图（General Graph）是图的一般形式，可能包含环和多重连通路径。树（Tree）是一种特殊的图——连通且无环的图，具有 $|E|=|V|-1$ 的精确边数关系。树是图论中最重要的结构之一，既是极小连通图（删除任意边就不连通），又是极大无环图（添加任意边就产生环）。

定义

普通图

图 $G=(V,E)$ 由顶点集 $V$ 和边集 $E$ 组成，对边的数量和结构没有特殊限制。普通图可能包含环（cycle）、重边、割点等复杂结构，边数范围从 $0$ 到 $\left(\genfrac{}{}{0ex}{}{|V|}{2}\right)$（简单图）。连通图是普通图的子类。

树

树是连通且无环的无向图。以下四个命题等价（$n$ 个顶点的简单图）：(1) 连通且无环；(2) 连通且有 $n-1$ 条边；(3) 无环且有 $n-1$ 条边；(4) 任意两点间存在唯一路径。Cayley 公式：$n$ 个标记顶点有 $n^{n-2}$ 棵不同的树。

对比维度

维度	普通图	树
环	可能包含环	无环
连通性	可能不连通	必须连通
边数	$0\le \Vert E\Vert \le \left(\genfrac{}{}{0ex}{}{\Vert V\Vert }{2}\right)$	恰好 $\Vert E\Vert =\Vert V\Vert -1$
路径唯一性	两点间可能有多条路径	任意两点间恰好一条路径
极值性质	无	极小连通图 + 极大无环图
生成结构	无	连通图有生成树
遍历	BFS/DFS	前序/中序/后序遍历
Cayley 公式	不适用	$n$ 个标记顶点有 $n^{n-2}$ 棵不同的树
删除边的影响	可能不影响连通性	删除任意边使图不连通
添加边的影响	可能不产生环	添加任意边产生唯一环

关键区别

• 树是无环的连通图，普通图可以含环——这是最本质的区别
• 树的边数被精确确定为 $|V|-1$，普通图的边数在一个很大的范围内变化
• 树中任意两点间只有唯一路径，普通图中两点间可能存在多条路径
• 删除树的任意一条边会使图不连通，删除普通图的边不一定影响连通性
• 每个连通图都包含生成树（包含所有顶点的树子图），生成树有 $n-1$ 条边
• 树是最小连通的图结构，任何更少的边都会使图不连通

联系

• 树是普通图的特例，所有树的性质都是图的性质的推论
• 每个连通图都有生成树，生成树是原图的极小连通子图
• 最小生成树（MST）算法（Prim/Kruskal）在加权连通图上寻找总权重最小的生成树
• BFS 和 DFS 遍历连通图时，遍历过程中经过的边构成一棵生成树（BFS 树 / DFS 树）
• 树在算法中有广泛应用：二叉搜索树、堆、决策树、语法树等

参见

• 树图 — 树的完整概念卡片
• 连通图 — 连通性是树的定义基础