图论

一句话：图是”允许有环、允许多个父节点”的树，所以树的 DFS/BFS 在图上全部适用，只是多了一件必须做的事——记录访问过的节点，否则会在环里死循环。图论题的额外技巧（拓扑排序、并查集）都是为了处理树没有的两个新问题：依赖顺序和动态连通性。

DFS/BFS + visited：图遍历的通用模板

200-岛屿数量、133-克隆图、417-太平洋大西洋水流、994-腐烂的橘子 都是”从若干起点出发，遍历所有可达节点”的变体，模板完全一致：DFS 或 BFS + 一个 visited 集合（或直接在原地标记）防止重复访问。选 DFS 还是 BFS 通常只看题目要不要”层数/步数”——994 要求”最少经过几轮”，天然是 BFS（层序自带步数信息）；200 只关心”连通块有几个”，DFS/BFS 都行。

787-K站中转内最便宜的航班 是带权图最短路的变体（Bellman-Ford 思想的有限轮次版本：每轮只允许松弛一次，松弛 K+1 轮对应最多经过 K 个中转站），和无权图的 BFS 遍历不是同一件事——边有权重时，“先到达”不等于”代价最小”，不能再用普通 BFS。

拓扑排序：把”依赖关系”排成线性顺序

207/210-课程表、802-找到最终的安全状态 的共性是：节点之间有”必须先做 A 才能做 B”的依赖关系，问能不能排出一个满足所有依赖的顺序（或者顺序本身是什么）。

做法是统计每个节点的入度，把入度为 0 的节点（没有前置依赖）依次加入队列处理，每处理一个节点就把它指向的节点入度减一，减到 0 就入队——这本质仍是 BFS，只是入队条件从”访问过就入队”换成了”入度归零才入队”。如果最终不是所有节点都被处理到，说明剩下的节点构成了环，此时不存在合法顺序（207 判断”能否修完所有课”，本质就是判断图中是否有环）。

并查集：动态维护连通性

547-省份数量、684-冗余连接、990-等式方程的可满足性、1319-连通网络的操作次数 的共性是：不断有新的”两个节点相连”的信息进来，要随时回答”这两个节点当前是否连通”。

如果每次都重新 DFS 遍历判断连通性，代价太高；并查集用一棵”指向父节点”的森林表示连通关系，find 找到集合代表元、union 合并两个集合，配合路径压缩和按秩合并后，均摊复杂度趋近 O(1)（反向阿克曼函数）。684-冗余连接 的应用是：依次合并每条边的两个端点，第一条”合并前发现两端点已经连通”的边，就是那条多余的边（加入它会形成环）。

什么时候该用并查集而不是 DFS：如果连通关系是动态增加的（边一条条给出，中间穿插查询），并查集是唯一合理的选择；如果图是静态给定的，一次性求连通块数量，DFS/BFS 和并查集效果等价，选更顺手的即可。