图论在力扣hot100里一直是个非常微妙的存在。说它难吧真正的高阶算法像网络流、强连通分量一个都没考说它简单吧岛屿数量、腐烂的橘子这些题又确实劝退了不少人。我自己刷完这一系列之后最大的感受是hot100里的图论题其实是一个被精心设计的“图论入门阶梯”从网格遍历到拓扑排序再到前缀树每一步都在帮你补一块拼图而这些拼图正好覆盖了面试中最常被问到的图论形态。这篇文章就把我刷完这些题之后的完整思路、代码模板和踩坑记录一次性整理出来不管你是刚开始刷图论还是已经磕磕绊绊刷了一半应该都能找到点有用的东西。1. 力扣hot100图论题的整体拆解与刷题路线1.1 hot100到底考了哪些图论题先把题目摆出来。hot100里真正算得上图论范畴的题我按编号列一下200岛屿数量、994腐烂的橘子、207课程表、208实现Trie前缀树、79单词搜索、329矩阵中的最长递增路径。有的刷题记录会把208单独拎出去归到“设计题”或者“字符串题”但从数据结构本质上来讲Trie就是一个多叉树、一个有向无环图放在图论里理解反而更顺畅。这六道题看起来各管各的实际上暗含了一条非常清晰的递进线先学会在网格可以理解成最特殊的图上做DFS和BFS然后从网格跳出来用邻接表处理真正的稀疏图并做拓扑排序最后再用Trie这种带权边的“图”做高效前缀检索。也就是说hot100不是随机挑了几道图论题而是故意让你把DFS、BFS、拓扑排序、前缀树这些基本功各练一遍。1.2 为什么说这个组合是面试图论的天花板覆盖我面试过不少公司也帮朋友模拟过面试图论这块能问的无非就这么几类网格上的连通性问题对应岛屿数量、多源最短路径或扩散问题对应腐烂的橘子、依赖关系处理与环检测对应课程表、大量字符串的前缀匹配对应Trie、以及带状态递推的图上搜索对应矩阵最长递增路径。hot100用六道题把这些场景全打了一遍覆盖面非常精准。而且这些题还有一个共同点都是可以用暴力做法先拿分、再优化到标准解的题型。比如矩阵最长递增路径你不加记忆化也能跑但会严重超时课程表你不用拓扑排序靠DFS硬搜环也不是不行但代码复杂度直接翻倍。所以刷这组题你不仅是学算法还是在学“怎么从暴力思路平滑过渡到高效思路”这个能力面试比背模板值钱多了。1.3 建议的刷题顺序与时间分配按照依赖关系我推荐的刷题顺序是200岛屿数量 - 994腐烂的橘子 - 79单词搜索 - 329矩阵中的最长递增路径 - 207课程表 - 208实现Trie。前四道都是网格/矩阵题结构相似适合一口气拿下课程表是完完全全的图论题需要建立邻接表思维建议单独给一天Trie前缀树虽然代码量不大但节点设计和指针操作要格外小心也值得单独消化。时间上如果每天抽出两小时三天可以刷完第一遍第二遍专门看自己写过的代码把模板背到能默写的程度再花一天。总共四天左右就能把这六道题吃透。别贪快这组题的通用性远比数量重要。2. 网格类DFS/BFS图论最朴素的打开方式2.1 方向数组与边界检查网格题的两个命根子200岛屿数量是所有网格题的母题。给定一个由1和0组成的二维网格让你数有多少个岛屿——也就是连成一片的1的块数。最直觉的做法是遍历每个格子遇到一个没访问过的1就从这个格子出发把整个岛屿的1全部标记为已访问计数器加一。这里有一个非常关键的设计怎么“标记已访问”。最常见的做法是原地修改把走过的1改成0或者改成别的字符。好处是不用额外开二维数组空间复杂度省下一大块。我第一次刷的时候犹豫了很久担心原地修改会破坏数据后来想通了这道题本身只问岛屿数量网格里的1被你改成0之后反而能避免后续重复计数一举两得。方向数组的写法也很讲究。四个方向的固定写法是int[][] dirs {{0,1},{0,-1},{1,0},{-1,0}}每次遍历都用nextX x dirs[i][0]、nextY y dirs[i][1]来算新坐标。这一步是网格DFS的基本功后面腐烂的橘子、单词搜索、最长递增路径全都会用到。边界检查则是if (nextX 0 || nextX m || nextY 0 || nextY n) continue必须写对否则数组越界能把你整场心态搞崩。2.2 岛屿数量的DFS代码模板直接上我最后稳定使用的模板class Solution { int m, n; char[][] grid; int[][] dirs {{0,1},{0,-1},{1,0},{-1,0}}; public int numIslands(char[][] grid) { this.grid grid; this.m grid.length; this.n grid[0].length; int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(i, j); } } } return count; } private void dfs(int x, int y) { if (x 0 || x m || y 0 || y n || grid[x][y] ! 1) { return; } grid[x][y] 0; for (int[] dir : dirs) { dfs(x dir[0], y dir[1]); } } }这个实现的精髓在于把边界检查写进了DFS的入口处而不是在遍历方向之前单独判断。这样四个方向都能统一处理代码更短也不容易漏条件。岛屿数量在hot100里算是几乎零变体的题面试时只要能把模板默写出来就算过了一关。2.3 腐烂的橘子BFS层数与多源扩散的处理细节994腐烂的橘子是hot100里BFS的招牌题。给定一个网格2代表腐烂的橘子1代表新鲜的橘子0代表空格。每分钟腐烂橘子会向上下左右四个方向蔓延问多少分钟后所有新鲜橘子都变腐烂如果永远不可能全腐烂就返回-1。这道题和岛屿数量最大的区别是DFS解决不了它。因为你要算的是“扩散多少轮”这天然是按层推进的BFS的工作。而更隐蔽的考点是初始状态下可能同时有多个腐烂橘子它们同时向外扩散所以必须用多源BFS——把所有初始为2的位置先全部放入队列然后再开始逐层遍历。实现BFS时最需要注意的是层数的统计方式。很多新手会直接在while循环里用一个minute结果发现扩散的轮数永远比正确答案多1或少1。正确做法是在每轮遍历前记录当前队列大小size只处理size个节点处理完这size个节点后再加一分钟。这本质上就是“层序扩散”的骨架同时也和二叉树层序遍历的写法完全一致理解了这一个点后面很多BFS变形题都能通吃。每次遍历到相邻格子时如果遇到新鲜橘子就把它的值改成2代表腐化发生同时新鲜橘子总数减一。最终如果新鲜橘子总数为0就返回分钟数否则返回-1。2.4 单词搜索回溯在网格上的剪枝要点79单词搜索看起来和岛屿数量很像都是在一个字符矩阵里移动但它的核心机制完全不同岛屿数量是“扩散”单词搜索是“匹配路径”。它要求你在网格中找到一条路径使得路径上的字符按顺序组成给定的单词。这道题用的搜索模型是带回溯的DFS。为什么必须回溯因为从某个字符出发尝试匹配单词时可能会走错路走错之后你必须把标记过的格子“恢复原状”让后续的其他搜索路径能再次经过这个格子。如果你像岛屿数量那样做了永久标记那么一旦某个方向尝试失败旁边正确路径就被你亲手堵死了。回溯的标准写法是在DFS返回之后把标记撤销进入递归时visited[i][j] true递归返回后visited[i][j] false。不过针对这道题有一个更省空间的小技巧既然矩阵里都是字母可以直接把访问过的格子改成#之类的占位符递归返回后再改回原字符。这样连visited数组都不用开。这道题真正的难点是剪枝。我刷的时候发现如果只在进入每个格子后判断“当前字符等于word对应位置的字符”有时候会过慢。更好的做法是在DFS入口处先做一次字符比对不相等直接返回进入后再看index word.length()是否成立成立说明整个单词都找到了。千万别在进入前就做index len的判断因为那样会忽略最后一个字符恰好匹配上的情况。2.5 一个网格遍历的通用代码骨架刷完这三道网格题后我总结了一个可以覆盖它们大部分逻辑的骨架。// 以DFS为例的网格遍历通用模板 void dfs(int x, int y, 其他状态参数) { // 1. 越界或非法状态检查 if (不合法) return; // 2. 标记已访问或修改状态 visited[x][y] true; // 3. 满足终止条件时做处理 if (达成目标) { 记录结果; return; } // 4. 递归遍历四个方向 for (int[] dir : dirs) { dfs(x dir[0], y dir[1], 更新后的状态参数); } // 5. 如果允许路径复用则撤销标记回溯 }这套骨架覆盖了岛屿数量第2步永久标记、单词搜索第5步回溯、329最长递增路径状态参数换成路径长度并用记忆化数组代替visited。以后不管遇到什么网格题都可以先套这个骨架再针对题目改细节比现场重新设计要稳得多。3. 拓扑排序课程表背后的调度思维3.1 什么时候会想到用拓扑排序207课程表的描述很经典一共要修numCourses门课给定若干[a, b]对表示修a课之前必须先修b课问你有没有可能修完所有课。初看这道题很多人会先去想DFS能不能做能做但要同时维护三种访问状态未访问、访问中、访问完成稍微绕一点就容易出错。拓扑排序入度表的BFS解法才是面试里最稳妥、最好解释的方案。拓扑排序本质上解决的是“有向无环图”的线性化问题。把每一门课当成一个节点把[a, b]看成b指向a的一条有向边那么从入度为0不需要先修课的节点开始不断删除节点并更新后续节点的入度如果最后所有节点都能被删除说明这个图没有环也就意味着课程依赖关系不矛盾。这个思路跟现实的工程依赖非常相似。比如你有一个大型项目模块A依赖模块B模块B又依赖模块C那构建顺序就必须是C、B、A。拓扑排序就是彻底解决这种“谁先谁后”问题的通用算法。想通了这一层课程表这道题就成了工程依赖问题的缩小版你甚至可以把它当成一个迷你的编译器依赖分析器来理解。3.2 邻接表和入度表的构建细节用BFS实现拓扑排序最重要的准备工作是构建两个数据结构邻接表和入度表。邻接表就是每个节点的“后继节点列表”。在课程表里prerequisites数组给了[a, b]说明要先学b再学a所以应该建立b - a的边。构建时用ListListInteger下标就是节点编号列表里的元素就是它能指向的后续节点。入度表记录每个节点有几个前驱节点。初始时对每一对[a, b]把a的入度加一。入度表的作用非常明确入度为0的节点就是当前可以“直接修”的课因为它的所有先修课都已经完成了。我在第一次实现时踩过一个坑ListListInteger初始化只做了外层忘了给内层逐个初始化结果一调用get(0).add(...)就空指针。正确写法是在初始化时用一个for循环给每一层都new ArrayList()。这是个很容易被忽略的细节但几乎决定了代码能不能跑通。3.3 课程表BFS拓扑排序标准代码class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { ListListInteger graph new ArrayList(); int[] indegree new int[numCourses]; for (int i 0; i numCourses; i) { graph.add(new ArrayList()); } for (int[] pair : prerequisites) { int a pair[0], b pair[1]; graph.get(b).add(a); indegree[a]; } DequeInteger queue new LinkedList(); for (int i 0; i numCourses; i) { if (indegree[i] 0) { queue.offer(i); } } int visited 0; while (!queue.isEmpty()) { int cur queue.poll(); visited; for (int next : graph.get(cur)) { indegree[next]--; if (indegree[next] 0) { queue.offer(next); } } } return visited numCourses; } }这个模板的巧妙之处在于用visited统计出队节点数如果最终不等于numCourses说明有环存在有些节点永远无法达到入度为0的状态。整个检测过程不需要额外写环判断的逻辑简洁高效。有一个细节建议特别注意BFS的队列建议用Deque或LinkedList的offer和poll方法。用add和remove在队列为空时会抛异常虽然平时刷题不一定会出问题但养成用offer/poll的习惯能避免在边界条件下翻车。我在写代码的时候凡是涉及队列的操作一律使用带有“不抛异常返回特殊值”的版本这个习惯在很多场景帮我省了调试时间。3.4 拓扑排序的变式返回一种修课顺序课程表在hot100里的原题只要求返回布尔值但面试官非常喜欢追加一问如果存在可行顺序请你输出一种具体的修课顺序。这就把题目从207变体升级成了210课程表II。解决办法其实已经在拓扑排序的模板里了。每次从队列中取出一个节点时把它追加到一个结果列表里最终如果visited numCourses就返回这个列表否则返回空数组。整个过程只需要把布尔值替换成列表收集不需要任何算法调整。我当时自己动手扩展练习了一下这道变式最大的收获是加深了对“出队顺序就是拓扑序”的理解。因为BFS保证每个节点都是在所有前驱节点出队之后才入队出队的所以这个顺序天然满足依赖关系。掌握了这部分面试时遇到任何依赖排序相关的问题都可以直接迁移。4. Trie前缀树一种高效的字符串“图”4.1 Trie节点设计的核心思路208实现Trie前缀树是hot100图论区里最特殊的一道题。它的本质是一个多叉树每条边代表一个字符从根到某个节点的路径就构成了一个字符串前缀。它把字符串匹配的时间复杂度从O(n)降到了O(单词长度)非常适合大量字符串的前缀查询场景。理解Trie最简单的方式是把它想象成一部英文字典的结构。字典里的单词“apple”和“apply”有共同的前缀“appl”Trie就把这4个字符的路径复用起来只在最后分流。这样节省了大量存储空间也极大加快了查找速度。Trie的节点设计非常关键。每个节点需要两部分信息一个指向子节点的数组或哈希表以及一个布尔标志位表示“是否存在一个单词在这个节点结束”。对于英文小写字母场景子节点数组长度固定为26用字符减去a得到数组下标这样可以用O(1)时间定位下一个节点。4.2 insert、search、startsWith的实现细节Trie的三种核心操作遵循同一套移动逻辑从根节点出发逐个字符移动只是结尾时的判断条件不同。插入操作是最“朴素”的每遇到一个字符如果当前节点的对应子节点为空就新建一个节点然后把当前节点指针移动到该子节点全部字符处理完后把当前节点的isEnd标记为true。这里有一个细节如果该单词之前已经被插入过isEnd原本就是true再设一遍问题不大但如果两个单词是包含关系比如“apple”和“appl”那么“appl”的最后节点必须有isEnd标记而“apple”继续向下延伸两者互不干扰。查找操作和前缀查找操作的差别在于最终的判断条件。search要求“路径存在且终点节点的isEnd为true”也就是必须是一个完整单词而startsWith只要求“路径存在”不要求isEnd。很多人在实现startsWith时会习惯性地沿用search的代码然后忘了去掉isEnd判断这个bug非常隐蔽。我把这道题刷了三遍每一次都提醒自己search查的是“单词”startsWith查的是“前缀”语义完全不同。还有一个面试高频追问如果字符集不只是26个小写字母而是包含大写字母、数字甚至中文字符节点该怎么设计答案是把数组换成哈希表MapCharacter, TrieNode children。这样虽然查找时多了哈希计算但存储空间更加紧凑。我在实际刷题和面试模拟中被问过不止三次这个扩展问题建议你也能顺手写出哈希表版本。4.3 一个完整的Java实现参考class Trie { private TrieNode root; class TrieNode { TrieNode[] children; boolean isEnd; TrieNode() { children new TrieNode[26]; isEnd false; } } public Trie() { root new TrieNode(); } public void insert(String word) { TrieNode node root; for (char c : word.toCharArray()) { int idx c - a; if (node.children[idx] null) { node.children[idx] new TrieNode(); } node node.children[idx]; } node.isEnd true; } public boolean search(String word) { TrieNode node findNode(word); return node ! null node.isEnd; } public boolean startsWith(String prefix) { TrieNode node findNode(prefix); return node ! null; } private TrieNode findNode(String word) { TrieNode node root; for (char c : word.toCharArray()) { int idx c - a; if (node.children[idx] null) { return null; } node node.children[idx]; } return node; } }把公共的查找路径抽象成findNode方法是这个实现的小亮点。三行代码分别复用查找逻辑代码量更少也会给面试官一种“这个人有工程抽象意识”的感觉。实际运用场景中Trie最常见的两个地方是自动补全和敏感词过滤理解了这208题这两个场景你都能应付。5. 矩阵最长递增路径当DFS遇上记忆化5.1 为什么暴力DFS必超时329矩阵中的最长递增路径从名字就能知道它的核心诉求在一个二维矩阵里从任意一个格子出发你可以向四个方向移动到比当前格子数值更大的相邻格子问最长能走多长。比如一个简单的递增矩阵[[1,2],[3,4]]最长的路径是1-2-4或者1-3-4长度为3。很多人的第一反应是暴力DFS从每个格子出发把所有可能的递增路径都走一遍取最大值。这个做法在3x3的小矩阵上没问题但一旦矩阵到了m x n 200 x 200的量级每个格子的分支都可能蔓延到整个矩阵时间复杂度是指数级的必然超时。问题的根源在于大量的重复计算。假设你先从(0,0)出发向下走到(1,0)再从(1,0)继续探索后面又从(1,0)作为起点去计算一遍两次探索的“从(1,0)出发能走的最长递增路径”其实完全一样。既然一样为什么要算两遍答案自然是不要算两遍。用一个二维数组memo[][]把每个格子的结果缓存起来等下次再经过这个格子时直接返回缓存值。这就是记忆化搜索在DFS的基础上做一次“空间换时间”的优化时间复杂度从指数级直接降到O(m*n)。5.2 递推公式与记忆化搜索的代码实现记忆化搜索的递推思路很直白。用dfs(i, j)表示“以(i,j)为起点能走出的最长递增路径长度”。它的值等于1加上所有“比它大的相邻格子”的dfs值的最大值如果没有相邻的大格子就只是1。class Solution { int[][] matrix; int m, n; int[][] memo; int[][] dirs {{0,1},{0,-1},{1,0},{-1,0}}; public int longestIncreasingPath(int[][] matrix) { this.matrix matrix; m matrix.length; n matrix[0].length; memo new int[m][n]; int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { ans Math.max(ans, dfs(i, j)); } } return ans; } private int dfs(int x, int y) { if (memo[x][y] ! 0) { return memo[x][y]; } int best 1; for (int[] dir : dirs) { int nx x dir[0]; int ny y dir[1]; if (nx 0 nx m ny 0 ny n matrix[nx][ny] matrix[x][y]) { best Math.max(best, 1 dfs(nx, ny)); } } memo[x][y] best; return best; } }这里的memo[x][y] ! 0充当了两个角色的判断一是“是否已经计算过”二是“路径长度是否至少为1”。因为每条合法路径至少长1所以0天然可以作为未计算的初始值。这是一个很巧妙的设计我第一次自己写的时候用了-1做初始化结果还要多写一层for循环填充后悔不已。这道题还有一个容易忽略的点条件中是“递增”strictly greater不是“非递减”。也就是说严格大于才能走等于的格子不能走。这个条件如果看漏了结果会差出很多而且用肉眼非常难排查因为测试用例的小矩阵上可能恰好影响不大但一到大数据量就会暴露。5.3 什么时候用memo什么时候用visited刷到这里很容易把DFS里各种标记混淆。我整理过一个非常清晰的区分准则岛屿数量搜索的目的是把所有节点标记一遍用永久标记visited或原地改值防止回头即可不需要memo。单词搜索搜索的目的是“找到一条合法路径”路径本身不允许复用节点但不同路径之间不能互相干扰所以必须回溯撤销标记。最长递增路径搜索的目的是计算“从每个点出发的最优值”子问题的结构是重叠的所以不仅不需要撤销标记反而必须把结果永久缓存。简单总结状态是否会被多次访问是区分visited和memo的关键。状态一旦被算出来就永远有效用memo状态只对当前递归路径有意义用visited或回溯。想通了这些看到任何DFS题都能快速判断该写哪种搜索形态。6. 刷图论题的常见问题与排查技巧实录6.1 一张问题速查表我自己刷hot100图论题时把遇到的典型问题整理成了下面这张表几乎每一道题翻车的原因都在这里面。问题现象可能原因排查与解决方案岛屿数量重复计数没有在DFS入口标记已访问或标记发生在递归之后进入DFS的第一件事就是修改状态不要等遍历完方向再标记腐烂的橘子分钟数多1每扩散一个节点就加一次时间而不是按层统计在while循环内用size queue.size()固定本层数量处理完再minute单词搜索答案错误回溯时没有正确恢复状态或字符比对的位置不对确保递归返回后立刻撤销标记在DFS入口先判断字符是否匹配课程表死循环邻接表建错方向把[a,b]当成a指向b先修b再修a应该建立b - a的边a的入度加一Trie search误判startsWith和search共用了同一个方法导致isEnd判断缺失search必须检查isEndstartsWith不要检查isEnd各自独立实现最长递增路径超时没有加memo指数级重复计算建立memo数组每个格子一旦算出结果就缓存下次直接读取数组越界边界判断写错位置或方向数组范围不对统一在DFS入口检查边界方向数组固定四个方向不要多写这七类问题是图论hot100题里最高频的坑也是我反复翻车总结出来的。你如果哪道题跑不过优先对照这张表一条条排查比自己盯着代码发愣效率高很多。6.2 两个调试小技巧第一个技巧是善用打印。网格类题目调试时我最常干的事是在DFS入口打印当前的坐标和状态值。比如岛屿数量每次遇到grid[i][j] 1就打印dfs in: i,j能非常直观地看到遍历顺序是不是符合预期。单独靠肉眼盯着递归代码找bug难度极大但把执行路径打印出来问题往往一眼就能看出来。第二个技巧是写一个极小的测试用例。比如矩阵最长递增路径你可以用[[1,2],[3,4]]、[[1,1],[1,1]]这种2x2的用例手动推演一遍观察预期结果跟代码返回值是否一致。这种小用例能暴露绝大多数逻辑错误而且算起来非常快。我习惯把每个用例都用一个单独的测试方法包起来方便反复运行。6.3 如何在面试中展示这组题的能力如果是在准备面试光刷完题不够还得知道怎么“讲”。面试官看重的不是你把代码背下来了而是你有没有能力把思路说清楚。我的建议是每题都练一套固定的表述框架先说暴力思路点出问题在哪再说优化思路说明为什么用DFS或BFS最后说复杂度把时间和空间复杂度都交代清楚。以腐烂的橘子为例你可以这么说先用暴力遍历找所有腐烂橘子把它们加入队列然后用BFS按层扩散每层的时间是一分钟遇到新鲜橘子就腐化并计数最后检查新鲜橘子数量是否为零。同时说明时间复杂度O(mn)每个格子最多入队一次空间复杂度O(mn)队列最大可能装下整个网格。这套表述方式我反复练习了很多次最大的感受是它能展示你的“算法直觉”和“复杂度意识”这两点恰恰是面试官最想看到的。刷题只是入场券能讲清楚才是加分项。6.4 我的最终刷题感悟把hot100的图论题完整刷一遍之后我自己最大的变化是对“图”这个概念有了更立体的认知网格式DFS、邻接表拓扑排序、多叉树Trie、记忆化搜索形态各异但底层逻辑惊人地一致都是在图上做遍历只是对节点的定义不同、对访问状态的管理不同。所以如果你刚开始刷这一组题别害怕那些看似陌生的数据结构多画图多用小样例跑代码把那些模板练到肌肉记忆。等你能闭着眼写出岛屿数量的DFS和课程表的拓扑排序再回头看看这六道题你会发现它们其实只是同一个核心思想披着不同外衣而已。这个系列刷透以后再往后啃hot100里更复杂的题心态会稳很多。