1. 概述
图的密度是衡量图中边数量相对于顶点数量多少的一个指标。根据密度的不同，图可以分为两类：稀疏图（Sparse Graph）和稠密图（Dense Graph）。
本文将从图的“大小”（Size）和“阶数”（Order）出发，推导出图密度的定义，并据此区分稀疏图与稠密图。最后，我们还将讨论图密度在内存存储上的意义。
2. 图的密度
2.1. 图密度的直观理解
图的密度可以理解为图中边的数量相对于顶点数量的“密集程度”。我们可以用一个包含 5 个顶点、4 条边的无向图来直观理解：
在这个图中，很多顶点之间并没有边相连，比如 (2, 5) 或 (3, 4)。如果我们不增加顶点数量，而是增加边的数量，图就会变得“更稠密”：
极端情况下，图可能是完全稠密的：
也可能是完全稀疏的：
因此，我们可以得出一个初步结论：图的密度是一个衡量图“边的密集程度”的指标，与边数和顶点数之间的关系有关。
2.2. 图的大小与阶数
- 图的大小（Size）指的是图中边的数量，记作
|E|。 - 图的阶数（Order）指的是图中顶点的数量，记作
|V|。
对于一个无边图（空图），其大小为 0，阶数为正整数。例如：
两个空图即使阶数不同，它们的密度也应为 0。
2.3. 最大边数
图的密度还与图中可能存在的最大边数有关。对于一个无向图，最大边数为：
$$ \text{Max}_U(V) = \binom{|V|}{2} = \frac{|V| \cdot (|V| - 1)}{2} $$
对于有向图，由于每条边都可以有两个方向，因此最大边数是无向图的两倍：
$$ \text{Max}_D(V) = |V| \cdot (|V| - 1) $$
这些公式帮助我们理解图的“理论最大连接数”，从而定义图的密度。
3. 图密度的正式定义
3.1. 密度公式
对于无向图 $ G(V, E) $，其密度 $ D_U(V, E) $ 定义为：
$$ D_U(V, E) = \frac{2 \cdot |E|}{|V| \cdot (|V| - 1)} $$
对于有向图 $ G(V, E) $，其密度 $ D_D(V, E) $ 定义为：
$$ D_D(V, E) = \frac{|E|}{|V| \cdot (|V| - 1)} $$
密度值范围在 [0, 1] 之间：
- $ D = 0 $：空图（完全稀疏）
- $ D = 1 $：完全图（完全稠密）
3.2. 稀疏图 vs. 稠密图
根据密度值，我们可以将图分为两类：
| 类型 | 密度范围 | 说明 |
|---|---|---|
| 稀疏图 | $ 0 \leq D < 0.5 $ | 边数较少 |
| 稠密图 | $ 0.5 < D \leq 1 $ | 边数较多 |
密度为 0.5 的图可视为“中间态”，通常不归类为稀疏或稠密。
一些常见图的密度特性：
- 阶数为 1 的图密度无定义（既可视为最稀疏也可视为最稠密）
- 所有空图密度为 0，属于稀疏图
- 所有完全图密度为 1，属于稠密图
- 无向可追踪图（Traceable Graph）密度至少为 $ \frac{2}{|V|} $，当 $ |V| < 4 $ 时必为稠密
- 有向可追踪图不一定稠密
- 锦标赛图（Tournament）密度恒为 0.5，与阶数无关
3.3. 示例计算
以一个 5 个顶点、4 条边的无向图为例：
$$ V = {1, 2, 3, 4, 5}, \quad E = {(1,2), (1,3), (1,4), (1,5)} $$
- 阶数：$ |V| = 5 $
- 边数：$ |E| = 4 $
- 最大边数：$ \frac{5 \cdot 4}{2} = 10 $
- 密度：$ D = \frac{4}{10} = 0.4 $
由于 $ D < 0.5 $，该图为稀疏图。
若增加 2 条边（如 (2,3) 和 (3,4)），则：
- 边数：$ |E| = 6 $
- 密度：$ D = \frac{6}{10} = 0.6 $
此时 $ D > 0.5 $，该图为稠密图。
4. 图密度与内存存储
图在内存中的表示方式通常有两种：
- 边列表（Edge List）：适用于稀疏图
- 邻接矩阵（Adjacency Matrix）：适用于稠密图
存储方式选择建议：
| 图类型 | 推荐存储方式 | 说明 |
|---|---|---|
| 稀疏图 | 边列表 | 节省空间，访问效率适中 |
| 稠密图 | 邻接矩阵 | 支持快速查找，空间开销较大 |
✅ 稀疏图使用边列表更节省内存
❌ 稠密图使用边列表可能导致频繁查找，效率低下
⚠️ 错误选择存储结构可能影响性能，甚至导致内存溢出
5. 总结
- 图的密度是衡量图中边数量相对于顶点数量的一个指标
- 密度范围为 [0, 1]，0 表示空图，1 表示完全图
- 稀疏图密度 < 0.5，稠密图密度 > 0.5
- 图的存储方式应根据其密度选择：稀疏图用边列表，稠密图用邻接矩阵
在实际开发中，尤其是图结构较大时，合理选择存储结构对性能和内存管理至关重要。