图Graph

由顶点集合和边集合组成，表示对象之间的连接关系。

核心约束: 每条边的端点属于顶点集合；方向、权重、自环和重边的约定需一致。
适用问题: 计算依赖、通信拓扑、状态关系。
边界与取舍: 图的存储表示与在图上运行的遍历、路径算法应分别选择。

有向图示例：A 连向 B、C，B、C 连向 D。此例是 DAG；一般图可以有环，也可以是无向图。

常见操作#

V 为顶点数，E 为边数，deg(v) 为顶点 v 的度。

操作	时间复杂度	条件与说明
判断两点之间是否有边	邻接矩阵 $O(1)$ ；邻接表 $O(\deg(v))$	邻接表按线性列表保存邻居；若用哈希邻居集合，成本不同。
枚举一个顶点的邻居	邻接表 $O(\deg(v))$ ；矩阵 $O(V)$	矩阵需扫描一行，邻接表只访问已存在的邻接项。
插入一条边	矩阵 $O(1)$ ；列表尾插摊还 $O(1)$	顶点已存在；列表不额外检查重复边。
遍历整张图	邻接表 $O(V+E)$ ；矩阵 $O(V^{2})$	可按 BFS 或 DFS 访问；非连通图需从未访问顶点继续。

时间与空间#

时间复杂度: 取决于邻接表示和所需操作
存储空间: 邻接表 $O(V+E)$ ；邻接矩阵 $O(V^{2})$

图是关系模型，具体性能来自表示。无向图邻接表通常把每条边保存两次，不改变渐进界。

工程中的应用#

6 个案例 · 附源码

Faiss·HNSW 索引v1.9.0

用分层近邻图检索相似向量

HNSW 从稀疏上层快速定位区域，再在底层扩大候选搜索。

HNSW 近邻检索图 HNSW 图索引邻接表

附源码片段 · 检索与计算

PyTorch·FX Graphv2.5.1

FX：按逆拓扑顺序删除无用计算

借助计算依赖图与使用者计数，清理既不影响输出也无副作用的节点。

附源码片段 · 图处理与编译

Linux Kernel·BPF verifier / 控制流图检查v6.12

用显式栈遍历 BPF 控制流

Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS，检查跳转目标、可达性及控制流结构。

栈深度优先搜索图数组

附源码片段 · 图处理与编译

LLVM·Legacy CallGraphSCCPassllvmorg-19.1.0

按强连通分量组织递归调用图优化

LLVM 的 legacy 调用图 pass 管理器使用 Tarjan SCC 迭代器，将相互递归的函数作为一组，并按被调用方优先的顺序处理分组。

Tarjan 强连通分量算法深度优先搜索栈图

附源码片段 · 图处理与编译

Git·Revision walk / topo orderv2.46.0

让提交历史先展示后代，再展示祖先

Git 的拓扑历史遍历记录尚未输出的子提交数量；只有相关子提交都已处理，父提交才进入可输出集合。

拓扑排序图邻接表

附源码片段 · 图处理与编译

PyTorch·torch.utils.checkpointv2.5.1

用反向重计算减少训练激活占用

PyTorch 的非重入 activation checkpoint 在反向传播需要中间张量时重新执行对应前向片段，以额外计算换取更低的激活存储需求。

激活重计算图

附源码片段 · 内存管理

基础原理参考资料

Open Data Structures · AdjacencyLists邻接表的存储与边操作。

Open Data Structures · AdjacencyMatrix邻接矩阵的查询和空间成本。