1. 从图论专题1到专题5这一路究竟在练什么代码随想录算法训练营走到 day52图论专题5 差不多是整个图论模块里最重要的一次“串讲型”练习。前面专题1到专题4分别解决“图怎么存、图怎么扫、连通块怎么数、集合怎么并”这几个基础问题到了第五专题重点一下子从“模板怎么写”变成了“这个题到底该选哪张模板”。很多人觉得图论难难的其实不是单个算法而是拿到一道题之后不知道应该从 DFS、BFS、并查集、拓扑排序、最短路径还是最小生成树里挑工具挑完之后又不知道边界条件卡在哪。这一天的内容恰好就是把这几张模板放在同一个平面上做对比逼着你开始建立“选题”的意识。我先按自己的理解把前四个专题分别打的基础整理成一张表。这个表不是官方讲义是我自己复盘时做的映射但做完之后再看图论专题5视角会清楚很多也建议你也这样整理一遍。专题主要训练动作应该建立的直觉图论专题1邻接表/邻接矩阵建图DFS、BFS 扫图图怎么表示遍历顺序是什么图论专题2DFS 递归深搜、连通块计数递归边界、方向数组、回溯时机图论专题3BFS 层序扩展、迷宫类最短步数队列弹出时机、visited 入队即置位图论专题4并查集、最小生成树连通性判断、按边权贪心排序图论专题5图论综合应用题根据数据范围倒推算法、识别题眼前四个专题可以理解成“零件加工”第五专题更像“总装车间”。比如专题3里面BFS 的 visited 数组大多数情况下还是一维的限制条件无非是坐标不能越界到了专题5样题里会出现“状态”这个词。同样走一步手上有什么钥匙、当前累积了几种状态、走过哪些点都会影响下一步能不能走所以 visited 必须升级成二维甚至三维。再比如专题4里的并查集通常只是用来判断两个点是否连通或者统计连通分量个数到了第五专题并查集可能会和拓扑排序出现在同一道题的多个子问题里你需要自己决定用并查集判断哪一部分、用 BFS 处理哪一部分。这种“组合感”才是第五专题真正要练的东西。1.1 第五专题真正难在哪我不觉得第五专题难在算法深度而是难在组合维度。给你一道题它可能同时包含多源、带状态、有向、可能有环这几个特征。你如果只熟单一模板就会下意识漏掉其中一个条件。我今年复习时定了一个笨办法每做完一道题就在题目旁边写三行话——这题的节点是什么、边是什么、条件限制了什么。坚持几天之后选算法的速度明显上来了。这个习惯比多刷十道题管用因为每次写三行话都是在强制自己把题目翻译成图论语言。1.2 什么人适合按这份复盘走如果你是跟着训练营往前走的新人建议先把前四个专题的模板敲熟再来读后面的内容否则细节会觉得跳跃。如果你是在准备面试、时间有限的老手可以重点看后面那张决策表拿它自测拿到一道题能不能在五分钟内说出算法选用依据。图论面试题其实很少超纲几乎所有问题都能归到连通性、可达性、有序性、最优性四个大类。第五专题题目的价值正是让你把这四类问题放在一起体会它们的判别方式、适用条件、复杂度差异。2. 建图基本功邻接表、入度表和索引偏移一样都不能错再高级的算法第一步永远是建图。我在复盘图论专题5的错题时发现绝大多数 WA答案错误不是算法选错而是图建错。建图阶段有三个地方特别容易翻车邻接表还是邻接矩阵、入度表怎么维护、索引从 0 开始还是从 1 开始。这三个问题如果没想清楚后面写出来的逻辑会非常拧巴。2.1 邻接表还是邻接矩阵先看两个数字建图先看两个数字节点数 n 和边数 m。如果 n 只有几十并且题目要求任意两点之间关系邻接矩阵最省心判断两点是否直接相连是 O(1)。一旦 n 超过几千邻接矩阵就会出现 n×n 的空间爆炸这个时候必须改成邻接表。训练营里的题目绝大多数都适合邻接表因为面试里的大图问题基本是稀疏图用邻接表存边遍历某个节点的所有邻居总复杂度是 O(nm)比矩阵的 O(n²) 优太多。写邻接表时我踩过一个坑默认把节点编号从 1 开始却把数组长度开成 n。比如节点范围是 1 到 ngraph应该开n1个桶visited、indegree、parent这些配套数组也得跟着开n1。专题5里题目往往带多个数组如果一个数组开n一个开n1运行时不报错结果全错。强烈建议在代码开头写一句注释# 节点编号范围1-based或者# 0-based做完一道题之后回头检查这句话对不对。2.2 入度表是拓扑题的生命线入度这个概念在专题5里出现频率很高尤其是拓扑排序。所谓入度就是有多少条边指向当前节点。维护入度表的时候要注意有向边u - v要同时做两件事把v加进graph[u]把indegree[v] 加 1。很多人在建图阶段只把边存进邻接表忘记维护入度结果后面做拓扑排序时队列永远是空的直接返回空数组。这不是算法问题是建图没建完整。2.3 重复边、自环和孤立点三个隐藏杀手图论专题5的题目里输入不会总是规规矩矩给你一棵树。比如题目说“给定一组边”里面可能包含重复边也就是同样的两个点出现两次。如果你用并查集判环重复边不会产生问题如果你用邻接矩阵重复边会把边长计数搞错。更麻烦的是自环一个点连向自己这在拓扑排序里会直接导致判环失败。处理办法是在读入边的时候如果设置if u v: continue或者if u in graph[v]把重复情况提前过滤。面试和训练营都不太会故意在这个地方刁难你但竞赛题和有些复杂题目会所以养成习惯比较好。孤立点则是另一类问题图里有节点没有出现在边列表里。这时拓扑排序或者 BFS 不能只从边列表去判断有哪些节点得先用数组把所有节点预置进图。常见写法是建图时先循环一遍节点给每个节点先建一个空邻接表再往里加边这样孤立点也会留在图里不会被漏掉。3. 拓扑排序第五专题里性价比最高的模板如果让我选一个图论专题5里最核心的模板我会选拓扑排序。它的应用场景特别多课程安排、编译依赖、任务调度、判断有向图是否有环。而且这个算法的代码量很小思路很固定学会之后能拿分的地方非常多。3.1 Kahn 算法用入度做 BFSKahn 算法的核心思想是每次从图里拿走一个入度为 0 的点。入度为 0 意味着当前没有任何前置依赖可以最先处理处理完之后把它指向的所有邻居的入度减 1如果某个邻居的入度变成 0说明它的前置依赖已经全部完成可以进入下一轮处理。这个过程天然是 BFS。from collections import defaultdict, deque def topological_sort(n, edges): graph defaultdict(list) indegree [0] * n for u, v in edges: graph[u].append(v) indegree[v] 1 queue deque([i for i in range(n) if indegree[i] 0]) result [] while queue: node queue.popleft() result.append(node) for nxt in graph[node]: indegree[nxt] - 1 if indegree[nxt] 0: queue.append(nxt) return result if len(result) n else []这个模板里有三个细节值得注意。第一当入度为 0 的节点不止一个时先处理谁都可以但如果你想要字典序最小的拓扑序列得把普通队列换成优先队列。第二最终result的长度不等于n时说明图里有环因为环上的节点入度永远不可能变成 0永远不会被放进队列。第三入队时机很重要一个节点必须在入度变成 0 的那一刻入队如果在邻居遍历过程中重复入队结果就会出现重复元素。3.2 DFS 三色标记法另一种判环姿势除了 Kahn 算法拓扑排序还有一种 DFS 写法通常叫三色标记法。它的思路是把每个节点标记成三种颜色0 表示还没访问1 表示正在访问2 表示已经访问结束。DFS 过程中如果碰到一个正在访问的节点说明从它出发绕了一圈又回到它自己这就是环。def can_finish(num_courses, prerequisites): graph [[] for _ in range(num_courses)] for a, b in prerequisites: graph[a].append(b) color [0] * num_courses # 0 未访问1 正在访问2 访问完成 def dfs(node): color[node] 1 for nxt in graph[node]: if color[nxt] 1: return False if color[nxt] 0 and not dfs(nxt): return False color[node] 2 return True for i in range(num_courses): if color[i] 0 and not dfs(i): return False return True我个人的习惯是如果题目只要判断能不能完成拓扑排序也就是有没有环用 DFS 三色标记法更直觉如果题目要求输出一个具体的排列顺序用 Kahn 算法更稳。因为 Kahn 算法天然给出序列而 DFS 的完成顺序是逆拓扑序需要反转后才符合“前置任务先完成”的语义新手经常在这里转不过弯。3.3 拓扑排序的常见变体图论专题5的拓扑题不会只考裸模板。最常见的变体是“所有前提条件用边表示但节点编号范围很大”比如节点编号到 10^9不能直接开数组这时要用字典来存图和入度。另一个常见变体是“多个入度为 0 的节点要求输出字典序最小的序列”这时要用堆来替代队列。还有一种变体是“给定一些明确顺序的对判断是否唯一”这种就要在拓扑过程中统计每个时刻队列长度如果任意时刻队列里有超过一个节点说明拓扑序不唯一。变体题其实都在考察同一个本质对入度为 0 这一条件在不同数据结构下的处理。把 Kahn 模板的队列换成堆、换成字典整个思路不会变变的只是排序规则和存储方式。我建议练习时把这三个变体都写一遍写完之后你再看课程表问题、安排课程顺序问题会觉得自己已经看穿了题目。4. 最短路径三件套Dijkstra、SPFA、Floyd 的使用边界图论专题5里最短路径的题也不会少但很多人一看到“最短”两个字就条件反射写 Dijkstra这是很危险的。最短路径算法有适用前提前提不满足时模板越熟练错得越离谱。先把三件套的使用边界说清楚再讨论代码。4.1 Dijkstra 的适用前提图中不能有负权边Dijkstra 的核心逻辑是贪心每次从堆里取出当前距离最小的节点认为这个节点的最短距离已经被确定了。这个结论成立的前提是所有边的权重都不为负。如果存在负权边可能出现一种情况某个节点已经被确定最短距离但之后通过一条负权边到达它的距离更小那贪心结论就失效了。import heapq def dijkstra(graph, start): n len(graph) dist [float(inf)] * n dist[start] 0 heap [(0, start)] while heap: d, node heapq.heappop(heap) if d dist[node]: continue for nxt, weight in graph[node]: nd d weight if nd dist[nxt]: dist[nxt] nd heapq.heappush(heap, (nd, nxt)) return dist堆优化 Dijkstra 的写法有固定套路。if d dist[node]: continue这一句是很多人的痛点它叫懒惰删除因为同一个节点可能会被推入堆多次弹出时如果不是最新最短距离就直接跳过。少了这句话代码也能跑但会多很多无意义的比较多了这句话时间效率会明显提升。对训练营和面试来说这个优化必写。4.2 Bellman-Ford 和 SPFA处理负权边的选项如果图里可能出现负权边Dijkstra 就不能用了。这时有两个选择Bellman-Ford 或者 SPFA。Bellman-Ford 的原理是对所有边反复松弛 n-1 轮。每一轮至少有一个节点的最短距离可以被确定下来。如果第 n 轮还能松弛说明图里有负环最短路径不存在。SPFA 可以理解成 Bellman-Ford 的队列优化版本它只拿被更新过的节点去松弛邻居而不是每一轮都扫所有边。平时写题用到负权边时我常常用 SPFA因为实现简单、常数小。但要说一句实话SPFA 在最坏情况下的复杂度并不好如果题目数据规模很大建议优先确认是否真的存在负权边。考场上的判断逻辑应该是题目没说权值非负就不能用 Dijkstra权值为负但有负环则最短路径问题无解权值可能是浮点数也可以用 Bellman-Ford/SPFA节点数很小比如 100 以内直接用 Floyd因为写起来最简单不容易出错。4.3 Floyd以空间换代码量Floyd 算法是一段几乎不可能写错的三重循环for k in range(n): for i in range(n): for j in range(n): dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])它的典型应用场景是两个第一节点数不超过几百直接暴力求所有点对之间的最短距离第二题目要求最短路径的同时还要判断某个点能否到达另一个点也就是传递闭包问题。Floyd 的优点是代码短、思路直白缺点是 O(n³) 复杂度以及初始化dist[i][i] 0、dist[i][j]初始为inf这些细节。如果题目里存在多条边连接同一对节点初始化时要取权重最小的那条否则后面会被更大权重覆盖出错误结果。4.4 怎么在这三件套之间快速选择我自己的选择顺序是这样的看到最短路径先看数据范围。n 小于 200 时直接无脑 Floyd因为不用考虑负权、多源、复杂数据结构的问题n 在几千时再看权值非负就 Dijkstra 堆优化有负权就 SPFA/Bellman-Fordn 达到十万级图通常是稀疏的而且权值几乎都是非负Dijkstra 是唯一稳妥的选择。这个选择依据不是靠背而是靠复杂度倒推。Dijkstra 堆优化是 O((nm)log n)SPFA 一般快但最坏可能退化成 O(nm)Floyd 是 O(n³)。数据范围只要超过某个量级算法几乎是被逼出来的根本没有自由选择的余地。所以做题时先读 n 和 m再读边的权值这两个信息就能帮你把算法锁定到只剩一个。5. 并查集在图论综合题里的三种升级用法第四专题里我们都在用并查集解决最朴素的连通性问题比如两个节点是否属于同一个集合。到了图论专题5并查集作为辅助工具的出镜率依然很高但它往往是嵌在更复杂的规则里。我总结了三种升级用法对做综合题特别有帮助。5.1 路径压缩加按秩合并模板先背熟并查集的模板在专题5里必须达到默写程度因为很多综合性题目里并查集只是其中一个环节如果这个环节还要现场想怎么写整体节奏就会崩。class DSU: def __init__(self, n): self.parent list(range(n)) self.size [1] * 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, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb] return True我重点说两个容易被忽略的点。第一find里要停顿在self.parent[x] ! x这个条件上路径压缩的关键是让当前节点直接指向根而不是一层一层往上爬。第二union里如果两个根相同返回 False这一步在“判环”场景里尤其有用因为一条边的两个端点如果已经在同一个集合里说明加上这条边就会形成环。5.2 离线倒推删除边问题的反套路有一种题目非常常见初始给定一个图然后不断删除若干条边询问每次删除后整个图是否连通。如果按照正常顺序做每删除一条边就要重新算一遍连通性代价极高。但如果你把操作反过来看从最终状态开始把“删除边”看成“倒着加边”并查集就特别好用。这就是离线倒推法。具体步骤是先把所有要删除的边从图中去掉得到最终状态然后用并查集算出这个最终状态的连通分量个数之后从最后一个操作往前扫描每遇到一次删除操作就在并查集里把这条边加回去同时记录当前连通分量个数。整个过程每个点只被合并一次复杂度接近线性。很多人在这一步卡住是因为觉得“删除边”是并查集不支持的操作。确实并查集很难支持删除但它支持添加。转换视角之后删除问题就变成了添加问题。这种逆向思维是图论专题5非常核心的一种能力值得专门找题练一遍。5.3 并查集处理“类别归属”而不是“点连通”第三种升级用法是让并查集不直接表示点的连通而是表示类别的归属。比如题目里给出一组约束a 和 b 不能放在同一组b 和 c 必须放在同一组。这类“分组约束”问题可以把每个点拆成两个虚拟点“a 在第 1 组”和“a 在第 2 组”再用并查集维护这些虚拟点之间的“必须同类”关系。这种思路也叫“种类并查集”或者“扩展域并查集”。它跟普通并查集的差别只在于建图前要多想一步节点的数量应该翻倍并且每一对约束条件都要映射到对应的虚拟点上。实现时特别容易崩的点是并查集初始化的大小如果原图有 n 个节点扩展域需要 2nparent和size数组也必须开 2n。6. 六类高频变式题的拆题思路前面四章讲的是模板和算法但从“知道模板”到“会做题”之间还有一段距离。这段距离靠的就是怎么把一道题翻译成一个图论模型。我选六个图论专题5里最高频的变式方向逐一说明拆题思路。6.1 多源 BFS把多个起点一起放进队列很多迷宫题不是只有一个起点而是有多个起点同时开始蔓延比如多个腐烂的橘子、多个人同时点火。这类题的套路是把所有起点在初始化时一次性全部放入队列然后正常做 BFS 层序扩展。我第一次做这类题时犯过一个错误只把第一个起点放进队列后来发现结果始终不对。原因很简单多源 BFS 本质上相当于存在一个虚拟超级起点它和所有真实起点都相连边的权重为 0。初始化把所有起点入队就是在模拟这个逻辑。6.2 状态压缩 BFSvisited 从二维变成多维有些迷宫题里钥匙、开关、门这些状态会影响节点是否可走。此时“走到某个位置”并不是一个足够精确的状态你还得记录“手上已经拿到了哪些钥匙”。如果总共有 k 把钥匙可以用一个整数 mask 表示拿钥匙的状态mask 的第 i 位为 1 表示已拿到第 i 把钥匙。visited 数组需要变成visited[x][y][mask]实际实现时可以用二维数组加 mask 维度或者压成一个整数。这种题在训练营里属于进阶但面试里偶尔会出现。它的难点不是 BFS而是想到用位运算表示状态。以后碰到“走过一遍的格子还能再走”的类似描述就要警觉很可能需要状态压缩。普通 visited 数组会把本来可以走通的路线挡在外面。6.3 虚拟节点把多对多的问题拆成一个统一入口某些题目会让你求从若干个候选起点到若干个候选终点的最短距离。如果直接做就是多源 Dijkstra效率不高。一个很常用的转化是建立一个虚拟超级源点把它和所有候选起点相连边权为 0这样原本“多起点到多终点”的问题就变成“一个起点到多个终点”的问题。反过来也可以用虚拟超级汇点把多个终点统一起来。这个技巧不难但很多没经验的人想不到。它本质上是在说建图的时候不一定要严格使用题目给的点你可以自己造点。图论的灵活性就在这里节点和边都是工具只要语义合理就可以为逻辑服务。6.4 最长路径图和树的处理方式完全不同很多人看到“最长路径”四个字第一反应是套最短路径模板。这里必须分清楚如果题目给的是树最长路径可以用两次 DFS 解决因为树是无环连通图路径是唯一的如果题目给的是有向图最长路径一般不能用 Dijkstra 的镜像来做因为负权问题会让贪心失效。有向图上的最长路径简单版本只能用拓扑排序加动态规划复杂版本是 NP 问题。所以在图论专题5里遇到最长路径第一步是确认图到底是不是树这是整个题的题眼。题目如果强调了“树”“无环”“每个节点最多一个父节点”那就是有特殊性质的图可以简化处理如果没有强调就要警惕复杂度。6.5 最小生成树的隐藏问法图论专题5里最小生成树经常不是直接问“最小生成树的权值是多少”而是包装成“让所有点连通的最小代价”“网络铺设最少消耗”之类的话术。识别方式很简单题目想要把若干个点连成一个连通整体边的选择没有方向性最终所有点都在同一个连通块里。看到这三点就可以往最小生成树上想。实现时优先考虑 Kruskal因为它只需要把所有边按权值排序再用并查集依次合并。Kruskal 的复杂度主要消耗在排序上在稀疏图里优势很明显。注意合并过程中要统计成功合并的次数合并到 n-1 次就可以提前结束不需要继续处理后面的边。如果结束后合并次数小于 n-1说明图本来就不连通最小生成树不存在。6.6 贪心陷阱局部最优不等于全局最优第六个变式最抽象也最影响正确率。图论题里很多看起来像贪心的场景其实需要搜索或者动态规划。比如“从左上角走到右下角路径上经过的每个节点都会刷新电量或体力值求最小初始值”这类题很容易让人想到贪心但金币、体力、层数这类资源约束往往会让你现在的选择影响后续状态贪心没法保证全局最优。遇到这类题我的原则是先看状态能不能往后传递如果当前步骤的最优不能直接推出下一步最优就不要贪心改成 BFS 加状态搜索或者动态规划。你能敏感地识别“这里不能贪心”比会写任何模板都重要。7. 做题之前先看这张决策表能少走很多弯路最后把我自己总结的决策表放出来。它不是万能公式但能在拿到题的前几分钟帮你快速定位算法方向避免在错误的赛道上浪费时间。7.1 题型特征到算法的快速映射题目特征首选算法关键判断依据求连通块数量、两点是否连通DFS / BFS / 并查集看是否需要单个起点的完整遍历找图中是否存在环拓扑排序 / 并查集有向图用拓扑无向图用并查集输出一个有先后顺序的序列拓扑排序有向无环图求边权非负的最短路径Dijkstra 堆优化所有权值是否非负存在负权边的最短路径Bellman-Ford / SPFA是否有负环需要检测节点数很小求所有点对最短距离Floydn 小于 200 时最省心把所有点连成一个整体且代价最小Kruskal / Prim并查集合并 n-1 次多个起点同时扩散到网格多源 BFS初始化时把起点全部入队有钥匙、开关等附加状态BFS 状态压缩visited 要包含 mask 维度动态删除边后询问连通性并查集 离线倒推删除变添加反向扫描这张表我贴在训练营笔记本的封面内侧。做题时翻一遍整个过程会顺畅很多。尤其是“无向图判环用并查集、有向图判环用拓扑”这句话我一开始总记反后来发现原因是无向图的环没有方向概念只要有边能连回已经连通的集合就是环有向图则必须考虑方向所以要用入度或者 DFS 颜色去判断。7.2 五个边界条件提交前必查写完代码之后我会习惯性地按下面五条检查一遍。很多图论题的 WA 都出在这五个地方。第一空图能不能跑。n 为 0 或者边列表为空时程序不能崩溃返回值要符合题目语义。第二只有一个节点时入度数组、visited 数组、队列初始化是否正确。第三节点编号是 0 开头还是 1 开头数组大小有没有统一加一。第四自环和重复边有没有被过滤否则后面统计会出错。第五大图下递归深度够不够DFS 是不是应该改成 BFS 或者显式栈。这五条里前三条是新手最容易死的后两条是进阶之后才容易遇到的。建议就把这张清单放在手边每次提交前扫一眼慢慢就会形成条件反射。7.3 个人训练安排上的几个小建议如果让我重新安排 day52 的复习节奏我会这样拆上午先把拓扑排序、Dijkstra、并查集三个模板各默写一遍然后挑一道综合性最高的题把完整拆题过程写下来下午集中做变式题每道题先不急着写代码而是先口头说清楚节点、边、算法、复杂度说得出来再动手晚上整理错题时只记录“审题失误”和“边界漏判”不记录粗粗心心的笔误。这个节奏不一定适合所有人但它帮我解决了最大的问题从“刷题量”转向“解题质量”。图论专题5不是靠题海堆出来的是靠把每个算法适用边界想清楚之后自然产生质变。你如果能做到看到一道题先画图、再选算法、最后才写代码这个专题就算真正吃透了。最后day52 这一天的训练给我最大的体会是图论模块的每一道题都是同一个故事的不同讲法。节点是人物边是关系算法是处理关系的策略。你在训练营里真正积累的不是某道题的答案而是面对一张陌生网络时知道该从哪个角度下手的能力。以后的面试题不管包装成什么场景只要你还能把它的节点、边、权值找出来用哪张模板反而成了最简单的事。 
长河君 · 2026/10/10 8:25:53 · 阅读 1.2k 图论综合题拆解：DFS、BFS、并查集与拓扑排序的算法选择指南
1. 从图论专题1到专题5这一路究竟在练什么代码随想录算法训练营走到 day52图论专题5 差不多是整个图论模块里最重要的一次“串讲型”练习。前面专题1到专题4分别解决“图怎么存、图怎么扫、连通块怎么数、集合怎么并”这几个基础问题到了第五专题重点一下子从“模板怎么写”变成了“这个题到底该选哪张模板”。很多人觉得图论难难的其实不是单个算法而是拿到一道题之后不知道应该从 DFS、BFS、并查集、拓扑排序、最短路径还是最小生成树里挑工具挑完之后又不知道边界条件卡在哪。这一天的内容恰好就是把这几张模板放在同一个平面上做对比逼着你开始建立“选题”的意识。我先按自己的理解把前四个专题分别打的基础整理成一张表。这个表不是官方讲义是我自己复盘时做的映射但做完之后再看图论专题5视角会清楚很多也建议你也这样整理一遍。专题主要训练动作应该建立的直觉图论专题1邻接表/邻接矩阵建图DFS、BFS 扫图图怎么表示遍历顺序是什么图论专题2DFS 递归深搜、连通块计数递归边界、方向数组、回溯时机图论专题3BFS 层序扩展、迷宫类最短步数队列弹出时机、visited 入队即置位图论专题4并查集、最小生成树连通性判断、按边权贪心排序图论专题5图论综合应用题根据数据范围倒推算法、识别题眼前四个专题可以理解成“零件加工”第五专题更像“总装车间”。比如专题3里面BFS 的 visited 数组大多数情况下还是一维的限制条件无非是坐标不能越界到了专题5样题里会出现“状态”这个词。同样走一步手上有什么钥匙、当前累积了几种状态、走过哪些点都会影响下一步能不能走所以 visited 必须升级成二维甚至三维。再比如专题4里的并查集通常只是用来判断两个点是否连通或者统计连通分量个数到了第五专题并查集可能会和拓扑排序出现在同一道题的多个子问题里你需要自己决定用并查集判断哪一部分、用 BFS 处理哪一部分。这种“组合感”才是第五专题真正要练的东西。1.1 第五专题真正难在哪我不觉得第五专题难在算法深度而是难在组合维度。给你一道题它可能同时包含多源、带状态、有向、可能有环这几个特征。你如果只熟单一模板就会下意识漏掉其中一个条件。我今年复习时定了一个笨办法每做完一道题就在题目旁边写三行话——这题的节点是什么、边是什么、条件限制了什么。坚持几天之后选算法的速度明显上来了。这个习惯比多刷十道题管用因为每次写三行话都是在强制自己把题目翻译成图论语言。1.2 什么人适合按这份复盘走如果你是跟着训练营往前走的新人建议先把前四个专题的模板敲熟再来读后面的内容否则细节会觉得跳跃。如果你是在准备面试、时间有限的老手可以重点看后面那张决策表拿它自测拿到一道题能不能在五分钟内说出算法选用依据。图论面试题其实很少超纲几乎所有问题都能归到连通性、可达性、有序性、最优性四个大类。第五专题题目的价值正是让你把这四类问题放在一起体会它们的判别方式、适用条件、复杂度差异。2. 建图基本功邻接表、入度表和索引偏移一样都不能错再高级的算法第一步永远是建图。我在复盘图论专题5的错题时发现绝大多数 WA答案错误不是算法选错而是图建错。建图阶段有三个地方特别容易翻车邻接表还是邻接矩阵、入度表怎么维护、索引从 0 开始还是从 1 开始。这三个问题如果没想清楚后面写出来的逻辑会非常拧巴。2.1 邻接表还是邻接矩阵先看两个数字建图先看两个数字节点数 n 和边数 m。如果 n 只有几十并且题目要求任意两点之间关系邻接矩阵最省心判断两点是否直接相连是 O(1)。一旦 n 超过几千邻接矩阵就会出现 n×n 的空间爆炸这个时候必须改成邻接表。训练营里的题目绝大多数都适合邻接表因为面试里的大图问题基本是稀疏图用邻接表存边遍历某个节点的所有邻居总复杂度是 O(nm)比矩阵的 O(n²) 优太多。写邻接表时我踩过一个坑默认把节点编号从 1 开始却把数组长度开成 n。比如节点范围是 1 到 ngraph应该开n1个桶visited、indegree、parent这些配套数组也得跟着开n1。专题5里题目往往带多个数组如果一个数组开n一个开n1运行时不报错结果全错。强烈建议在代码开头写一句注释# 节点编号范围1-based或者# 0-based做完一道题之后回头检查这句话对不对。2.2 入度表是拓扑题的生命线入度这个概念在专题5里出现频率很高尤其是拓扑排序。所谓入度就是有多少条边指向当前节点。维护入度表的时候要注意有向边u - v要同时做两件事把v加进graph[u]把indegree[v] 加 1。很多人在建图阶段只把边存进邻接表忘记维护入度结果后面做拓扑排序时队列永远是空的直接返回空数组。这不是算法问题是建图没建完整。2.3 重复边、自环和孤立点三个隐藏杀手图论专题5的题目里输入不会总是规规矩矩给你一棵树。比如题目说“给定一组边”里面可能包含重复边也就是同样的两个点出现两次。如果你用并查集判环重复边不会产生问题如果你用邻接矩阵重复边会把边长计数搞错。更麻烦的是自环一个点连向自己这在拓扑排序里会直接导致判环失败。处理办法是在读入边的时候如果设置if u v: continue或者if u in graph[v]把重复情况提前过滤。面试和训练营都不太会故意在这个地方刁难你但竞赛题和有些复杂题目会所以养成习惯比较好。孤立点则是另一类问题图里有节点没有出现在边列表里。这时拓扑排序或者 BFS 不能只从边列表去判断有哪些节点得先用数组把所有节点预置进图。常见写法是建图时先循环一遍节点给每个节点先建一个空邻接表再往里加边这样孤立点也会留在图里不会被漏掉。3. 拓扑排序第五专题里性价比最高的模板如果让我选一个图论专题5里最核心的模板我会选拓扑排序。它的应用场景特别多课程安排、编译依赖、任务调度、判断有向图是否有环。而且这个算法的代码量很小思路很固定学会之后能拿分的地方非常多。3.1 Kahn 算法用入度做 BFSKahn 算法的核心思想是每次从图里拿走一个入度为 0 的点。入度为 0 意味着当前没有任何前置依赖可以最先处理处理完之后把它指向的所有邻居的入度减 1如果某个邻居的入度变成 0说明它的前置依赖已经全部完成可以进入下一轮处理。这个过程天然是 BFS。from collections import defaultdict, deque def topological_sort(n, edges): graph defaultdict(list) indegree [0] * n for u, v in edges: graph[u].append(v) indegree[v] 1 queue deque([i for i in range(n) if indegree[i] 0]) result [] while queue: node queue.popleft() result.append(node) for nxt in graph[node]: indegree[nxt] - 1 if indegree[nxt] 0: queue.append(nxt) return result if len(result) n else []这个模板里有三个细节值得注意。第一当入度为 0 的节点不止一个时先处理谁都可以但如果你想要字典序最小的拓扑序列得把普通队列换成优先队列。第二最终result的长度不等于n时说明图里有环因为环上的节点入度永远不可能变成 0永远不会被放进队列。第三入队时机很重要一个节点必须在入度变成 0 的那一刻入队如果在邻居遍历过程中重复入队结果就会出现重复元素。3.2 DFS 三色标记法另一种判环姿势除了 Kahn 算法拓扑排序还有一种 DFS 写法通常叫三色标记法。它的思路是把每个节点标记成三种颜色0 表示还没访问1 表示正在访问2 表示已经访问结束。DFS 过程中如果碰到一个正在访问的节点说明从它出发绕了一圈又回到它自己这就是环。def can_finish(num_courses, prerequisites): graph [[] for _ in range(num_courses)] for a, b in prerequisites: graph[a].append(b) color [0] * num_courses # 0 未访问1 正在访问2 访问完成 def dfs(node): color[node] 1 for nxt in graph[node]: if color[nxt] 1: return False if color[nxt] 0 and not dfs(nxt): return False color[node] 2 return True for i in range(num_courses): if color[i] 0 and not dfs(i): return False return True我个人的习惯是如果题目只要判断能不能完成拓扑排序也就是有没有环用 DFS 三色标记法更直觉如果题目要求输出一个具体的排列顺序用 Kahn 算法更稳。因为 Kahn 算法天然给出序列而 DFS 的完成顺序是逆拓扑序需要反转后才符合“前置任务先完成”的语义新手经常在这里转不过弯。3.3 拓扑排序的常见变体图论专题5的拓扑题不会只考裸模板。最常见的变体是“所有前提条件用边表示但节点编号范围很大”比如节点编号到 10^9不能直接开数组这时要用字典来存图和入度。另一个常见变体是“多个入度为 0 的节点要求输出字典序最小的序列”这时要用堆来替代队列。还有一种变体是“给定一些明确顺序的对判断是否唯一”这种就要在拓扑过程中统计每个时刻队列长度如果任意时刻队列里有超过一个节点说明拓扑序不唯一。变体题其实都在考察同一个本质对入度为 0 这一条件在不同数据结构下的处理。把 Kahn 模板的队列换成堆、换成字典整个思路不会变变的只是排序规则和存储方式。我建议练习时把这三个变体都写一遍写完之后你再看课程表问题、安排课程顺序问题会觉得自己已经看穿了题目。4. 最短路径三件套Dijkstra、SPFA、Floyd 的使用边界图论专题5里最短路径的题也不会少但很多人一看到“最短”两个字就条件反射写 Dijkstra这是很危险的。最短路径算法有适用前提前提不满足时模板越熟练错得越离谱。先把三件套的使用边界说清楚再讨论代码。4.1 Dijkstra 的适用前提图中不能有负权边Dijkstra 的核心逻辑是贪心每次从堆里取出当前距离最小的节点认为这个节点的最短距离已经被确定了。这个结论成立的前提是所有边的权重都不为负。如果存在负权边可能出现一种情况某个节点已经被确定最短距离但之后通过一条负权边到达它的距离更小那贪心结论就失效了。import heapq def dijkstra(graph, start): n len(graph) dist [float(inf)] * n dist[start] 0 heap [(0, start)] while heap: d, node heapq.heappop(heap) if d dist[node]: continue for nxt, weight in graph[node]: nd d weight if nd dist[nxt]: dist[nxt] nd heapq.heappush(heap, (nd, nxt)) return dist堆优化 Dijkstra 的写法有固定套路。if d dist[node]: continue这一句是很多人的痛点它叫懒惰删除因为同一个节点可能会被推入堆多次弹出时如果不是最新最短距离就直接跳过。少了这句话代码也能跑但会多很多无意义的比较多了这句话时间效率会明显提升。对训练营和面试来说这个优化必写。4.2 Bellman-Ford 和 SPFA处理负权边的选项如果图里可能出现负权边Dijkstra 就不能用了。这时有两个选择Bellman-Ford 或者 SPFA。Bellman-Ford 的原理是对所有边反复松弛 n-1 轮。每一轮至少有一个节点的最短距离可以被确定下来。如果第 n 轮还能松弛说明图里有负环最短路径不存在。SPFA 可以理解成 Bellman-Ford 的队列优化版本它只拿被更新过的节点去松弛邻居而不是每一轮都扫所有边。平时写题用到负权边时我常常用 SPFA因为实现简单、常数小。但要说一句实话SPFA 在最坏情况下的复杂度并不好如果题目数据规模很大建议优先确认是否真的存在负权边。考场上的判断逻辑应该是题目没说权值非负就不能用 Dijkstra权值为负但有负环则最短路径问题无解权值可能是浮点数也可以用 Bellman-Ford/SPFA节点数很小比如 100 以内直接用 Floyd因为写起来最简单不容易出错。4.3 Floyd以空间换代码量Floyd 算法是一段几乎不可能写错的三重循环for k in range(n): for i in range(n): for j in range(n): dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])它的典型应用场景是两个第一节点数不超过几百直接暴力求所有点对之间的最短距离第二题目要求最短路径的同时还要判断某个点能否到达另一个点也就是传递闭包问题。Floyd 的优点是代码短、思路直白缺点是 O(n³) 复杂度以及初始化dist[i][i] 0、dist[i][j]初始为inf这些细节。如果题目里存在多条边连接同一对节点初始化时要取权重最小的那条否则后面会被更大权重覆盖出错误结果。4.4 怎么在这三件套之间快速选择我自己的选择顺序是这样的看到最短路径先看数据范围。n 小于 200 时直接无脑 Floyd因为不用考虑负权、多源、复杂数据结构的问题n 在几千时再看权值非负就 Dijkstra 堆优化有负权就 SPFA/Bellman-Fordn 达到十万级图通常是稀疏的而且权值几乎都是非负Dijkstra 是唯一稳妥的选择。这个选择依据不是靠背而是靠复杂度倒推。Dijkstra 堆优化是 O((nm)log n)SPFA 一般快但最坏可能退化成 O(nm)Floyd 是 O(n³)。数据范围只要超过某个量级算法几乎是被逼出来的根本没有自由选择的余地。所以做题时先读 n 和 m再读边的权值这两个信息就能帮你把算法锁定到只剩一个。5. 并查集在图论综合题里的三种升级用法第四专题里我们都在用并查集解决最朴素的连通性问题比如两个节点是否属于同一个集合。到了图论专题5并查集作为辅助工具的出镜率依然很高但它往往是嵌在更复杂的规则里。我总结了三种升级用法对做综合题特别有帮助。5.1 路径压缩加按秩合并模板先背熟并查集的模板在专题5里必须达到默写程度因为很多综合性题目里并查集只是其中一个环节如果这个环节还要现场想怎么写整体节奏就会崩。class DSU: def __init__(self, n): self.parent list(range(n)) self.size [1] * 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, a, b): ra, rb self.find(a), self.find(b) if ra rb: return False if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb] return True我重点说两个容易被忽略的点。第一find里要停顿在self.parent[x] ! x这个条件上路径压缩的关键是让当前节点直接指向根而不是一层一层往上爬。第二union里如果两个根相同返回 False这一步在“判环”场景里尤其有用因为一条边的两个端点如果已经在同一个集合里说明加上这条边就会形成环。5.2 离线倒推删除边问题的反套路有一种题目非常常见初始给定一个图然后不断删除若干条边询问每次删除后整个图是否连通。如果按照正常顺序做每删除一条边就要重新算一遍连通性代价极高。但如果你把操作反过来看从最终状态开始把“删除边”看成“倒着加边”并查集就特别好用。这就是离线倒推法。具体步骤是先把所有要删除的边从图中去掉得到最终状态然后用并查集算出这个最终状态的连通分量个数之后从最后一个操作往前扫描每遇到一次删除操作就在并查集里把这条边加回去同时记录当前连通分量个数。整个过程每个点只被合并一次复杂度接近线性。很多人在这一步卡住是因为觉得“删除边”是并查集不支持的操作。确实并查集很难支持删除但它支持添加。转换视角之后删除问题就变成了添加问题。这种逆向思维是图论专题5非常核心的一种能力值得专门找题练一遍。5.3 并查集处理“类别归属”而不是“点连通”第三种升级用法是让并查集不直接表示点的连通而是表示类别的归属。比如题目里给出一组约束a 和 b 不能放在同一组b 和 c 必须放在同一组。这类“分组约束”问题可以把每个点拆成两个虚拟点“a 在第 1 组”和“a 在第 2 组”再用并查集维护这些虚拟点之间的“必须同类”关系。这种思路也叫“种类并查集”或者“扩展域并查集”。它跟普通并查集的差别只在于建图前要多想一步节点的数量应该翻倍并且每一对约束条件都要映射到对应的虚拟点上。实现时特别容易崩的点是并查集初始化的大小如果原图有 n 个节点扩展域需要 2nparent和size数组也必须开 2n。6. 六类高频变式题的拆题思路前面四章讲的是模板和算法但从“知道模板”到“会做题”之间还有一段距离。这段距离靠的就是怎么把一道题翻译成一个图论模型。我选六个图论专题5里最高频的变式方向逐一说明拆题思路。6.1 多源 BFS把多个起点一起放进队列很多迷宫题不是只有一个起点而是有多个起点同时开始蔓延比如多个腐烂的橘子、多个人同时点火。这类题的套路是把所有起点在初始化时一次性全部放入队列然后正常做 BFS 层序扩展。我第一次做这类题时犯过一个错误只把第一个起点放进队列后来发现结果始终不对。原因很简单多源 BFS 本质上相当于存在一个虚拟超级起点它和所有真实起点都相连边的权重为 0。初始化把所有起点入队就是在模拟这个逻辑。6.2 状态压缩 BFSvisited 从二维变成多维有些迷宫题里钥匙、开关、门这些状态会影响节点是否可走。此时“走到某个位置”并不是一个足够精确的状态你还得记录“手上已经拿到了哪些钥匙”。如果总共有 k 把钥匙可以用一个整数 mask 表示拿钥匙的状态mask 的第 i 位为 1 表示已拿到第 i 把钥匙。visited 数组需要变成visited[x][y][mask]实际实现时可以用二维数组加 mask 维度或者压成一个整数。这种题在训练营里属于进阶但面试里偶尔会出现。它的难点不是 BFS而是想到用位运算表示状态。以后碰到“走过一遍的格子还能再走”的类似描述就要警觉很可能需要状态压缩。普通 visited 数组会把本来可以走通的路线挡在外面。6.3 虚拟节点把多对多的问题拆成一个统一入口某些题目会让你求从若干个候选起点到若干个候选终点的最短距离。如果直接做就是多源 Dijkstra效率不高。一个很常用的转化是建立一个虚拟超级源点把它和所有候选起点相连边权为 0这样原本“多起点到多终点”的问题就变成“一个起点到多个终点”的问题。反过来也可以用虚拟超级汇点把多个终点统一起来。这个技巧不难但很多没经验的人想不到。它本质上是在说建图的时候不一定要严格使用题目给的点你可以自己造点。图论的灵活性就在这里节点和边都是工具只要语义合理就可以为逻辑服务。6.4 最长路径图和树的处理方式完全不同很多人看到“最长路径”四个字第一反应是套最短路径模板。这里必须分清楚如果题目给的是树最长路径可以用两次 DFS 解决因为树是无环连通图路径是唯一的如果题目给的是有向图最长路径一般不能用 Dijkstra 的镜像来做因为负权问题会让贪心失效。有向图上的最长路径简单版本只能用拓扑排序加动态规划复杂版本是 NP 问题。所以在图论专题5里遇到最长路径第一步是确认图到底是不是树这是整个题的题眼。题目如果强调了“树”“无环”“每个节点最多一个父节点”那就是有特殊性质的图可以简化处理如果没有强调就要警惕复杂度。6.5 最小生成树的隐藏问法图论专题5里最小生成树经常不是直接问“最小生成树的权值是多少”而是包装成“让所有点连通的最小代价”“网络铺设最少消耗”之类的话术。识别方式很简单题目想要把若干个点连成一个连通整体边的选择没有方向性最终所有点都在同一个连通块里。看到这三点就可以往最小生成树上想。实现时优先考虑 Kruskal因为它只需要把所有边按权值排序再用并查集依次合并。Kruskal 的复杂度主要消耗在排序上在稀疏图里优势很明显。注意合并过程中要统计成功合并的次数合并到 n-1 次就可以提前结束不需要继续处理后面的边。如果结束后合并次数小于 n-1说明图本来就不连通最小生成树不存在。6.6 贪心陷阱局部最优不等于全局最优第六个变式最抽象也最影响正确率。图论题里很多看起来像贪心的场景其实需要搜索或者动态规划。比如“从左上角走到右下角路径上经过的每个节点都会刷新电量或体力值求最小初始值”这类题很容易让人想到贪心但金币、体力、层数这类资源约束往往会让你现在的选择影响后续状态贪心没法保证全局最优。遇到这类题我的原则是先看状态能不能往后传递如果当前步骤的最优不能直接推出下一步最优就不要贪心改成 BFS 加状态搜索或者动态规划。你能敏感地识别“这里不能贪心”比会写任何模板都重要。7. 做题之前先看这张决策表能少走很多弯路最后把我自己总结的决策表放出来。它不是万能公式但能在拿到题的前几分钟帮你快速定位算法方向避免在错误的赛道上浪费时间。7.1 题型特征到算法的快速映射题目特征首选算法关键判断依据求连通块数量、两点是否连通DFS / BFS / 并查集看是否需要单个起点的完整遍历找图中是否存在环拓扑排序 / 并查集有向图用拓扑无向图用并查集输出一个有先后顺序的序列拓扑排序有向无环图求边权非负的最短路径Dijkstra 堆优化所有权值是否非负存在负权边的最短路径Bellman-Ford / SPFA是否有负环需要检测节点数很小求所有点对最短距离Floydn 小于 200 时最省心把所有点连成一个整体且代价最小Kruskal / Prim并查集合并 n-1 次多个起点同时扩散到网格多源 BFS初始化时把起点全部入队有钥匙、开关等附加状态BFS 状态压缩visited 要包含 mask 维度动态删除边后询问连通性并查集 离线倒推删除变添加反向扫描这张表我贴在训练营笔记本的封面内侧。做题时翻一遍整个过程会顺畅很多。尤其是“无向图判环用并查集、有向图判环用拓扑”这句话我一开始总记反后来发现原因是无向图的环没有方向概念只要有边能连回已经连通的集合就是环有向图则必须考虑方向所以要用入度或者 DFS 颜色去判断。7.2 五个边界条件提交前必查写完代码之后我会习惯性地按下面五条检查一遍。很多图论题的 WA 都出在这五个地方。第一空图能不能跑。n 为 0 或者边列表为空时程序不能崩溃返回值要符合题目语义。第二只有一个节点时入度数组、visited 数组、队列初始化是否正确。第三节点编号是 0 开头还是 1 开头数组大小有没有统一加一。第四自环和重复边有没有被过滤否则后面统计会出错。第五大图下递归深度够不够DFS 是不是应该改成 BFS 或者显式栈。这五条里前三条是新手最容易死的后两条是进阶之后才容易遇到的。建议就把这张清单放在手边每次提交前扫一眼慢慢就会形成条件反射。7.3 个人训练安排上的几个小建议如果让我重新安排 day52 的复习节奏我会这样拆上午先把拓扑排序、Dijkstra、并查集三个模板各默写一遍然后挑一道综合性最高的题把完整拆题过程写下来下午集中做变式题每道题先不急着写代码而是先口头说清楚节点、边、算法、复杂度说得出来再动手晚上整理错题时只记录“审题失误”和“边界漏判”不记录粗粗心心的笔误。这个节奏不一定适合所有人但它帮我解决了最大的问题从“刷题量”转向“解题质量”。图论专题5不是靠题海堆出来的是靠把每个算法适用边界想清楚之后自然产生质变。你如果能做到看到一道题先画图、再选算法、最后才写代码这个专题就算真正吃透了。最后day52 这一天的训练给我最大的体会是图论模块的每一道题都是同一个故事的不同讲法。节点是人物边是关系算法是处理关系的策略。你在训练营里真正积累的不是某道题的答案而是面对一张陌生网络时知道该从哪个角度下手的能力。以后的面试题不管包装成什么场景只要你还能把它的节点、边、权值找出来用哪张模板反而成了最简单的事。