图论算法专题

这部分知识我前后看过不止一次。刚接触“图论算法专题”时，图论是我最容易学散的一块，遍历、最短路、生成树、拓扑排序各有模板，却缺少一张按问题选择算法的地图。等我回头从问题本身出发，而不是从模板出发，很多原来零散的规则才慢慢连在一起。下面按我自己的理解过程展开。

图论算法专题负责处理“关系网络”里的问题。只要问题里出现连接、路径、依赖、分组、容量、匹配，就很可能能抽象成图。

图论最容易学散，因为算法名字很多。更好的学习方式是按问题问自己：我要遍历、求最短路、求连通块、求最小连接成本、处理依赖、匹配资源，还是处理流量？

先画点和线，不要先背算法名

地铁站是点，线路是边；课程是点，先修关系是有方向的边；服务器是点，网络延迟是边权。图不是某一种固定业务，而是一种只保留“对象与关系”的建模语言。

第一次遇到图题，先回答四件事：边有没有方向、有没有权重、数据是否连通、最终要求路径还是整体结构。模型明确后，算法范围会大幅缩小。

我为什么先补这一章

这一章重点解决：

1. 图问题如何建模。
2. 不同图算法适合什么边权和场景。
3. 连通、路径、匹配、割、流之间的区别。
4. 工程中如何把业务关系抽象成点和边。

我自己的学习顺序

1. 图算法：从遍历到最短路。
2. 并查集算法应用。
3. 最短路算法。
4. 最小生成树。
5. 二分图与匹配。
6. 强连通分量 Tarjan。
7. 网络流入门。

我当时最容易混淆的地方

最短路解决的是“两点之间路径成本最小”；最小生成树解决的是“连接全部点的总成本最小”。这两个问题名字像，但目标完全不同。

并查集适合动态合并集合，但它不擅长回答复杂路径信息。

网络流不是普通路径问题，它多了容量约束，适合描述资源从源点流向汇点的最大可行量。

我后来这样检查自己是否真的理解

• 无权图最短路为什么用 BFS？
• Dijkstra 为什么要求边权非负？
• Kruskal 为什么天然适合并查集？
• Tarjan 缩点之后为什么会得到 DAG？