图算法全景图：从结构探索到组合优化

社交网络里谁是意见领袖？GPS 导航怎么找最短路线？编译器如何确定指令的执行顺序？推荐系统如何发现用户社区？这些问题看起来毫不相关，但它们有一个共同的底层结构——图（graph）。只要一个问题涉及”实体之间的关系”，就能建模为图；只要建模为图，就可以调用一整套成熟的算法工具箱。

本文是整条图算法路径的开篇纲领。 我们不会深入任何一个算法的细节，而是建立全局概念地图——图能建模什么、图有哪些基本类型、图怎么存在计算机里、图上有哪些核心问题、用什么范式去解决它们、以及这 19 篇后续文章如何组织成一条连贯的学习弧线。

为什么图是通用建模语言

一个核心观察：任何”实体 + 关系”的场景，都能建模为图 $G = (V, E)$ ——实体是顶点（vertex），关系是边（edge）。

这个抽象看似简单，却有巨大的威力：一旦将现实问题映射为图，所有图算法立刻可用。你不需要为社交网络重新发明社区发现算法，不需要为交通路网重新发明最短路径算法——它们是同一个问题在不同领域的实例。

更重要的是，图的算法工具箱经过了半个多世纪的打磨。从 Euler 1736 年的哥尼斯堡七桥问题到今天的图神经网络（GNN），图论提供了一套从精确算法到启发式近似的完整梯度。学会这套工具箱，你获得的不是一个算法，而是一种思维方式——遇到问题先问：这里有没有图？

图的基本词汇表

在进入算法之前，我们需要建立一套共同语言。以下是图论中最常见的类型分类。

按边的方向

无向图（undirected graph）：边没有方向， $(u, v)$ 和 $(v, u)$ 是同一条边。社交网络的好友关系是典型例子。
有向图（directed graph, digraph）：边有方向， $(u, v)$ 表示从 $u$ 指向 $v$ 的一条边。网页之间的超链接、任务之间的依赖关系都是有向的。

按边的权重

无权图（unweighted）：所有边等价，只关心”连不连”。
加权图（weighted graph）：每条边 $e$ 附带一个权重 $w(e)$ ，可以表示距离、成本、容量、概率等。

按密度

稀疏图（sparse）： $m = O(n)$ 或 $m = O(n \log n)$ ，边远少于所有可能的边数 $\binom{n}{2}$ 。绝大多数现实网络是稀疏的——社交网络中平均每人有几百个好友，而不是几亿个。
稠密图（dense）： $m = \Theta(n^2)$ ，接近完全图。某些科学计算场景会出现。

特殊图类型

DAG（Directed Acyclic Graph，有向无环图）：有向图但没有环。编译器的依赖图、课程的先修关系、Git 的提交历史都是 DAG。DAG 有一个极其重要的性质：可以进行拓扑排序（Art. 3）。
二部图（bipartite graph）：顶点分成两组 $U$ 和 $V$ ，边只在 $U$ 和 $V$ 之间，组内没有边。用户-商品关系、学生-课程关系都是二部图。匹配问题（Art. 13）在二部图上有高效算法。
树（tree）：无环的连通图，恰好 $n-1$ 条边。文件系统目录、组织架构、决策树都是树。树上有一套专属的高效工具（Art. 5）。
多重图（multigraph）：两个节点之间允许多条边。比如两个城市之间有公路、铁路、航线三条不同的连接。
超图（hypergraph）：一条”边”可以连接多于两个节点。论文的共同作者关系是典型例子——一篇论文连接所有作者。本路径不深入超图，但会在 Art. 19 中提及。

图的表示方法

同一张图可以用不同的数据结构存在计算机里。选择正确的表示方法，直接决定算法的实际效率。

邻接矩阵（Adjacency Matrix）

用一个 $n \times n$ 的矩阵 $A$ 表示图： $A_{ij} = 1$ 表示从 $i$ 到 $j$ 有边（加权图中 $A_{ij} = w(i,j)$ ）。

