图

• 图是什么
• 为什么问题可以抽象为图
• 不同图结构如何决定算法选择

一、图的第一性原理（What is a Graph）

1. 图的本质

图（Graph）是一种用于表达“实体之间约束关系”的抽象结构。

• 顶点（Vertex）：实体 / 状态 / 节点
• 边（Edge）：关系 / 约束 / 转移可能性

当系统中的“关系”比“实体本身”更重要时，图是最自然的建模方式。

典型问题本质：

• 路径问题 → 状态转移成本
• 依赖问题 → 因果顺序
• 连通问题 → 可达性

2. 图的核心结构要素

这些结构性质直接决定可用算法集合。

二、图的表示模型（How to Represent）

表示方式不是实现细节，而是空间—时间权衡模型。

1. 邻接矩阵（Adjacency Matrix）

模型特征：

• 用二维矩阵表达“任意两点是否存在关系”

适用场景：

• 稠密图
• 高频边查询
• 图运算可转化为矩阵运算

代价：

• 空间复杂度 O(V²)

2. 邻接表（Adjacency List）

模型特征：

• 每个节点仅维护自身的出边集合

适用场景：

• 稀疏图
• 遍历型算法（DFS / BFS）

代价：

• 边查询效率低于矩阵
• 非连续存储，缓存友好性较差

3. 边表（Edge List）

模型特征：

• 仅关注“关系本身”，忽略节点结构

典型用途：

• 最小生成树（Kruskal）
• 离线图算法

三、图的遍历范式（How to Explore）

遍历不是目的，而是状态空间探索策略。

1. 深度优先搜索（DFS）

核心思想：

• 沿一条路径探索到极限，再回溯

本质能力：

• 结构发现
• 组件划分
• 环检测

典型派生问题：

• 连通分量
• 强连通分量
• 拓扑排序（DFS 版本）

复杂度：O(V + E)

2. 广度优先搜索（BFS）

核心思想：

• 按“距离层级”逐层扩展

本质能力：

• 最短路径（无权）
• 最小跳数

复杂度：O(V + E)

3. DFS vs BFS 的本质区别

DFS / BFS 是基础遍历器，而非最终算法。

四、图的结构性质问题（What the Graph Is Like）

1. 连通性

• 无向图中：极大连通子图称为连通分量
• 判断方式：DFS / BFS

2. 有向图与可达性

• 可达性：是否存在从 u 到 v 的路径
• 强连通：u ⇄ v 互相可达

强连通分量本质是有向图的结构分解问题。

3. 环与依赖关系

• 有向无环图（DAG）代表“可线性化依赖”
• 存在环 → 依赖无法排序

五、图上的优化问题（How to Optimize）

优化问题 = 在约束关系下寻找最优路径 / 子结构。

1. 最小生成树（MST）

问题本质：

• 在保持连通的前提下，最小化总代价

适用前提：

• 连通
• 无向
• 有权

Prim 算法

• 思想：从“点”扩展
• 适合稠密图

Kruskal 算法

• 思想：从“边”筛选
• 依赖并查集判环
• 适合稀疏图

2. 最短路径问题

Dijkstra 算法

核心约束：

• 边权非负

本质原因：

• 贪心选择一旦确认不可回退

3. A* 算法（启发式搜索）

核心思想：

• 在 Dijkstra 的基础上引入启发函数 h(n)

代价函数：

f(n) = g(n) + h(n)

关键前提：

• h(n) 不得高估真实代价（可采纳性）

六、算法选型决策视图（How to Choose）

是否有权？
 ├─ 否 → BFS
 └─ 是
     ├─ 是否有负权？
     │   ├─ 是 → Bellman-Ford
     │   └─ 否 → Dijkstra / A*

七、总结：稳定认知框架

• 图不是算法集合，而是关系建模工具
• 遍历算法是"探索器"，优化算法是"决策器"
• 结构性质 → 决定算法边界