1. 为什么图这一章总让人心里发虚聊到数据结构与算法面试前面数组、链表、栈、队列、哈希表、树这几关大部分人刷一刷还能扛过去。一到图画风就变了题目描述里全是“岛屿”“网络延迟”“课程安排”“单词接龙”看着像语文阅读理解写起来又像在拼乐高。更麻烦的是图不像数组那样有天然的下标顺序也不像树那样有个稳稳的根它是一张网节点之间谁连谁、有没有方向、有没有权重全得你自己在脑子里先建好模型。这篇东西就是冲着这个痛点来的。我把图相关的面试要点重新捋了一遍从“图到底怎么存”到“几大核心算法怎么选”再到“面试官最爱挖的坑在哪”尽量用一线刷题和带人的经验把它讲透。适合谁看如果你已经能写二叉树遍历但一遇到网格搜索、拓扑排序、最短路就卡壳那这篇就是给你准备的。如果你基础还不错也可以拿它当一份查漏补缺的清单看看自己是不是只记住了模板却没搞懂什么时候该用哪个。先说一个我自己的判断图这一章的面试题真正考的不是你背了多少代码而是建模能力和算法选型能力。面试官给你一道题第一步永远是判断这题能不能抽象成图第二步才是选 BFS、DFS、拓扑还是最短路。很多人栽就栽在第一步题目都没翻译成图就开始硬写结果越写越乱。2. 图的存储方式选错了后面全是坑图这东西逻辑上就是“点集 边集”。但落到代码里怎么存直接决定了你后面写起来顺不顺。面试里最常见的就是两种邻接矩阵和邻接表。别看这俩名字简单选错了真的会让你在写 BFS 的时候多绕十分钟。2.1 邻接矩阵适合稠密图但别乱用邻接矩阵就是一个二维数组graph[i][j]表示从节点 i 到节点 j 有没有边或者边的权重是多少。它的好处是查询“i 和 j 之间有没有边”是 O(1)写起来也直观尤其适合节点数不多、边特别密的场景。但它的问题也很明显空间是 O(n²)。如果节点有 10 万个你开一个 10 万乘 10 万的数组内存直接爆炸。而且如果图很稀疏大部分格子都是 0浪费得让人心疼。我见过有人做网格类题目网格是 200×200他非要开一个 40000×40000 的矩阵结果还没跑就挂了。其实网格题根本不需要显式建图直接按坐标上下左右走就行。提示邻接矩阵适合节点数在几百以内、且边比较多的图。面试里如果节点数上千基本可以放弃矩阵直接上邻接表。2.2 邻接表面试里的主力选手邻接表就是每个节点挂一个列表列表里存它所有能到达的邻居。用哈希表或者数组套列表都能实现。它的空间是 O(n m)n 是节点数m 是边数稀疏图下非常省。遍历一个节点的所有邻居也很快正好是 BFS 和 DFS 需要的操作。在 Python 里我一般这么建from collections import defaultdict graph defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) # 无向图才加这一行在 Java 里就是ListListInteger或者MapInteger, ListInteger。如果是带权图列表里存的就不是单个节点而是(邻居, 权重)这样的二元组。这里有个细节很多人会忽略有向图和无向图的建图方式不一样。无向图一条边要加两次有向图只加一次。面试时如果题目说“A 依赖 B”那通常是一条从 B 指向 A 的边方向搞反了拓扑排序直接全错。2.3 什么时候干脆不建图这是我想重点强调的一点。很多图论题尤其是网格类、岛屿类、迷宫类根本不需要你显式地把图建出来。网格本身就是一张图每个格子是一个节点上下左右相邻就是边。你直接用一个visited数组加方向数组[[0,1],[0,-1],[1,0],[-1,0]]就能遍历省时省力还省内存。我个人的经验是只要节点之间的关系是隐式确定的比如坐标相邻、字符串差一个字母就优先考虑不建图直接在原数据结构上做搜索。只有关系是题目额外给的边列表时才老老实实建邻接表。3. 两大基础遍历BFS 和 DFS 到底怎么选图的遍历是所有图算法的地基。BFS 和 DFS 这两兄弟代码都不长但用错场景就是灾难。面试里经常有人问“这题为什么用 BFS 不用 DFS”答不上来就露馅了。3.1 BFS一层一层往外扩天然适合找最短BFS 的核心是队列。你把起点扔进队列然后每次取出一个节点把它的邻居加进去直到队列空。它的特点是按层扩散先访问离起点近的再访问远的。这个特性决定了 BFS 最擅长的场景无权图的最短路径。因为它是按距离一层层扩的第一次遇到目标节点时走过的步数一定是最少的。比如“迷宫最短路径”“单词接龙最少变换次数”“腐烂橘子扩散时间”这些题用 BFS 就是标准答案。写 BFS 有几个坑入队时就标记 visited不要出队才标记。否则同一个节点可能被重复加入队列复杂度直接退化。层数怎么记录。常见做法是在每轮开始前记录当前队列长度一次性处理完这一层层数加一。这样能准确算出最短距离。多源 BFS。有些题起点不止一个比如“腐烂橘子”里所有烂橘子同时开始扩散。做法是把所有起点一次性入队然后正常 BFS效果就是多源同时扩散。from collections import deque def bfs(start, target, graph): queue deque([start]) visited {start} steps 0 while queue: for _ in range(len(queue)): node queue.popleft() if node target: return steps for nxt in graph[node]: if nxt not in visited: visited.add(nxt) queue.append(nxt) steps 1 return -13.2 DFS一条路走到黑适合连通性和回溯DFS 的核心是递归或者栈。它从起点出发沿着一条路一直走走不通了再回头。它的特点是深度优先适合处理连通性、路径枚举、环检测这类问题。DFS 最典型的应用是求连通分量。比如“岛屿数量”你遍历每个格子遇到陆地就 DFS 把整座岛淹掉岛屿计数加一。还有“朋友圈数量”“省份数量”都是同一个套路。DFS 的坑也不少递归深度。如果图很大递归可能爆栈。面试时如果节点数上万最好改成显式栈的迭代写法或者跟面试官确认递归深度是否可接受。visited 的时机。DFS 里通常一进入节点就标记 visited防止绕圈。回溯和 visited 的区别。这是最容易混的地方。如果题目问“是否存在一条路径”用 visited 就行访问过的不用再看。如果题目问“所有路径”或者“排列组合”那要用回溯访问完要撤销标记因为不同路径可以复用同一个节点。3.3 一张表说清 BFS 和 DFS 的选型场景推荐算法原因无权图最短路径BFS按层扩散首次到达即最短连通分量 / 岛屿数量DFS 或 BFS两者都行DFS 代码更短环检测有向图DFS用三色标记法判断后向边环检测无向图DFS 或并查集并查集更直观拓扑排序BFSKahn或 DFS两种都能做所有路径枚举DFS 回溯需要撤销状态多源扩散多源 BFS所有起点同时入队这张表我建议直接记在脑子里。面试时先判断题目属于哪一类再选算法比上来就硬写靠谱得多。4. 拓扑排序有向无环图的排班艺术拓扑排序是图论面试里的高频考点典型题目就是“课程表”“任务调度”“编译顺序”。它的本质是给一个有向无环图DAG的所有节点排个序保证每条边的起点都排在终点前面。4.1 Kahn 算法基于入度的 BFSKahn 算法的思路特别符合直觉先找所有入度为 0 的节点它们没有前置依赖可以最先执行。把它们入队然后依次取出每取出一个就把它的邻居入度减一如果某个邻居入度变成 0说明它的前置都完成了也入队。最后如果输出的节点数等于总节点数说明没有环否则说明有环无法拓扑排序。from collections import deque, defaultdict def topo_sort(n, prerequisites): graph defaultdict(list) indegree [0] * n for course, pre in prerequisites: graph[pre].append(course) indegree[course] 1 queue deque([i for i in range(n) if indegree[i] 0]) order [] while queue: node queue.popleft() order.append(node) for nxt in graph[node]: indegree[nxt] - 1 if indegree[nxt] 0: queue.append(nxt) return order if len(order) n else []Kahn 算法的好处是顺便能检测环。如果最后输出的节点数不够就说明有环。这一点在“课程表”题里经常被考到问你能不能修完所有课其实就是问图有没有环。4.2 DFS 版拓扑排序后序遍历的逆序DFS 也能做拓扑排序。思路是对每个未访问的节点做 DFS在递归返回的时候把节点加入结果列表最后把结果列表反转。这个顺序正好满足拓扑序因为一个节点的所有后继都先于它被加入列表。DFS 版的好处是代码短但检测环稍微麻烦一点需要用三色标记白色未访问、灰色正在访问、黑色已完成。如果在 DFS 过程中遇到灰色节点说明有环。提示面试里如果题目只要求判断有没有环Kahn 算法更直观如果要求输出拓扑序两种都行。我个人更推荐 Kahn因为入度数组的变化过程很清晰不容易写错。4.3 拓扑排序的常见变体拓扑排序不只是“排个序”这么简单面试里经常变形课程表 II要求输出任意一个合法顺序直接返回 Kahn 的结果。课程表 III带权重的课程调度其实已经不是纯拓扑而是贪心加优先队列。外星文字典从单词顺序反推字母顺序本质是建图加拓扑排序。并行课程问最少需要几个学期修完本质是 BFS 的层数。这些变体的核心都是同一件事把依赖关系抽象成有向边然后做拓扑排序。建模建对了剩下的就是套模板。5. 最短路径从无权到带权算法层层升级最短路径是图论里最庞大的一个家族面试里出现的频率极高。但好消息是面试考察的范围其实有限主要就三档无权图、非负权图、以及偶尔出现的负权图。5.1 无权图BFS 就够了无权图的最短路径就是 BFS前面已经讲过。这里补充一个细节BFS 求的是边数最少不是权重最小。如果题目里每条边的代价不一样BFS 就不适用了。5.2 非负权图Dijkstra 是标准答案Dijkstra 算法解决的是边权非负的单源最短路径。它的核心思想是贪心每次从还没确定的节点里选一个当前距离最小的把它确定下来然后用它去松弛它的邻居。朴素版 Dijkstra 是 O(n²)用优先队列优化后是 O((n m) log n)。面试里一般写优先队列版。import heapq def dijkstra(n, graph, start): dist [float(inf)] * n dist[start] 0 heap [(0, start)] while heap: d, node heapq.heappop(heap) if d dist[node]: continue for nxt, w in graph[node]: nd d w if nd dist[nxt]: dist[nxt] nd heapq.heappush(heap, (nd, nxt)) return distDijkstra 有几个必须记住的点不能处理负权边。因为贪心策略假设“当前最小的距离不会再被更新”负权边会打破这个假设。if d dist[node]: continue这行不能省。这是懒删除防止处理过期的堆元素。稠密图用朴素版可能更快。因为优先队列的 log 因子在边特别多时反而拖后腿。5.3 负权图Bellman-Ford 和 SPFA如果图里有负权边Dijkstra 就废了得换 Bellman-Ford。它的思路是对所有边做 n-1 轮松弛每轮都尝试用每条边去更新距离。n-1 轮之后如果还能松弛说明有负环。Bellman-Ford 的复杂度是 O(nm)比较慢。它的优化版是 SPFA用队列来避免无意义的松弛。但 SPFA 在最坏情况下还是 O(nm)而且面试里考得不多了解思路即可。5.4 多源最短路Floyd 一把梭如果题目要求任意两点之间的最短路径而且节点数不多一般 n ≤ 400那就上 Floyd。它的核心是三重循环枚举中间点 k然后更新所有 i 到 j 的距离。def floyd(n, dist): for k in range(n): for i in range(n): for j in range(n): if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return distFloyd 的代码短到离谱但要注意循环顺序不能乱k 必须在最外层。因为它的含义是“只允许经过前 k 个节点作为中间点”k 放里面就错了。算法适用场景复杂度能否负权BFS无权图单源O(n m)不涉及Dijkstra非负权单源O((nm) log n)否Bellman-Ford任意权单源O(nm)是Floyd任意权多源O(n³)是这张表建议背下来。面试时先看题目问的是单源还是多源再看有没有负权基本就能锁定算法。6. 并查集处理连通性的瑞士军刀并查集严格来说不算图算法但它在图论题里出场率极高尤其是“连通分量”“冗余连接”“岛屿数量 II”这类题。它的核心操作就两个find找根和 union合并。6.1 路径压缩 按秩合并并查集要跑得快靠的是两个优化路径压缩find 的时候把沿途所有节点直接挂到根上下次查找就是 O(1)。按秩合并union 的时候把矮的树挂到高的树上避免树退化成链。两个优化一起用均摊复杂度接近 O(1)快得离谱。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[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 if self.rank[rx] self.rank[ry]: self.rank[rx] 1 return True6.2 并查集 vs DFS什么时候用哪个这是很多人纠结的问题。我的经验是如果图是静态的一次性给完所有边DFS 和并查集都行。DFS 代码更直观并查集更短。如果边是动态加入的或者要频繁判断连通性并查集优势明显。因为 DFS 每次都要重新遍历并查集是增量的。如果题目问“最少加几条边能连通”并查集几乎是唯一选择。统计连通分量个数减一就是答案。提示并查集不支持删边。如果题目有删边操作得换思路比如反向加边或者用更复杂的数据结构。7. 面试高频题型拆解与避坑实录前面讲的都是工具这一节讲怎么用。我把图论面试题分成几大类每类给一个典型题和解题思路再附上我踩过的坑。7.1 网格搜索类岛屿、迷宫、腐烂橘子这类题的特点是图是隐式的网格本身就是图。核心套路是遍历每个格子遇到符合条件的就启动 BFS 或 DFS同时用 visited 标记防止重复访问。典型题“岛屿数量”遍历网格遇到1就计数加一然后 DFS 把整座岛变成0。这样下次就不会重复计数。典型题“腐烂橘子”多源 BFS。把所有烂橘子入队然后一层层扩散最后看有没有新鲜橘子剩下。典型题“迷宫最短路径”BFS起点入队每次走上下左右遇到终点返回步数。这类题的坑边界检查。每次走之前都要判断坐标是否越界否则数组越界直接崩。visited 和原数组的关系。有些题可以直接修改原数组当 visited省空间有些题不允许修改就得额外开数组。多源 BFS 的层数。多源 BFS 的层数代表的是“所有源同时扩散的时间”不是单个源的距离。7.2 依赖关系类课程表、任务调度这类题的核心是拓扑排序。把依赖关系建成有向图然后跑 Kahn 或 DFS。典型题“课程表”问能不能修完所有课就是问图有没有环。Kahn 算法最后看输出节点数是否等于总数。典型题“课程表 II”要求输出顺序直接返回 Kahn 的结果。这类题的坑边的方向。“课程 A 依赖课程 B”意味着 B 指向 A别搞反。入度数组的初始化。一定要在加边的时候同步更新入度别漏了。环的判断。Kahn 算法输出节点数不足就是有环这个判断别忘。7.3 最短路径类网络延迟、最小代价这类题的核心是选对最短路算法。无权用 BFS非负权用 Dijkstra多源用 Floyd。典型题“网络延迟时间”从某个节点出发求到所有节点的最短路径然后取最大值。标准 Dijkstra。典型题“最小体力消耗路径”边权是高度差非负用 Dijkstra 或者二分加 BFS。这类题的坑Dijkstra 的懒删除。if d dist[node]: continue这行一定要写否则会处理过期元素。优先队列的排序。Python 的 heapq 是小顶堆存(距离, 节点)元组自动按距离排序。不可达的情况。如果某些节点不可达dist 还是无穷大最后要判断。7.4 连通性类朋友圈、冗余连接这类题的核心是并查集或 DFS。典型题“冗余连接”给一堆边找出一条可以删掉的边使得剩下的图是一棵树。做法是遍历边用并查集判断两个端点是否已经连通如果已经连通这条边就是冗余的。典型题“朋友圈数量”并查集统计连通分量个数。这类题的坑并查集的初始化。parent 数组要初始化为自身。路径压缩的递归写法。递归深度可能很大注意栈溢出。统计连通分量。遍历所有节点看有多少个不同的根。7.5 常见问题速查表问题现象可能原因排查方向结果偏大visited 标记时机不对入队时就标记别出队才标记死循环有环且没标记 visited检查 visited 逻辑最短路径不对用了 DFS 求无权最短路换成 BFSDijkstra 结果错有负权边换 Bellman-Ford拓扑排序结果不全图有环检查入度更新和环判断并查集超时没做路径压缩加上路径压缩和按秩合并网格题越界边界检查漏了每次移动前检查坐标范围这张表是我自己刷题时总结的基本上图论题出错就这几个原因。面试时如果卡住了对照这张表排查能省不少时间。8. 我个人的刷题顺序和实战建议最后聊点实在的。图论这块我建议的刷题顺序是先网格搜索再拓扑排序再最短路最后并查集。因为网格搜索最直观不需要建图容易建立信心拓扑排序套路固定练几道就能掌握最短路算法多需要理解选型并查集代码短但细节多放最后。刷题的时候我强烈建议每道题都先问自己三个问题这题能不能抽象成图节点是什么边是什么是有向还是无向有没有权重要求的是连通性、最短路径、还是拓扑序这三个问题答清楚了算法基本就定了。很多人刷题刷得多但进步慢就是因为只记代码不记选型逻辑换个题面就懵了。还有一个经验图论题一定要动手画图。面试的时候如果允许在纸上把节点和边画出来很多隐藏的环、孤立点、方向问题一眼就能看出来。我见过太多人对着屏幕硬想想了半天没发现图里有个环画出来三秒就明白了。提示面试时如果一时想不出最优解先写一个能跑的暴力解比如 DFS 枚举所有路径。面试官通常更看重你的思路和沟通而不是一上来就写出最优解。先跑通再优化这是更稳妥的策略。图这一章内容确实多但核心就那么几块存储、遍历、拓扑、最短路、并查集。把这几块的模板写熟再理解每种的适用场景面试里遇到图论题就不会心里发虚了。真正拉开差距的从来不是谁背的模板多而是谁能在一堆文字描述里快速看出那张隐藏的图。