优点：查询任意两点之间是否有边， $O(1)$ 。矩阵运算方便（ $A^k$ 的第 $(i,j)$ 项 = 从 $i$ 到 $j$ 的长度为 $k$ 的路径数）。
缺点：空间 $O(n^2)$ ，不管有多少边。遍历一个节点的邻居需要 $O(n)$ 。

适用场景：稠密图、需要快速边查询、需要矩阵运算（如谱方法）。

邻接表（Adjacency List）

为每个节点 $v$ 维护一个列表 $\text{adj}[v]$ ，存储 $v$ 的所有邻居。

优点：空间 $O(n + m)$ ，只存实际存在的边。遍历邻居只需 $O(\deg(v))$ 。
缺点：查询 $(u, v)$ 是否有边需要 $O(\deg(u))$ （用哈希表可优化到均摊 $O(1)$ ）。

适用场景：稀疏图（绝大多数情况）、遍历密集的算法（BFS/DFS）。邻接表是本路径的默认表示方法。

边列表（Edge List）

直接存一个列表 $[(u_1, v_1), (u_2, v_2), \ldots]$ ，每个元素是一条边。

优点：空间 $O(m)$ ，结构最简单。
缺点：查询和遍历都需要 $O(m)$ 。

适用场景：只需要按边遍历的算法（如 Kruskal 的最小生成树）、图的输入/输出。

选错表示方法的代价

表示方法不是小事——选错了，复杂度可以差好几个数量级。

具体例子：在一张有 $n = 10^6$ 个节点、 $m = 10^7$ 条边的稀疏图（平均度 10）上，BFS 遍历所有节点的邻居：

邻接矩阵：每个节点扫描一整行 → $O(n^2) = O(10^{12})$ 次操作
邻接表：每个节点只遍历实际邻居 → $O(n + m) = O(10^7)$ 次操作

差了 五个数量级。这不是常数因子的差异，而是”能跑完”和”跑到天荒地老”的区别。

统一符号系统

为了保证整条路径的一致性，我们在这里定义全路径通用的符号约定。后续 19 篇文章都遵循这套符号。

几个重要约定：

$n$ 和 $m$ 始终表示顶点数和边数，不做他用
度用 $\deg(v)$ 而不是裸的 $d$ ，因为 $d(u,v)$ 保留给最短路径距离
$A$ 在图文章中默认是邻接矩阵；其他含义加下标

核心问题分类

图上的问题千变万化，但可以归纳为有限的几大类。以下这张表是整条路径的”目录”——每一行都有一篇专门的文章来深入展开。

点击下方卡片可跳转到对应文章：

完整问题分类表（文字版）：

基本问题	一句话	典型算法	文章
可达性与遍历	能不能到？怎么走遍？	BFS, DFS, Flood Fill	Art. 1
连通性与结构	图能拆成几块？哪里是瓶颈？	SCC, 桥/割点, 2-SAT	Art. 2
拓扑排序与 DAG	有依赖时怎么排合法顺序？	Kahn, DFS 后序, 关键路径	Art. 3
环与路径	走遍所有边/节点？	Hierholzer, 哈密顿判定	Art. 4
树上算法	特殊图的专属工具	LCA, 重心分解, 直径	Art. 5
最短路径	最便宜的路？	Dijkstra, Bellman-Ford, Floyd, A*	Art. 6
中心性	谁最重要？	Degree, Betweenness, PageRank	Art. 7
社区发现	哪些节点抱团？	Louvain, 标签传播, k-core	Art. 8
相似性与同构	两个图/节点有多像？	SimRank, WL test, Graph Kernel	Art. 9
团与密子图	最紧密的子群？	Bron-Kerbosch, k-core/k-truss	Art. 10
最小生成树	最便宜地连通所有人？	Prim, Kruskal, Steiner	Art. 11
网络流	管道能通多少？瓶颈在哪？	Ford-Fulkerson, Dinic	Art. 12
匹配	怎么最优配对？	Hungarian, Hopcroft-Karp	Art. 13
着色与划分	最少几种颜色？	贪心着色, Brooks 定理	Art. 14
NP-hard 与近似	最优解算不出来怎么办？	Christofides, LP relaxation	Art. 15
随机图模型	真实网络长什么样？	ER, Watts-Strogatz, BA	Art. 16
概率图模型	图上的不确定性推理	贝叶斯网, 信念传播	Art. 17
图嵌入与 GNN	把图变成向量	Node2Vec, GCN, GAT	Art. 18
图建模案例集	现实问题→图建模	编译器, 推荐, 因果推断	Art. 19

