图论 · graph 算法合集

把对象之间的关系画成节点 + 边,就得到一张 graph;一大批问题——最短路线、任意两点间的距离表、最省成本的连通、带依赖的排程、一笔画、一组不等式的可行解、把图近似成树以便 DP——都落在图算法上。本合集主要用单步播放拆开几个经典算法:选一张图、逐步前进 / 后退、对照右侧的状态表与高亮代码,看它们如何一步步收敛(树分解一页除外)。

建议顺序:先看 topological sort(DAG 上的线性化, 最基础),再看带权图上的 Dijkstra 与最小生成树两个 greedy(Bellman-Ford 属动态规划, 与它们不同源)——shortest path 与 minimum spanning tree;由 shortest path 顺势接 all-pairs(Floyd 的矩阵递推)与它的应用出口 difference constraints(一组不等式即一张图)。Euler path 一页不依赖前面几页, 随时可插入;最后是把图按 treewidth 近似成树的 tree decomposition。

共同的骨架: 算法把执行过程预先展开成一串帧 (frame),每帧是一份完整快照(数据结构状态 + 高亮代码行 + 解说);页面只持有一个游标,前进 / 后退 / 自动播放都只是移动游标再重绘。底层的 priority queue 与 disjoint set 另有专题展开(见下方相关链接)。 topological-sort · 拓扑排序

拓扑排序：Kahn 与 DFS

DAG 的线性化：Kahn 按入度逐层剥离，DFS 取完成序的逆序；队列提前耗尽即说明图里有环。

shortest-path · 最短路径

最短路径：拆解 Dijkstra

relaxation 是单源最短路的共同内核：Dijkstra 靠非负边权按 dist 递增确定，Bellman-Ford 反复扫边容许负权，A* 用启发式收窄搜索。

mst · 最小生成树

最小生成树：Prim 与 Kruskal

cut theorem 保证「任一割上最小的横跨边必属某棵最小生成树」，Prim 与 Kruskal 是它的两种贪心走法。

tree-decomposition · 树分解

树分解与 treewidth

树分解把顶点装进树上的 bag，treewidth 衡量图离树有多远；bag 之间的交集是分隔集，DP 因此可在树上做。

euler · 一笔画

Euler path：度数判据与 Hierholzer

一笔画有一条只看度数的判据：无向图全偶或恰两奇，有向图入出度相等或差一。Hierholzer 用线性时间把路线构造出来；而把「每条边一次」换成「每个点一次」，同一张图上的问题就成了 NP-complete。

all-pairs · 全源最短路

全源最短路：Floyd 与 Johnson

Floyd-Warshall 的三重循环是一层 DP，$k$ 是允许中转的点集前缀，故须在最外层。同一副骨架可算 transitive closure，对角线出负值即 negative cycle；稀疏图改用 Johnson 重赋权。

difference-constraints · 差分约束

差分约束系统：不等式与最短路

一组 $x_j - x_i \le c$ 与一张边权图上的松弛条件逐字相同。Bellman-Ford 从超级源点跑出的 dist 就是一组可行解，检出 negative cycle 即判定系统无解。

相关链接

• 优先队列 · binary heap 本站 Dijkstra / Prim 的底座:每步 extract-min 的高效实现。看 sift-up / sift-down 如何维持堆序。
• 并查集 · disjoint set 本站 Kruskal 判环的底座:近乎 O(1) 地合并集合、查询连通性 (路径压缩 + 按秩合并)。
• 分支限界 · branch & bound 本站 A* 的推广:把「乐观界」用于剪枝。Dijkstra / A* 都可视作它在最短路上的特例。
• 动态规划 · 背包九讲 本站 DAG 上的递推天然按拓扑序进行;tree decomposition 把图 DP 推广到「树宽有界」的图。
• Graph theory en.wikipedia.org 图论的总览:有向 / 无向、带权、连通性、各类经典问题与算法的索引。