页面加载中…
从一块格子到整张地图，四条主线一次吃透图论核心套路
图论看似抽象，其实网格矩阵就是最直观的图：每个格子是节点，四个方向是边。本路径从网格 DFS 入手，逐步过渡到多源 BFS、拓扑排序、并查集，最后收口 Dijkstra 与 Prim，每一步都有前置技法可复用。按序刷完，面试中遇到任何图题都能拆出套路、动笔开写。
适合：想系统学 DFS/BFS/拓扑/并查集/最短路的人
网格题统一心智模型：二维数组里每个格子 = 图的节点，上下左右四条边，visited 用原地标记（沉岛）或布尔数组防重入。掌握这套模板后，所有网格 DFS 题都是同一份代码的变形。
图论开篇：把每个 '1' 当图节点，DFS 递归把整座岛「沉掉」（置 '0'），外层循环计次即可。这是网格图题的基础模板，后面每道题都站在它肩膀上。
沿用上一题「沉岛 DFS」的框架，只把「计次」换成「累加节点数并取最大值」——同一模板，返回值从 void 变成 int，零额外心智负担。
上两题从内部扩散找岛，这题反过来：从边界出发 DFS 标记「不能翻转的 O」，剩余 O 才翻转。学会「反向 DFS / 从边界入手」，是网格题的第二个高频套路。
把「被围绕的区域」的反向 DFS 推进一步：同时从太平洋边界和大西洋边界各跑一遍 DFS，两张 visited 取交集。双向反跑思路消除了正向枚举的高复杂度。
BFS 的本质是「按距离层序扩散」，适合求最少步数/最短时间。多源 BFS 是把所有起点同时压入队列，等价于虚拟一个超级源点；掌握这一招，腐烂橘子、01矩阵、墙与门全是同一个模板。
从 DFS 切换到 BFS：把所有初始烂橘子同时入队即是多源 BFS。BFS 层数天然对应时间步——「同时扩散几轮」就是答案，DFS 无法直接做到这点。
多源 BFS 退化为单源：从左上角一个起点出发，BFS 第一次到达右下角时的层数就是最短路长度。将「腐烂橘子」的多源模板缩成单源，感受两者的统一性。
再次多源 BFS：把所有「门」同时入队向外扩散填距离——与腐烂橘子完全同构，仅把「时间步」换成「距离值」，零额外心智负担。
BFS 从网格搬到词图：每个单词是节点，改一个字母可达是邻居，BFS 层数即最短序列长度。四向扩散 → 枚举 26×L 邻居，框架完全相同。
离开矩阵，进入邻接表建图。核心新概念：有向图的环检测（三色标记 DFS）和拓扑排序（Kahn BFS / DFS 逆后序）。拓扑排序是「有向无环图上的 BFS 层序」，掌握它就掌握了依赖调度类题目的通解。
第一道邻接表图题：DFS 遍历能到达的所有房间，判断是否访问全部节点。把网格的「四向邻居」换成「邻接表」，核心 DFS 框架不变。
DFS 升级为环检测：用三色（未访问/访问中/已完成）标记节点，「访问中」节点被二次访问即有环 = 课程无法完成。这是有向图 DFS 最重要的新技能。
在上一题环检测基础上输出具体顺序：DFS 子孙处理完后压栈逆序即拓扑序，或 Kahn 入度队列逐层弹出。两种写法复用同一张邻接表和访问标记。
把 Kahn 拓扑排序用到字母序推导：相邻单词逐字符对比得出先后约束 = 有向边，建图后跑上一题的拓扑排序。建图方式变，内核不变。
并查集用「找父节点 + 路径压缩 + 按秩合并」以近 O(1) 判断连通性，擅长处理动态合并问题，是 DFS/BFS 的轻量替代。最短路（Dijkstra）和最小生成树（Prim/Kruskal）是带权图的终极套路，以此收口图论全貌。
并查集入门：省份数 = 无向图连通分量数，DFS 也能做，但并查集只需逐边 union、最后数根节点。感受「合并连通块」用并查集比 DFS 更简洁的地方。
并查集的「联通性检测」发挥作用：逐条添加边时，若两端节点已同属一个集合，则该边是冗余边。这是并查集最经典的应用——比 DFS 环检测更直观、代码更短。
进入带权图：Dijkstra 用最小堆贪心弹最近节点并松弛邻边，求单源最短距离。从无权 BFS「层数=距离」到「堆+松弛」，是图论最重要的一次跃升。
把 Dijkstra 框架转向最小生成树：Prim 同样用「最小堆 + visited」，只是松弛目标从「到源距离」变成「并入树的边权」，代码骨架几乎相同。