算法范式索引

解决图上的问题不是靠”记住算法”，而是靠理解范式。同一种范式可以解决看似不同的问题，而同一个问题也可能有不同范式的解法。本路径定义了 10 种算法范式，每篇文章开头都会标注涉及哪些范式。

完整算法范式索引表：

范式	一句话	典型算法
穷举搜索	系统地访问所有可能，不遗漏	BFS, DFS
贪心	每步选当前最优，不回头	Dijkstra, Prim, Kruskal
动态规划	拆成重叠子问题，记住答案避免重算	Floyd-Warshall, DAG 最长路径
迭代逼近	维护估计值，反复改善，直到收敛	Bellman-Ford, 信念传播
增广路	在残余图中找还能改善的路径	Ford-Fulkerson, 匈牙利算法
对偶性	一个问题的最优解 = 另一个互补问题的最优解	最大流 = 最小割, 独立集 $\leftrightarrow$ 覆盖
回溯 + 剪枝	DFS 搜索解空间树，不可能更优时回头	Bron-Kerbosch, 图着色
分治	拆成子图，分别求解，合并结果	重心分解
消息传递	每个节点根据邻居消息更新状态	标签传播, 信念传播, GNN
约束松弛与近似	放松约束得易解版本，映射回来	Christofides, LP rounding

学习这些范式有一个关键好处：当你遇到新问题时，不需要从零开始设计算法。你可以问自己——这个问题有贪心性质吗？有最优子结构吗？能不能松弛？——然后从已知范式中找到起点。

探 → 量 → 优 → 建模：路径弧线

19 篇文章不是 19 个孤立的算法教程——它们沿着一条认知弧线展开。

Part 1 “探”（Art. 1–5）：面对一张图，第一件事是看清它的结构。BFS 和 DFS 是最基础的两个遍历工具——后续几乎所有算法都以它们为子程序。有了遍历能力，我们可以回答：图是否连通？有没有环？能不能拓扑排序？树上有哪些特殊结构？

关键澄清：Part 1 的 BFS/DFS 不仅仅属于”探索”——它们是通用基础设施。后续 Part 2 的 Dijkstra 用 BFS 的思想，Part 3 的 Ford-Fulkerson 用 BFS 找增广路，Part 4 的消息传递本质上也是广度优先的信息扩散。所以 Part 1 是整条路径的地基。

Part 2 “量”（Art. 6–10）：看清结构之后，我们想量化——节点之间多远？谁最重要？哪些节点抱团？两张图有多像？Part 2 的问题都是描述性的：回答”图是什么样的”。

Part 3 “优”（Art. 11–15）：量化之后，我们想行动——如何最便宜地连通所有节点（最小生成树）？管道网络最大能通多少流量（网络流）？怎么把任务最优地分配给机器（匹配）？Part 3 的问题都是决策性的：回答”图上该怎么做”。这里也是 NP-hard 问题集中出现的地方，我们会学习如何在精确解不可行时设计近似算法。

Part 4 “建模”（Art. 16–19）：前三个 Part 假设图已经给定。Part 4 反过来问——现实世界的问题如何映射为图？真实网络有什么统计特征？如何在图上做概率推理？如何用神经网络学习图的表示？Part 4 是图与外部世界的接口。

四个 Part 的认知递进：被动探索结构 → 量化度量 → 主动优化决策 → 逆向建模。每篇文章都知道自己在这条弧线上的位置。

两种视角：组合 vs 矩阵

图的问题可以从两个互补的视角来理解：

