图论 · graph 算法合集

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

建议顺序:先看 topological sort(DAG 上的线性化, 最基础),再看带权图上的两个 greedy——shortest path 与 minimum spanning tree,最后是把图按 treewidth 近似成树的 tree decomposition。

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

拓扑排序：Kahn 与 DFS

DAG 上把节点排成一条线、让每条边都从前指向后。从拓扑序的定义与「有环则无解」讲起，单步运行 Kahn（按 in-degree 一层层剥）与 DFS（后序完成、逆序即拓扑序）两种算法，并看它们如何顺带把图里的环检测出来。

shortest-path · 最短路径

最短路径：拆解 Dijkstra

从唯一的内核动作 relaxation 与 dist[] estimate 讲起，单步看 Dijkstra 的 greedy 逐点 settle；再看有 cycle 为何不影响正确性、而一条 negative-weight edge 为何让它失效，最后给它装上启发式得到 A*。

mst · 最小生成树

最小生成树：Prim 与 Kruskal

从 cut theorem 出发，论证 greedy 选取最小 crossing edge 的正确性。单步运行 Prim（从一点长出树）与 Kruskal（按 edge weight 排序 + 并查集判环），两种算法得到相同的最小总 weight。

tree-decomposition · 树分解

树分解与 treewidth

treewidth 衡量一张图有多接近一棵树。从 tree decomposition 的三条性质出发，跨图族对比 treewidth，再看 bag 作为 separator 如何支撑分解树上的 DP——许多 NP-hard 问题在低 treewidth 的图上可高效求解。

相关链接

• 优先队列 · 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 图论的总览:有向 / 无向、带权、连通性、各类经典问题与算法的索引。