第9类题型图论问题背景为什么图论题你总觉得自己会 BFS / DFS一到面试还是容易把题型判断错很多实习面试里的图论题表面根本不写“图”这个字。它可能长成二维矩阵像200. 岛屿数量、994. 腐烂的橘子也可能长成依赖关系像207. 课程表。真正让人失分的地方往往不是代码敲不出来而是你没有在前 30 秒里判断清楚这题的点和边分别是什么。这是在求连通块、最短扩散层数还是在判断有没有环。该用 DFS、BFS还是拓扑排序。如果你现在的状态是“看过图论模板但一遇到矩阵题和依赖题还是会犹豫”那这一类题必须单独练透。读完这篇你至少要把 4 件事固定下来先把题目抽象成图、先决定遍历方式、访问标记要在什么时候打、依赖题要怎么建邻接表和入度表。文章目录第9类题型图论问题背景为什么图论题你总觉得自己会 BFS / DFS一到面试还是容易把题型判断错1. 核心知识点2. 图论题型选择表DFS / BFS / 拓扑排序什么时候用3. 动画辅助理解图论题先建模再决定怎么遍历4. 用样例手推 DFS / 拓扑排序先手推 DFS200. 岛屿数量再手推拓扑排序207. 课程表5. 这类题在面试里考什么6. 高频题清单7. 这类题最容易犯的 4 个错误8. 代表题精讲 1题目思路Java 代码复杂度边界提醒如果这是面试现场你可以这样说9. 代表题精讲 2题目思路Java 代码复杂度边界提醒如果这是面试现场你可以这样说10. 其余题模板与关键片段[994. 腐烂的橘子](https://leetcode.cn/problems/rotting-oranges/)[733. 图像渲染](https://leetcode.cn/problems/flood-fill/)11. 图论题先判断什么12. 错题本记录方式13. 面试前 3 分钟速记14. 快速验证同一套判断能不能落到 200 / 994 / 20715. 本地样例验证结果16. 最后总结图论题真正难的不是模板而是建模速度1. 核心知识点实习面试里的图论最常见的不是 Dijkstra 或 Floyd而是下面 3 类基础模型网格 DFS常见于“数连通块”“把一整片区域染色”。多源 BFS常见于“按层扩散”“求最少几轮传播到位”。拓扑排序常见于“课程依赖”“任务先后关系”“判断是否有环”。你可以先把它们理解成三个固定问法如果题目在问“这一整片算一个块吗”优先想 DFS / BFS。如果题目在问“最少经过几步扩散完成”优先想 BFS。如果题目在问“这些依赖能不能都做完”优先想拓扑排序。2. 图论题型选择表DFS / BFS / 拓扑排序什么时候用题目特征常见问题优先解法你在面试里要先说清楚什么二维矩阵上下左右连通有几个连通块、整片区域是否连通DFS / BFS一个格子是不是一个节点连边规则是什么从多个起点同时扩散最少几轮传播完成、最短层数BFS为什么要按层处理初始队列里有哪些起点课程 / 任务存在先后依赖是否有环、能否完成全部任务拓扑排序邻接表怎么建入度表示什么真正高频的失误不是“不会写”而是“题型选错”200. 岛屿数量本质是数连通块不是在求最短路径。994. 腐烂的橘子本质是多源扩散不适合拿 DFS 去硬做分钟数。207. 课程表本质是判断依赖图里是否有环不是在普通遍历里随便走一遍。3. 动画辅助理解图论题先建模再决定怎么遍历你可以先打开这页分步动画图论建图、入队、访问邻居分步动画这个动画最值得盯住的不是按钮而是 4 个固定动作先说明节点和边怎么定义。再决定起点怎么入栈 / 入队。访问邻居时立刻处理visited避免重复访问。最后根据题目要求统计答案是连通块数量、扩散轮数还是可完成课程数。4. 用样例手推 DFS / 拓扑排序这一节非常重要。图论题如果只看模板不手推状态你在面试里还是容易卡。先手推 DFS200. 岛屿数量样例grid [ [1,1,0,0], [1,0,0,1], [0,0,1,1] ]你可以把每个值为1的格子看成一个陆地节点上下左右相邻就有边。手推过程扫描位置看到什么动作当前岛屿数(0,0)1且未访问岛屿数1从(0,0)开始 DFS把(0,0)、(0,1)、(1,0)全部淹没 / 标记1继续扫描第一、二行已访问陆地或海水跳过1(1,3)1且未访问岛屿数1DFS 扩到(2,3)、(2,2)2扫描结束没有新的未访问陆地返回答案2你在面试里要说清楚的关键点是这题不是“从某个起点找到一条路径”而是“扫描全图遇到新陆地就扩掉整片连通块”。每次 DFS 的目的不是求最短路而是“把这一整片陆地都处理掉避免重复计数”。再手推拓扑排序207. 课程表样例numCourses 4 prerequisites [[1,0],[2,0],[3,1],[3,2]]这表示学1之前先学0学2之前先学0学3之前先学1和2所以邻接表和入度表会变成0 - [1, 2] 1 - [3] 2 - [3] 3 - [] indegree [0, 1, 1, 2]手推过程队列出队课程更新后入度变化已处理课程数[0]01: 1-02: 1-0把1、2入队1[1,2]13: 2-12[2]23: 1-0把3入队3[3]3无后续课程4最后处理课程数等于numCourses说明图里没有环可以学完。你在面试里要强调入度为0的课说明它当前没有前置依赖可以先学。如果图里有环那么环上的课程入度永远不可能全部降到0。所以最后只要比较“处理掉的课程数”和“总课程数”是否相等就能判断能不能学完。5. 这类题在面试里考什么图论题考的不是名词量而是你能不能把题目稳定抽象成“点 边 遍历规则”。面试官通常会看你能不能先判断它是网格图、普通图还是依赖图。你会不会解释为什么该用 DFS、BFS 或拓扑排序。你能不能把visited、邻接表、入度表维护清楚。你是否知道答案统计发生在什么时候是每次发现新连通块时、每一层 BFS 结束时还是拓扑出队时。真正拉开差距的地方在于你不只是把代码敲出来还能解释“为什么这个统计口径正好对应题目要的答案”。6. 高频题清单题目来源难度高频属性200. 岛屿数量LeetCode 热题 100Medium高频994. 腐烂的橘子LeetCode 热题 100Medium高频207. 课程表LeetCode 热题 100Medium高频733. 图像渲染面试经典 150Easy基础高频7. 这类题最容易犯的 4 个错误看到矩阵题没有意识到本质上是网格图。visited标记时机错了导致重复入队或重复 DFS。把“求最少几轮扩散”的题写成 DFS结果分钟数不好统计。课程表不会把依赖关系转成邻接表和入度表。8. 代表题精讲 1题目200. 岛屿数量思路这题本质上是“数二维网格里的连通块数量”。扫描整个矩阵时只要看到一个还没处理过的1就说明发现了一座新岛屿此时答案加一然后从这个格子出发 DFS把整片和它连通的陆地全部标记掉。这样后面再扫到这片区域时就不会重复计数。这题为什么适合 DFS每次进入 DFS目标都是“扩完这一整片连通块”。不需要维护层数也不需要比较最短路径。递归写法足够直接面试里表达也最顺。Java 代码classSolution{privatestaticfinalint[][]DIRS{{1,0},{-1,0},{0,1},{0,-1}};publicintnumIslands(char[][]grid){introwsgrid.length;intcolsgrid[0].length;intislands0;for(introw0;rowrows;row){for(intcol0;colcols;col){if(grid[row][col]1){islands;dfs(grid,row,col);}}}returnislands;}privatevoiddfs(char[][]grid,introw,intcol){if(row0||rowgrid.length||col0||colgrid[0].length){return;}if(grid[row][col]!1){return;}grid[row][col]0;for(int[]dir:DIRS){dfs(grid,rowdir[0],coldir[1]);}}}复杂度时间复杂度O(m * n)空间复杂度递归栈最坏O(m * n)边界提醒这题最容易错的地方有三个忘了在 DFS 里把当前格子标记掉导致重复访问。只从一个起点出发却忘了外层还要扫描整张图。把对角线也当成连通方向结果答案算多。这题默认只看上下左右不看斜对角。这个细节如果面试里不先说容易被追问。如果这是面试现场你可以这样说这题我会把矩阵看成一个网格图每个陆地格子是节点上下左右相邻就有边。扫描矩阵时只要遇到一个还没处理过的1就说明发现了一整片新连通块答案加一然后用 DFS 把这片陆地全部标记掉避免后面重复计数。9. 代表题精讲 2题目207. 课程表思路这题问的是所有课程依赖关系里是否存在环。只要没有环就能完成所有课程。最稳的做法是拓扑排序建邻接表记录一门课学完后能解锁哪些课。统计每门课当前的入度。把所有入度为0的课程入队。每次弹出一门课就把它指向的后续课程入度减一。如果某门课入度减到0说明它现在没有前置依赖了可以入队。最后比较处理课程数和总课程数。Java 代码importjava.util.ArrayDeque;importjava.util.ArrayList;importjava.util.List;importjava.util.Queue;classSolution{publicbooleancanFinish(intnumCourses,int[][]prerequisites){ListListIntegergraphnewArrayList();for(inti0;inumCourses;i){graph.add(newArrayList());}int[]indegreenewint[numCourses];for(int[]edge:prerequisites){intcourseedge[0];intpreedge[1];graph.get(pre).add(course);indegree[course];}QueueIntegerqueuenewArrayDeque();for(inti0;inumCourses;i){if(indegree[i]0){queue.offer(i);}}intfinished0;while(!queue.isEmpty()){intcurrentqueue.poll();finished;for(intnext:graph.get(current)){indegree[next]--;if(indegree[next]0){queue.offer(next);}}}returnfinishednumCourses;}}复杂度时间复杂度O(V E)空间复杂度O(V E)边界提醒这题最容易误判的地方是以为“遍历过所有点”就够了但实际上关键是能不能按依赖顺序不断找到入度为0的点。邻接表方向建反了。这里必须是pre - course表示学完前置课程后才能解锁后续课程。忘了最后比较finished numCourses导致即使有环也返回了true。如果这是面试现场你可以这样说这题本质是在判断依赖图里有没有环。我会用拓扑排序先统计每门课的入度把所有入度为0的课入队再不断出队并更新后续课程的入度。如果最后能处理掉全部课程说明图里没有环否则就说明有课程被环卡住了。10. 其余题模板与关键片段994. 腐烂的橘子这题的关键不是“会不会遍历”而是“为什么必须按层扩散”。所有初始腐烂橘子都要先入队因为它们是同一时刻的多个起点。每处理完一层队列才代表过去了 1 分钟。因此这题优先想多源 BFS而不是 DFS。关键片段while(!queue.isEmpty()fresh0){intsizequeue.size();minutes;for(inti0;isize;i){int[]currentqueue.poll();for(int[]dir:DIRS){intnextRowcurrent[0]dir[0];intnextColcurrent[1]dir[1];if(isFresh(grid,nextRow,nextCol)){grid[nextRow][nextCol]2;fresh--;queue.offer(newint[]{nextRow,nextCol});}}}}733. 图像渲染这题是最基础的网格 DFS / BFS 题。面试里如果你第一次接触图论题往往会先从它开始热身。11. 图论题先判断什么真正动手写代码前你可以先问自己 4 个问题这题里的节点是什么是格子、课程还是普通图节点。边怎么连是上下左右、依赖关系还是邻接关系。题目要的是连通块数量、最短扩散层数还是是否存在环。visited应该在什么时候标记是入队时、出队时还是进入 DFS 时。这 4 个问题一旦先说清楚图论题的大部分思路就已经定下来了。12. 错题本记录方式图论题建议重点记这题里的点和边分别是什么。我为什么判断该用 DFS / BFS / 拓扑排序。visited或入度表是怎么维护的。这题的答案到底是在什么时候统计出来的。13. 面试前 3 分钟速记矩阵上下左右扩散优先想网格图。数连通块常见 DFS / BFS。求最少几轮扩散优先想多源 BFS。课程依赖、先修关系优先想拓扑排序。图题一上来先说节点、边、访问标记。14. 快速验证同一套判断能不能落到 200 / 994 / 207你在面试前可以用下面这张表做最后自检看看自己是不是真的把这类题吃透了题目先识别什么正确做法为什么不是别的做法200. 岛屿数量网格图、数连通块DFS / BFS它不是求最短层数不需要按层统计分钟994. 腐烂的橘子多起点同时扩散多源 BFS题目要最少几分钟天然需要按层推进207. 课程表依赖关系、有无环拓扑排序核心不是遍历所有点而是看能否持续找到入度为0的点如果你能在 30 秒内把这三题都归到正确模型并说明“为什么不用另两种”那这类图论高频题基本就已经掌握到位了。15. 本地样例验证结果为了避免“思路看起来对但代码细节有误”我按文中的200和207代码思路做了本地样例验证输出如下numIslands2 canFinishtrue这两行结果分别对应200. 岛屿数量的手推样例最终得到2座岛。207. 课程表的依赖样例最终可以完成全部课程因此返回true。如果你自己复盘时写出的结果和这里不一致优先检查 3 个地方DFS 是否真的把整片陆地都标记掉了、拓扑排序的边方向有没有建反、入度减到0时有没有及时入队。16. 最后总结图论题真正难的不是模板而是建模速度图论题最容易让人慌的地方是题面不一定直接告诉你“这是图”。但只要你养成固定顺序很多题都会变简单先找节点和边。再判断这是连通块、扩散层数还是依赖有环。然后决定用 DFS、BFS还是拓扑排序。最后明确答案统计发生在什么时候。面试里你只要能把这条链路说顺图论题就不会再只是“背过几个模板”而是真正掌握了这一类题的公共骨架。上期速递【Java实习面试算法冲刺】回溯感谢阅读记得点赞、关注、收藏欢迎各位评论区交流
