经典图算法
这一页把五个最常用的图算法放慢到一步一停：广度优先与深度优先、Dijkstra 与 Bellman–Ford、Kruskal 与 Prim、最大流最小割、二分图匹配。每一个都不只是"能跑出答案"，而是要看清它为什么正确——以及在什么条件下它会给出错误答案。
LAB 01
广度与深度优先
单步执行，队列与栈的内容同屏显示
问题
在一张图上"走遍所有点"有两种最基本的走法：一圈一圈往外铺，还是一条路走到黑？这个选择决定了你能回答什么问题——最短路、连通性、拓扑排序、回路检测，分别只对其中一种成立。
模型
两者只差一个容器：BFS 用队列（先进先出），DFS 用栈（后进先出）。
BFS：队列 → 层序，无权图最短路； DFS：栈 → 深度优先，连通分量、拓扑序、回路
两者复杂度都是 O(|V| + |E|)。BFS 的层序保证"先访问到的一定是最近的"，DFS 没有这个性质，但它的递归结构能自然地暴露回路和割点。已访问—
队列 / 栈长度—
是否已到终点（路径长）—
最深探到第几层—
BFS 逐层铺开，DFS 一条道走到黑。这个差别决定了它们各自的用途：BFS 第一次碰到终点时走的一定是最少边数的路（无权图最短路），DFS 不保证；但 DFS 的栈深度只和路径长度有关，空间上更省，而且天然适合做拓扑排序、找强连通分量、检测环这些"要看清结构"的事。
LAB 02
最短路
标记已定点、松弛边；加一条负权边看 Dijkstra 怎么出错
问题
导航软件要在几百万条路里找最快的一条。Dijkstra 的想法很简单：永远先确定"已知距离最小"的那个点。可这个想法有一个前提，前提一破就彻底错。
模型
Dijkstra 的正确性依赖"边权非负"：一旦确定，就不会再被更短的路径刷新。
松弛：d[v] ← min( d[v], d[u] + w(u,v) )， 前提 w ≥ 0
有负权边时必须换 Bellman–Ford（O(|V||E|)，还能检出负环）。这一台会加一条负权边，让你亲眼看见 Dijkstra 在哪一步做错了决定。已确定的点—
松弛次数—
到终点的距离—
结果正确吗—
勾上「加入一条负权边」，再跑 Dijkstra。它会给出一个看起来很正常、但其实不是最短的答案——因为 Dijkstra 的正确性依赖一个前提：已经出队的点不可能再被改进。负权边直接推翻这个前提。Bellman–Ford 慢得多，但它反复松弛所有边直到不再变化，所以不依赖这个前提。注意这条负边是单向的（图上带箭头的红色虚线）：无向图上放负边会造出负环，那时最短路根本不存在，演示的就不是算法出错而是问题没有答案了。这是算法选择里最典型的一次权衡——快的那个有前提条件，而前提条件往往写在你没读的那一行。
LAB 03
最小生成树
两种贪心并排跑，最终树相同但过程完全不同
问题
给几个村子通电，怎么用最少的电缆把所有村子连起来？这个问题有两个完全不同的贪心解法，过程看起来毫无关系，结果却一模一样——这本身就值得解释。
模型
最小生成树。Kruskal 按边排序合并，Prim 从一个点长出来。两者都靠同一条"割性质"。
割性质：任何一个割上权值最小的边，一定属于某棵最小生成树
正因为这条性质对任何割都成立，两种顺序完全不同的贪心才会殊途同归。Kruskal 是 O(|E| log|E|)，Prim 配堆是 O(|E| log|V|)。Kruskal 已选边—
Prim 已选边—
两棵树一样吗—
总权重—
两种贪心，过程完全不同，结果通常相同。Kruskal 按边从小到大扫全局，Prim 从一个点往外长。最终总权重一定相等（最小生成树的权重是唯一的），但当存在等权边时，具体选中哪条可能不同——这提醒一件常被忽略的事：最优解的"值"唯一，最优解本身未必唯一。
LAB 04
最大流最小割
找增广路、更新残量网络，最后高亮那条最小割
问题
一条管网从源头到终点最多能送多少水？直觉上这取决于最窄的那一段——而这个直觉可以写成一条精确的定理，它把一个"最大化"问题和一个"最小化"问题变成了同一个问题。
模型
最大流最小割定理：最大流的值等于最小割的容量。
maxf |f| = min(S,T) c(S,T)， 残量网络里没有增广路 ⟺ 当前流最大
增广路算法（Ford–Fulkerson / Edmonds–Karp）每次在残量网络里找一条还能走的路并加满。这是线性规划对偶在图上的一个具体实例。当前流量—
增广次数—
最小割容量—
最大流 = 最小割？—
跑完之后看那条高亮的割。最大流最小割定理说：能推过去的最大流量，恰好等于"把源和汇分开所需切断的最小容量"。这条定理的实用价值在于它给了你一个可验证的最优性证明——找到一个流和一个割且两者相等，就证明了这个流是最大的，不需要再搜索。
LAB 05
二分图匹配
增广路径找匹配，对应到「任务指派」的实际问题
问题
把工人分配给任务、把学生分配给导师、把订单分配给车辆——怎么在"谁能做什么"的约束下配对最多的组合？这个问题看着和上一台没关系，其实是它的一个特例。
模型
二分图最大匹配可以化成单位容量的最大流；König 定理给出对偶。
最大匹配数 = 最小顶点覆盖数（König 定理，只对二分图成立）
直接算法是匈牙利增广路法：从未匹配点出发找一条交错路，翻转它就多配一对。复杂度 O(|V||E|)，Hopcroft–Karp 可优化到 O(√|V| |E|)。当前匹配数—
最大匹配数—
最小点覆盖—
有没有 Hall 阻塞集—
这就是"人—任务"指派问题的骨架。König 定理说，二分图里最大匹配数等于最小点覆盖数；而 Hall 定理给出了"能否全部匹配上"的判据：存在一组人，他们会做的任务总数比人还少，就一定有人分不到活。把"会做的概率"调低，看阻塞集什么时候出现——它直接指出了瓶颈在哪几个人身上，比只报一个"匹配不上"有用得多。
这一页想说的
五个算法，五个不同的"为什么正确"。值得带走的不是伪代码，而是每个算法背后那句前提：Dijkstra 要非负权，Kruskal 靠的是"环上最重的边一定不在最小生成树里"，最大流靠的是残量网络里没有增广路就到顶了，匹配靠的是增广路径定理。竞赛里选错算法，多半不是不知道有这个算法，而是没检查前提。