组合/算法视角：操作的是节点、边、路径、子图。用遍历、贪心、DP、增广等范式设计算法。这是本路径的主题。
矩阵/谱视角：把图编码为邻接矩阵 $A$ 或 Laplacian 矩阵 $L = D - A$ ，用特征值和特征向量揭示图的性质。PageRank 是幂迭代，谱聚类基于 Fiedler 向量，GNN 的消息传递可以写成矩阵乘法。这是 matrix-math 路径 Part 2 “传” 的主题。

两种视角不是对立的，而是互补的。很多问题的最优解法同时用到两种视角。但为了保持聚焦，本路径主攻组合/算法视角，谱方法用 cross-reference 指向 matrix-math 路径的相关文章：

本路径不覆盖什么

为了保持聚焦，以下内容不在本路径范围内：

谱图论和矩阵方法：邻接矩阵的特征值分析、Laplacian 谱、谱聚类的数学推导。这些在 matrix-math 路径已有系统覆盖。本路径在需要时会引用这些结果，但不会重新推导。
算法竞赛技巧与极端优化：如 $O(n \sqrt{m})$ 的分块技巧、离线算法、各种”卡常”手段。我们关注算法的核心思想和正确性，不追求竞赛级的实现细节。
具体编程语言的图库 API 教程：我们会在每篇文章的”实现指引”中列出 NetworkX、Neo4j GDS、scipy 等库的函数名，但不会写完整的编程教程。

前置知识

本路径假设读者具备以下基础：

基本数据结构：数组、链表、栈、队列、哈希表、优先队列（堆）
递归和基本算法分析：能读懂 $O(n \log n)$ 之类的复杂度标注
基础概率（Part 4 需要）：概率分布、条件概率、贝叶斯定理

不需要图论的任何前置知识——本路径从零开始构建。

实现指引

作为全景图，本文不涉及具体算法，但这里列出本路径会频繁使用的图算法库：

库	语言/平台	特点
NetworkX	Python	最常用的通用图算法库，API 清晰，适合学习和原型
igraph	Python / R / C	高性能图计算，比 NetworkX 快一个数量级
Neo4j GDS	Neo4j (Java)	生产级图数据库的图数据科学库
scipy.sparse.csgraph	Python	基于稀疏矩阵的图算法，适合大规模稀疏图
scikit-network	Python	大规模网络分析，基于稀疏矩阵
PyG (PyTorch Geometric)	Python	图神经网络框架
DGL (Deep Graph Library)	Python	另一个主流 GNN 框架
pgmpy	Python	概率图模型

每篇后续文章都会在”实现指引”一节中标注具体算法在这些库中的函数/方法名。

⚙️ 迭代机器视角 — 图算法全景

全景文章本身不包含具体算法，而是提供分类导航。具体算法的框架映射见各篇文章的 callout。

→ 框架详解：Art. 0A

总结与展望

本文建立了整条图算法路径的概念框架：

图是通用建模语言：任何”实体 + 关系”都能建模为 $G = (V, E)$
基本词汇表：有向/无向、加权/无权、稀疏/稠密、DAG、二部图、树
三种表示方法：邻接矩阵（稠密图）、邻接表（稀疏图，默认）、边列表（边算法），选错表示可差五个数量级
19 个核心问题：从遍历到 GNN，覆盖”看清结构→量化性质→组合优化→现实建模”的完整弧线
10 种算法范式：穷举、贪心、DP、迭代逼近、增广路、对偶性、回溯剪枝、分治、消息传递、约束松弛
组合视角 vs 矩阵视角：本路径主攻前者，后者参见 matrix-math 路径

在进入具体算法之前，Art. 0A: 图上的通用迭代机器（上）和 Art. 0B:（下）将揭示一个贯穿全路径的统一视角：BFS、Dijkstra、PageRank、GC tri-color marking、编译器 dataflow 分析、GNN message passing 等来自不同领域的算法，共享同一个七组件计算骨架。后续每篇文章都会在「迭代机器视角」callout 中将该篇算法映射回这个框架。

要看清一张图的结构，第一个工具是系统地遍历——逐层扩展的 BFS 和递归深入的 DFS。Art. 1: BFS 与 DFS 将详细展开这两个图算法的基石。