很多人一刷力扣hot100看到图论这个分类就直接头皮发麻觉得又是图遍历又是连通分量抽象到不行。但实际上hot100里的图论题并没有想象中那么恐怖题型非常集中套路也相对固定我把这些题拆开揉碎看了一遍之后发现真正需要死磕的模型就那么几类。这篇文章就从一个刷题人的视角把力扣hot100图论这部分的核心考点、解题模板、易错细节全部摊开讲清楚希望能给正在刷题或者准备面试的同学一些参考。先把范围说清楚。力扣hot100里面真正属于图论的题目数量不算多但分布很有规律主要围绕岛屿类网格问题、拓扑排序、并查集、图的遍历与深拷贝这几条主线。每一类都有非常成熟的解法模板而且题与题之间的关联度极高常常是同一套思路换了层壳。如果你能把这些核心模型的原理吃透再去做那些“冷门”的图论题会发现它们基本都在已知模型上做的变形不看穿这层壳就会觉得题题都难看穿了就是题题都一样。全文我会先带大家梳理hot100中图论题到底覆盖哪些知识点然后把必背模板写在前面接着按题型拆解每个模型的解题思路和注意事项最后整理一下刷题过程中最常见的坑和排查技巧。内容会比较长建议收藏了慢慢看。1. 力扣hot100里的图论题到底考什么1.1 hot100中的图论题分布与分类我先把hot100里和图论强相关的题目按题型归了个类刷的时候可以对照这份清单看看自己覆盖了没有整理归属分类的大致情况如下岛屿类网格问题200岛屿数量、130被围绕的区域、695岛屿的最大面积、994腐烂的橘子、417太平洋大西洋水流问题图的遍历与拷贝133克隆图拓扑排序207课程表、210课程表Ⅱ图论建模与连通性399除法求值、547省份数量、684冗余连接这个分类不是官方分类是我按解题模型粗分的但它比官方标签看起来更“对症”。同一类题解法模型完全统一比如岛屿类那几道题核心都是grid上的深度优先或广度优先遍历区别只在计数、边界条件、面积统计这些细节上。1.2 为什么hot100偏爱这几类图论题我个人刷下来的感受是hot100在选图论题时非常看重现实生产环境中解决问题的能力而不是纯考背诵性质的高深算法。岛屿类问题本质上考的是用DFS/BFS做网格遍历的能力这种能力在图像处理、游戏地图开发、区域识别等场景下非常常见。拓扑排序考的则是带依赖关系的任务编排你做一个构建系统、一个包管理器、一个编排流程引擎几乎都要碰到这类基于入度的调度问题。另外像并查集这种数据结构它在连通性判断上的应用又直观又实用。省份数量是典型的“朋友圈”式连通块问题冗余连接则是把连通性判断用在“找闭环”入边上这些都是实际编码中频繁遇到的场景。所以hot100不是随便塞了一堆难题进来它挑的图论题都有很强的代表性刷透了这些题面试时再碰到图论题你至少心里有底了。1.3 图论基础概念先扫个盲如果你对图论的基础术语还不是很熟建议先花半小时把这些概念过一遍。图最基本的构成是顶点和边顶点就是节点边就是节点间的关系。边可以有方向有方向的叫有向图没方向的叫无向图边上可以带权重带权重的叫加权图。判断两个节点是否连通、是否存在闭环、是否存在可达路径是图论题目的几个核心问题。在代码里图最常见的存储方式有三种邻接表、邻接矩阵、边列表。邻接表用哈希表或数组记录每个顶点“连接了谁”适合稀疏图邻接矩阵用二维数组记录任意两点间是否有边适合稠密图或顶点数量很少的图边列表则直接用一个数组把所有边存下来适合需要按边处理的场景比如并查集的典型应用冗余连接就是围绕边列表展开的。hot100里大部分题都用邻接表实现少数题如根节点邻接矩阵会直观一些同学们自行取舍。2. 先把这些模板焊死在脑子里2.1 DFS和BFS模板谁是主角要分清图论的很多题都建立在“遍历”基础之上。深度优先搜索DFS和广度优先搜索BFS这两个模板就是整个图论题大厦的地基。DFS的核心写法是递归或显式栈。以递归为例最朴素的模板是进入一个节点后先做处理标记该节点为已访问然后遍历该节点的所有相邻节点如果相邻节点没访问过就递归进入。BFS的核心写法则是用队列先把起点入队并标记然后循环从队首取节点处理它再把它的所有未访问邻居入队。两者最大的区别是DFS一条路走到底再回头适合求连通块、枚举路径BFS一层一层向外扩展天然适合求最短步数、层数相关的问题。我在刷题时最深的体会是很多人DFS写不好是因为递归出口和访问标记没设计好。递归出口就是“当前节点已经处理完了不再深入”的条件访问标记则是“防止同一个节点被重复访问”的手段这两个点没想清楚代码就会乱。在网格类题目里DFS的递归出口通常包括坐标越界和已访问标记的判断缺一不可。2.2 并查集模板连通性问题的万能螺丝刀并查集非常适合解决“判断两个点是否连通”“统计连通分量个数”这类问题。它的基本操作就三个初始化、查找、合并。查找操作负责找到某个节点的根节点合并操作负责把两个节点所在的集合合并。为了防止树退化成一条链查找时要做路径压缩合并时可以用按秩合并这两个优化几乎是标配了。我经常用下面这个精简版模板刷题时直接套没有问题class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * n self.count n # 连通分量数量按需保留 def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx self.rank[rx] self.rank[ry] self.count - 1 return True这段模板中find方法里面的路径压缩是两步一跳的比递归少一点栈溢出的风险性能也不错。union方法返回布尔值如果两个点原本就在同一个集合里返回False这在冗余连接这类题里特别好用因为“这条边是多余的”本质就是“这条边连接的两个点已经连通了”。2.3 拓扑排序模板处理依赖关系不用慌拓扑排序解决的问题是给定一组任务和它们之间的先后依赖关系能否找到一个不冲突的执行顺序。hot100里课程表I和课程表II就是标准原型。课程表I只需要判断能不能完成也就是能不能排出合法顺序课程表II更进一步要求输出任意一种合法顺序。拓扑排序的教科书算法是Kahn算法也就是基于入度表的BFS。思路分四步根据边关系构建邻接表并统计每个顶点的入度。把入度为0的顶点全部加入队列这些顶点是没有前置依赖可以马上完成的任务。从队列中取出顶点把它加入结果序列并“移除”它的出边也就是将相邻顶点的入度减1。如果某个相邻顶点的入度变成0就把它加入队列。循环直到队列为空。队列结束时如果结果序列的长度和顶点总数相等说明拓扑排序成功如果不相等说明图里有环存在循环依赖任务无法完成。这个判断很关键因为很多题不直接说“判断是否有环”而是包装成“是否能完成所有课程”“是否存在合理的选课顺序”本质都是在问拓扑排序是否存在。模板参考如下def canFinish(numCourses, prerequisites): graph [[] for _ in range(numCourses)] indegree [0] * numCourses for a, b in prerequisites: graph[b].append(a) indegree[a] 1 queue [i for i in range(numCourses) if indegree[i] 0] for node in queue: for nxt in graph[node]: indegree[nxt] - 1 if indegree[nxt] 0: queue.append(nxt) return len(queue) numCourses3. 图论题的突破口常见题型拆解3.1 岛屿类网格题组统一解法批量搞定岛屿类题目我给它起了个外号叫“图上开着的小迷宫”它们的共同特点是在一个二维网格上用0和1标记陆地和水域然后要求统计陆地块的数量、最大面积、边界情况等。这类题只要学会一次遍历其他题都是一层薄壳的事。以200岛屿数量为例核心就是扫描整个网格遇到未访问的‘1’就计数加一然后从这个点出发用DFS或BFS把和它相连的所有‘1’全部标成已访问。标访问的方式可以是使用单独visited数组也可以直接原地把格子改成‘0’后者更省空间但会修改原数据看你接受度如何。四个方向的遍历用方向数组写法很优雅出界判断放递归开头就可以。我写过多次的经验是方向数组这样定义dirs [(1, 0), (-1, 0), (0, 1), (0, -1)]然后在DFS里用循环把所有方向都尝试一遍比手写四个嵌套判断要简洁得多减少重复代码的同时也不容易漏方向。130被围绕的区域这道题有个小变化它要求把被‘X’包围的‘O’全改成‘X’但边界上的‘O’及其连通的‘O’要保持原样。这个题的正解是从边界上的‘O’反向标记把所有能连通到边界的‘O’标记出来剩下的‘O’才需要被替换。反过来想很重要正着找“被围住的O”很麻烦反着找“没被围住的O”则简单得多。这种“正难则反”的思想在图论题里出现频率极高值得多体会。3.2 图的拷贝与结构还原好写但细节多133克隆图是hot100图论里有意思的一道题。它给了一个无向连通图要求你深拷贝一份也就是每个节点的值和邻居关系都要独立复制新图与原图在结构上完全一致但不能共用节点。这个题不涉及复杂的算法核心就是遍历原图的同时建立“原节点到新节点的映射关系”并保证每个节点只创建一次。这里最常用的实现思路是用一个哈希表做映射遍历到一个节点时先查哈希表看它是否已经被复制过如果复制过就直接用映射副本没复制过就创建新节点并存入映射然后递归或迭代处理它的邻居。说白了这就是一个“复制节点 建好邻居连接”的过程难点在于别复制出两个“分身”所以每次创建新节点后要立刻记录到哈希表中并且创建时先不急忙处理邻居等遍历到对应边时再补全。很多人在这个题上提交出错是因为递归中重复创建节点或者漏掉已访问标记导致栈溢出或连接不全把往表里塞映射的时机放在创建节点之后马上处理就能避开这种问题。3.3 连通性与环路判断并查集的舒适区547省份数量是并查集的入门应用题。题目给定一个n × n的矩阵isConnected[i][j]1表示城市i和城市j直接相连省份的定义是直接或间接相连的城市集合数量。如果用DFS染色也能做先标记访问过的城市每次没访问过就启动一次深度优先并计数这样一个计数结果就是省份数。但我更推荐并查集方式因为它的语义更直观初始化每个城市自己一个集合遍历矩阵的上三角遇到相连就把两个城市合并最后统计有多少个根节点就能得出省份数量。684冗余连接是并查集判闭环的典型题。场景是一棵树多了一条边要求找出一条可以删除的边使得剩下的图还是一棵树。实现方式非常直接把所有边按顺序依次尝试加入并查集如果某条边的两个端点已经在同一个集合中说明这条边是“多余”的它就是答案。这个解法妙就妙在它是“顺序流”判断符合题目要求的优先级而且不需要额外建图非常省心。3.4 带权并查集与图论建图题hot100里有一道容易被低估的题——399除法求值。它的核心是给出若干除法等式然后求若干带未知数的表达式结果如果无法推导则返回-1。这个问题第一眼看上去不像图论但巧妙建图后就是一个图上的搜索或并查集问题把每个变量当顶点两个变量除法的结果当作一条带权有向边那么求a/b就相当于在图上找从a到b的一条路径并把路径上的权值连乘起来。如果你用并查集实现需要给每个节点维护一个“到根节点的倍率因子”每次合并和查找都要同时更新权重代码会比基础并查集略多但核心思路仍然非常清晰。这种方法在面试里很加分因为遇到问题时能把它抽象成图模型是一种稀缺能力。我刷这题时还总结了一个小经验如果题目的输入是一组“等式关系”输出是一组“查询结果”那么大概率是在考察图论建模你需要先把“如何建图”搞清楚再考虑用什么遍历或数据结构。很多人一开始就想写分式消元其实绕了很远的路。4. 刷图论时踩过的坑全给你列出来4.1 访问标记的时机错一步就崩图论题里最常见的bug就是访问标记的位置写错。BFS时如果你在元素出队时才标记已访问那就糟糕了因为同一个节点可能被多个邻居同时加入队列产生重复处理。正确做法是在节点被加入队列的那一刻就标记已访问。DFS就相对宽容一些因为你进入某个节点后立刻就能判断是否访问过但如果递归前标记晚了也会造成重复递归乃至栈溢出。这个细节很多人起初不重视直到数据一大就超时或者栈溢出回头找问题才意识到。4.2 有向无向别搞混方向处理要想清楚很多题看标题就默认是无向图但实际上可能是带方向的。冗余连接是无向图课程表是有向图岛屿类方向的“四连通”和“八连通”也是区分开了考的hot100里基本都考四连通也就是上下左右对角不算连。但如果题目描述没有明确说明建议默认四连通因为很多国际站题目只对上下左右相邻做处理扩展成八连通就会多算。读题的时候把“相邻”的定义圈出来屡次避免吃亏。4.3 数据范围决定方案暴力并不是不行图论的题有时候数据范围给得不大暴力过表就行。例如部分岛屿题n和m最大只有几十这时候无论DFS还是BFS还是反复扫描都不会超时。但如有些课程表类的题n可能到十万的级别那递归裸DFS就非常容易栈溢出这时候要么显式用栈要么用Kahn算法这类迭代思路。做题第一步应该看看题目给出的数据范围再决定递归深度是否可以接受不要上来就写一个四层递归套娃最后白调半天。4.4 边界判断放在递归第一步网格类DFS在递归函数开头做坐标越界判断这是一个重要习惯。我见过很多新手的代码喜欢在调用递归前就判断各种边界条件结果导致主函数里写一大串if递归函数里再写一小撮if前后不一致导致漏判。统一在递归函数入口做全局判断简洁还不会漏。更关键的是递归的时候你把邻居传进去就算越界了也无所谓直接被递归函数第一行的if拦回来逻辑上非常干净。4.5 并查集的常见错忘记路径压缩或合并计数并查集实现本身很简短但很多人照着模板手写时会把路径压缩或者秩合并的一行丢掉。如果丢了路径压缩查找的复杂度会退化数据一大很容易超时。如果合并时没维护根节点数量或集合大小最终统计连通分量个数时又会出错。不建议自己凭印象写并查集直接用上面那个已经调通的模板或者在理解每一行的作用后删改减少低级错误的概率。4.6 类型与构建细节邻接表别漏了初始化有些题需要你先构建图的邻接表比如课程表构建前要把每个顶点的空列表先初始化好否则后面append时直接空指针或下标越界。还有一种比较隐蔽的错误是节点编号不是从0开始或者输入给的是字符串变量名你需要先做一次节点映射把所有变量名转成数字编号之后再建图否则并查集或邻接表都无从下手。399除法求值就专门在这上面坑人把变量名转数字索引那一步非常关键。这个转换如果不顺后续的一切都会很别扭。4.7 常见问题排查速查表为了方便大家对照自查我整理了一张刷题时的排查速查表现象可能原因排查思路栈溢出/递归层数过深数据范围大、递归无出口、未标记访问改迭代或显式栈检查递归出口和标记时机结果偏大/多统计了数量未去重、把对角线也算成邻接、方向数组多算检查visited标记明确相邻的定义结果偏小/少了连通块漏访问邻居、邻接表构建不全检查循环里是否遍历了所有邻居邻接表是否漏初始化出现环却判断成了合法拓扑排序的计数和顶点总数对比失准确保处理完所有入度为0的节点比较最终计数与顶点总数并查集超时缺少路径压缩/按秩合并补全模板优化尽量用非递归实现答案错位或顺序不符合预期存储边的数组顺序被乱改严格按输入顺序处理不要提前排序除非题目明确要求这张表是我刷了两遍hot100图论题之后总结出来的每次同一个问题反复出现时去看表里对应的行基本能迅速定位。5. 题刷完了下一步怎么规划复习5.1 按题组复盘比按题号刷更高效我自己的刷题习惯是第一遍按题号顺序过第二遍一定按题型归类复盘。比如把岛屿类的几道题放在同一天做做的时候会明显感觉到思路在复用每次只需要调整一个小逻辑比如从统计数量改成统计面积从计数改成染色标记从直接遍历改成反向遍历。按题组复盘还有个好处是能形成“题型直觉”看完题干你脑子里会立刻弹出该套哪个模板而不是跳进细节里去凑代码。按题型分组后我建议至少把每道题的代码重写两遍。第一遍照着模板写目的是“把那层壳给揭掉”第二遍关着代码凭思路写目的是“把模型焊死在脑子里”。图论题很特殊答案的天花板不是你把这道题背下来了而是把这个模型在不同场景下的变形都见过并且理解变形出现的原因。5.2 时间安排建议两周打基础一周刷手感我自己带过几个刷题的朋友针对hot100图论部分给一个我实测下来还不错的安排前两天只看模板和理解基础概念用简单题练手第三天到第八天按上面分的四类题型逐个攻克每天一类遇到卡壳就看题解理解做法第九天到第十二天做第二轮混合刷打乱顺序练快速识别题型的能力后面剩几天专门做错题重写和模拟面试限时训练。这种安排比较稳健不至于一开始就冲难题导致心态崩掉也不会一直在舒适区打转。5.3 复盘时不要只背题要把思路讲出来复盘最有价值的地方在于把复杂思路压缩成自己能讲清楚的话像岛屿数量就是“扫描全图见一数一DFS淹掉”课程表就是“建图数入度拓扑判环”冗余连接就是“按序并查集碰上同根就删除”。这种一句话记忆法对后续复习帮助巨大甚至可以画成示意图或者表格存起来比反复抄代码有性价比得多。图论板块的题更新不多题型也很稳定你把所列模型都吃透了面试和笔试中碰到的绝大多数图论题基本都能落回这些框架里。接下来要做的事情很简单就是动手写。光看永远觉得难真打开编译器一道道码完你会发现一个月前的畏难情绪全是纸老虎。