图

一、图的第一性原理（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 的本质区别

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

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*

七、总结：稳定认知框架

关联内容（自动生成）