1. 引言
在本文中，我们将介绍加权图（Weighted Graph）与非加权图（Unweighted Graph），并解释它们之间的区别。同时，我们会展示在程序中如何表示这两种图结构。
2. 什么是图？
图（Graph）是一组相互连接的对象的集合。这些对象可以是数学概念，也可以是现实世界中的实体或现象。例如，一组有亲属关系的人构成一个图；城市之间通过道路连接也构成一个图。
通常，我们将图中的对象称为节点（Node）或顶点（Vertex），连接这些对象的线称为边（Edge）或弧（Arc）。例如，城市与道路之间的图可以这样可视化：
每个节点代表一个城市，每条边代表两个城市之间的一条道路。
3. 非加权图
如果我们只关心两个节点之间是否有连接，而不关心连接的其他属性，这样的图称为非加权图。对于两个直接相连的节点，我们称它们为相邻节点（Adjacent）或邻居（Neighbor）。
3.1. 邻接矩阵（Adjacency Matrix）
非加权图可以用邻接矩阵表示。这是一个 n x n 的矩阵（n 为节点数量），其中的元素为 0 或 1。如果 a[i][j] == 1，表示第 i 个节点和第 j 个节点之间有边；如果为 0，则没有。
以下是非加权图的邻接矩阵示例：
$$ \bordermatrix{ & A & B & C & D & E \cr A & 0 & 1 & 0 & 0 & 0 \cr B & 1 & 0 & 1 & 0 & 1 \cr C & 0 & 1 & 0 & 1 & 1 \cr D & 0 & 0 & 1 & 0 & 0 \cr E & 0 & 1 & 1 & 0 & 0 } $$
该矩阵是对称的，适用于无向图（Undirected Graph）。
使用邻接矩阵有两个前提：
✅ 能将节点映射为唯一的整数编号
✅ 节点数量足够小，使得内存可以容纳 n x n 矩阵
如果这些条件不满足，或者图是稀疏的（Sparse），我们通常使用邻接表（Adjacency List）。
3.2. 邻接表（Adjacency List）
邻接表为每个节点维护一个链表，记录它的所有邻居节点：
邻接表的优点是存储空间不连续，适合稀疏图。但缺点是查询两个节点是否相连的时间复杂度不再是 O(1)，最坏情况下可能需要遍历整个链表。
例如，如果节点 i 几乎连接了所有节点，但唯独没有连接 j，那么我们最多需要检查 n-2 个元素才能确定它们不相邻。
4. 加权图
非加权图只能告诉我们两个节点是否相连，适用于以下问题：
- 从节点
u到v是否存在路径？ - 从
u出发可以到达哪些节点？ u和v之间的最短路径包含多少个节点？
但在许多实际应用中，边是有数值属性的。例如，寻找城市之间的最短路径时，必须考虑道路长度和交通密度。我们为每条边 e 分配一个实数 w(e)，称为权重（Weight）。这种图称为加权图（Weighted Graph）。
下图是加权图的示例，边上的数字代表道路长度：
权重可以表示各种实际意义：长度、密度、时间、成本、概率等。
4.1. 加权图的表示方式
加权图的表示方式是对非加权图的扩展：
- 权重矩阵（Weight Matrix）：是一个
n x n的实数矩阵，其中w[i][j]表示节点i与j之间的边的权重。通常，0 表示没有边，正数表示存在边。如果允许负权边，需定义一个特殊符号（如INF）表示无边。
权重矩阵示例如下：
$$ \bordermatrix{ & A & B & C & D & E \cr A & 0 & 1 & 0 & 0 & 0 \cr B & 1 & 0 & 4 & 0 & 3 \cr C & 0 & 4 & 0 & 3 & 2 \cr D & 0 & 0 & 3 & 0 & 0 \cr E & 0 & 3 & 3 & 0 & 0 } $$
- 邻接表：在链表中保存邻居节点的同时，也保存对应的边的权重：
4.2. 非加权图作为加权图的特例
非加权图也可以看作是一种特殊的加权图，其权重函数定义如下：
$$ w(u, v) = \begin{cases} 0, & u \text{ 和 } v \text{ 不相连} \ 1, & u \text{ 和 } v \text{ 相连} \end{cases} $$
此外，如果所有边的权重相同，或者路径成本只取决于节点数量，我们可以使用非加权图算法，稍后再计算权重。
4.3. 显式图与隐式图
加权图和非加权图都可以是显式图（Explicit Graph）或隐式图（Implicit Graph）。
- 显式图：节点和边可以在程序运行前全部枚举并存储在内存中。例如，城市与道路图。
- 隐式图：图结构非常庞大或复杂，无法提前完整构建。我们通过某种函数动态生成图的节点和边。例如，在 AI 搜索问题中，每个候选解是一个节点，搜索时动态生成邻居节点。
⚠️ 隐式图的概念类似于数据库中的懒加载（Lazy Loading），而显式图则类似于急加载（Eager Loading）。
5. 总结
- 非加权图适用于只需知道节点之间是否连接的场景。
- 加权图适用于边具有数值属性的情况，如成本、长度等。
- 图的表示方式包括邻接矩阵和邻接表，各有优劣。
- 加权图可以看作是非加权图的扩展。
- 图可以是显式的（完整构建）或隐式的（动态生成）。
✅ 在选择图结构和表示方式时，应根据具体应用场景进行权衡。