图

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

1. 图的本质

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

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

典型问题本质：

2. 图的核心结构要素

要素 抽象含义
有向 / 无向 关系是否具有方向性（依赖、因果）
有权 / 无权 关系是否存在成本 / 距离
度 节点约束强度 / 影响范围
环 是否存在循环依赖
连通性 状态空间是否割裂

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

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

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

1. 邻接矩阵（Adjacency Matrix）

模型特征：

适用场景：

代价：

2. 邻接表（Adjacency List）

模型特征：

适用场景：

代价：

3. 边表（Edge List）

模型特征：

典型用途：

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

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

1. 深度优先搜索（DFS）

核心思想：

本质能力：

典型派生问题：

复杂度：O(V + E)

2. 广度优先搜索（BFS）

核心思想：

本质能力：

复杂度：O(V + E)

3. DFS vs BFS 的本质区别

维度 DFS BFS
搜索策略 路径优先 距离优先
适用问题 结构性质 最短路径
内存模型 递归栈 队列

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

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

1. 连通性

2. 有向图与可达性

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

3. 环与依赖关系

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

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

1. 最小生成树（MST）

问题本质：

适用前提：

Prim 算法

Kruskal 算法

2. 最短路径问题

场景 算法
无权图 BFS
正权单源 Dijkstra
含负权 Bellman-Ford
全源 Floyd

Dijkstra 算法

核心约束：

本质原因：

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

核心思想：

代价函数：

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

关键前提：

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

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

七、总结：稳定认知框架

关联内容（自动生成）