搜索和图论这块是很多学算法的人又爱又怕的部分。爱的是它跟现实结合得特别紧迷宫寻路、导航规划、网络布线都能用上怕的是概念又多又绕DFS、BFS、最短路、最小生成树听起来像四门课实际上放一起学反而更容易搭出体系感。这篇就按我自己的理解把这几个算法从原理到模板再到避坑完整过一遍希望能给准备面试或者刚入门数据结构的同学一些参考。先交代一下背景我一般会把这讲放在算法课的图谱之后来讲因为图结构本身就靠遍历来驱动而最短路和最小生成树本质上又都是在图这种结构上做优化。换句话说你先把DFS/BFS吃透后面理解最短路、生成树就会顺畅很多它们是同一个思路在不同问题上的延伸。1. 先从整体上拆解这几个算法的关系1.1 图的遍历是所有图论算法的基础不管是最短路也好最小生成树也好第一步都得先能“走”到图的每个节点。而图上的“走法”无非就两种深度优先和广度优先。DFS是一条道走到黑撞了南墙再回头BFS是一层一层往外扩散像水波一样推开。学的时候要有一个很清晰的意识DFS和BFS不只是两个孤立的模板它们解决的是“图能不能被访问到、从一个点能到哪些点”这类连通性问题。我把它们当作整块图论知识的地基来看。比如大家熟悉的拓扑排序用DFS可以写用BFS也能写只是思路不同。再比如无向图的连通分量、有向图的强连通分量本质上也都是DFS的扩展用法。1.2 最短路问题和最小生成树问题的本质区别很多人容易把最短路和最小生成树搞混原因是它们都在求“最小”但对象完全不同。最短路求的是“从a点到b点的最小代价”关心的是路径最小生成树求的是“让所有点连通起来的最小总代价”关心的是边集的取舍。我习惯这样区分如果题目问的是“从某个起点到某个终点的最少花费/最短时间/最少步数”那就是最短路如果题目问的是“要让所有城市通网/通水/通电最少要修多长的线路”那就是最小生成树。一个是单源到单点的局部最优化一个是覆盖全图的全局最优化。再往深了说这两类问题在算法选型上也有很大差异。最短路问题里有单源的Dijkstra也有全源的Floyd最小生成树里有从点出发的Prim也有从边出发的Kruskal。学的时候别急着背模板先把“什么时候用谁”的道理搞清楚下面的代码才不会白抄。1.3 学习路线建议先搜索再最短路最后生成树我上课的习惯是给自己排一条主线先把图的存储方式定下来邻接矩阵、邻接表或者链式前向星接着用DFS/BFS做连通性练习再进入最短路最后才是最小生成树。为什么要这么排因为最短路里要反复进行“松弛操作”本质就是遍历加贪心而Prim算法从写法上看几乎是Dijkstra的孪生兄弟。你把前面基础打牢了后面会发现很多代码模板换个皮就能复用。另外这一讲涉及的算法都对数据规模敏感。比如邻接矩阵存图简单但V到1000以上就开始吃紧优先队列优化的Dijkstra能应付十万级别的点Floyd基本只适合二三百个点的小图。做实战题前一定要先看数据范围这是我踩过无数次坑之后总结出来的第一条铁律。2. 深度优先搜索回溯就是DFS的灵魂2.1 DFS的思维模型一条路走到黑再回头DFS在代码上其实极其简单核心就是递归。每次进入一个节点尝试所有可能的分支如果分支走不通或者走到头了就回到上一个状态继续试别的分支。这个“回到上一个状态”的动作就是回溯。我把DFS的模板写成了固定三步判断当前状态是否满足结束条件满足就记录并返回遍历所有可能的分支逐一尝试每次尝试前做状态标记递归返回后撤销标记在这里第二步和第三步才是重点。递归本身包含了调用栈所以DFS的空间复杂度是O(V)体现在递归深度上但搜索全部方案时时间复杂度往往是O(2^N)甚至O(N!)这是很多人容易忽略的点。如果题目数据范围稍微大一点就要考虑配合剪枝否则跑死也出不来结果。2.2 回溯法的代码模板这里的伪代码我会写得比较通用但放在实际的DFS题目里可以直接套void dfs(当前状态) { if (满足结束条件) { 记录结果; return; } for (每个可能的分支) { 如果分支不合法跳过; 做出选择标记状态; dfs(进入下一层状态); 撤销选择恢复标记; } }这个模板几乎覆盖了全排列、组合、子集、n皇后、岛屿数量这类经典DFS题目。区别只在于“分支的选择”和“状态标记”怎么写。举个例子全排列问题里状态标记是一个used数组当递归到深度等于数组长度时记录答案而n皇后问题的状态标记是列号、主对角线和副对角线的占用情况。这里有个很常见的坑不同题目的“状态撤销”方式可能完全不一样。排列组合类问题通常需要撤销的是布尔数组标记记忆化搜索类问题可能完全不需要撤销。我在初期做题时经常会多写一句撤销反而导致状态错误后来才意识到剪枝和回溯的区别——回溯是“尝试别的可能”剪枝是“提前排除不可能的路径”。2.3 DFS的经典应用从排列组合到图上连通性DFS最常见的入门题是全排列和组合总和这类题练的是对递归层数的控制再往前走一步就是图的连通性问题比如判断一个无向图里有多少个连通分量或者从某个点出发能到达的所有点。其实代码和图的遍历差不多void dfs(int u) { vis[u] true; for (int v : adj[u]) { if (!vis[v]) { dfs(v); } } }这段代码不用回溯因为这里要的是“到达过哪些点”一旦标记了就是访问过了。但它和回溯模板的区别恰好说明了一个重要观点DFS不一定要撤销状态只有当你需要枚举不同路径方案时才必须撤销。这个区分是做DFS题的“分水岭”我见过很多同学在这上面绕很久。2.4 DFS的剪枝技巧写DFS的时候最容易遇到的问题就是超时。本质上是因为搜索空间太大了指数级别的分支数量在一些数据点上根本撑不住。剪枝的思路是在递归早期就判断当前路径是否还有希望走向正确答案如果没有就提前返回。常见的剪枝策略我整理几个可行性剪枝当前路径已经违反约束直接return最优性剪枝即使当前路径继续走完代价也已经超过已知最优解剪掉排序预处理先对候选分支排序把成功率更高的分支放在前面往往能更快找到较优解为剪枝创造机会这些技巧在“组合总和”类问题上特别常用。我第一次遇到组合总和的数据范围加强版时单纯靠回溯会严重超时增加了一个“当前和大于目标值就返回”的判断运行时间直接从不可接受降到几十毫秒。这个教训也说明了一个道理DFS本身是一种暴力枚举的思维方式只有搭配剪枝才能真正落地在工业场景中。3. 广度优先搜索BFS在层级与最短路径中的独特地位3.1 BFS的核心队列与扩散层BFS的逻辑比DFS更贴近人的直觉。它在图上遵循一个严格的顺序先访问起点再访问起点相邻的所有点接着访问它们的相邻点一层一层向外扩展。为了保证这种层序顺序BFS必须借助队列。我用一句话概括BFS的本质越先出队的节点离起点的距离越近且这个距离一定是最短距离前提是图中所有边的权值相同。因此BFS天然适合解决两类问题一类是“最少步数/最短路径”另一类是“层序遍历”比如树的层序遍历、多源扩散模拟。3.2 BFS模板用队列模拟层序推进下面是最标准的BFS模板配套一个dist数组记录到每个点的最短步数void bfs(int s) { queueint q; dist[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { // 未访问过 dist[v] dist[u] 1; q.push(v); } } } }注意这里我用了dist数组来代替vis数组因为用它判断是否访问过的同时还可以顺便记录距离。如果是二维网格上的迷宫问题只需要把“点”打包成坐标数组换成二维即可核心逻辑是一样的。3.3 BFS在最短路径中的经典使用场景BFS最典型的一个应用是“迷宫最短步数”。假设二维迷宫里有起点、终点和若干障碍物每次只能上下左右走一格问从起点到终点最少走多少步。地图规模在几百乘几百的范围内用BFS都非常稳。为什么不用DFS因为DFS找到的第一条路径不一定是最短路径你必须把全部分支都搜完才能确定答案效率很差而BFS的层序扩展天然保证第一次到达终点的路径就是最短路径。另一个被反复拿出来考的场景是“多源BFS”比如多个火源同时蔓延或者多个快递站点同时开始送货要计算某个位置被覆盖到的最早时间。处理方式也简单给队列里一次性塞入所有起点dist数组初始化成0剩下的扩展示意和单源BFS完全一样。3.4 A*算法与BFS的差异先说结论A算法是在BFS基础上加入了启发式评估的升级版。BFS只看当前扩散到哪里完全不管哪个方向更有潜力A则设计一个评估函数 f(n) g(n) h(n)其中g(n)是起点到当前点的实际代价h(n)是当前点到终点的估计代价然后优先扩展f(n)最小的节点。我用一个对比表来看它们的优缺点维度BFSA*算法搜索策略盲目层序扩展启发式优先扩展搜索空间大尤其在复杂地图上更小因为朝目标方向搜索最优性边权相同时保证最优启发函数满足可采纳性时保证最优实现复杂度低中高需维护优先队列与启发函数适用场景迷宫步数、无权图最短路径游戏寻路、大规模地图导航在游戏AI寻路里A基本是标配因为它的搜索范围远小于BFS实时性更好。但BFS的代码简单、思想直观面试里问基础题时出现频率极高。学的时候建议先吃透BFS再往A延伸不要一上来就纠结启发函数怎么设计。实际工程里启发函数往往只用一个曼哈顿距离或欧几里得距离就能取得很好的效果反而是在代码的优先级队列维护上容易出bug。4. 最短路算法单源、多源、全源的全梳理不管你是搞后端、客户端还是算法岗最短路都是绕不开的高频考点。现实中导航、物流配送、社交网络的“几度人脉”背后都能归约成最短路问题。但算法本身有很多口味必要选错了就是在错误的方向上浪费时间。先放一张总览表方便后面展开讲算法适用场景时间复杂度核心思想Dijkstra堆优化非负权图单源最短路O((VE)logV)贪心优先队列Bellman-Ford可处理负权边单源最短路O(VE)松弛n-1轮SPFA负权边的常见选择有负环判断能力玄学平均O(kE)队列优化Bellman-FordFloyd全源最短路点数较少O(V^3)动态规划4.1 Dijkstra贪心思想与堆优化Dijkstra每次从尚未确定最短路的点中挑出当前距离起点最近的点然后用它去尝试更新相邻点的距离。这里最核心的前提是“所有边的权值非负”因为只有这样才能保证当前取出的最近点以后不可能再被其他点更新一旦出队它的最短路就确定了。堆优化就是用优先队列维护候选点。每次更新的代码长这样void dijkstra(int s) { memset(dist, 0x3f, sizeof dist); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }注意一下if (d dist[u]) continue;这行它能过滤掉那些已经被更小距离优化过的旧队列条目。这一行如果漏了算法可能在自己的数据面前乱套这是入坑Dijkstra后最容易犯的错误之一。4.2 Bellman-Ford与SPFA处理负权边Dijkstra解决不了负权边因为一旦有负数边贪心的“当前最近点一定不会被更新”就失效了。比如起点到A点是5起点到B点是10但B到A有一条-6的边A的最短路径实际上是通过B走的4Dijkstra在起点直接取A的态度就会漏掉这个最优解。Bellman-Ford的思路是进行n-1轮松弛每轮遍历所有边尝试用已知的dist[u] w更新dist[v]。因为一条最短路最多包含n-1条边所以反复松弛n-1轮后一定能收敛。如果第n轮还有边能更新那就说明图里存在负环。SPFA是Bellman-Ford的队列优化只有上一轮被更新过的点才有资格更新别人的距离。这样在很多实际图中速度会快很多但复杂度仍然不稳定最坏情况可能会退化到O(VE)挂大数据点的题时心里要有数。4.3 Floyd从动态规划视角看全源最短路Floyd虽然代码短但理解起来更绕。它其实是动态规划dp[k][i][j]表示“只允许经过前k个中间节点时从i到j的最短距离”。状态转移就是要么不经过第k个节点要么经过第k个节点取两者的最小值。写成二维滚动数组后就是大家最熟悉的三层循环for (int k 0; k n; k) { for (int i 0; i n; i) { for (int j 0; j n; j) { dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); } } }这里有个很关键的点k必须放在最外层循环。如果把i和j放在外层dp状态的含义就乱了算出来的结果会出错。这个我在现场debug过好几次都是因为觉得三层循环无所谓顺序结果怎么跑都差几个数。Floyd适合n小于等于300到500的场景因为O(n^3)在1000个点时就开始吃力了。但它实现零门槛既能求任意两点间距离又能顺带做传递闭包在小规模应用题里非常香。4.4 最短路算法怎么选看数据范围和权值符号我自己的选择逻辑是这样的如果权值全非负优先用堆优化的Dijkstra这是性能最好的通用单源方案如果存在负权边但没有负环用Bellman-Ford或SPFA如果只是小规模图点不超过几百个也要求多个点对之间的最短距离直接用Floyd最省事如果明确知道有负环那道题的考点就不再是最短路本身而是负环检测了说实话Dijkstra的出场率远远高于其他两个这是面试题里最常见的考查点。负权相关的题出得不多但一旦出就是区分度很大的题目所以混个眼熟也很重要。5. 最小生成树为什么是“树”并且是“最小”的5.1 最小生成树到底在求什么最小生成树的定义其实很直白在原图上选n-1条边让n个点保持连通同时所有边权之和最小。为什么是n-1条边因为这正好构成一棵树的边数再多一条就会成环少一条就不连通。算法领域里给了个严谨的定义无环且连通则必为一棵树。实际场景很好理解假设一个园区有若干个机房机房之间可能有各种光纤线路但运营商不希望你全铺一遍而是让你挑最省钱的一组线路保证每个机房都能间接或直接连通这就是一个最小生成树问题。5.2 Prim算法从一个点开始“生长”Prim算法的思路特别像Dijkstra初始化时从任意一个点出发把这个点加入生成树集合然后重复n-1次每次从“当前生成树集合”到“集合外”的所有边中挑一条权值最小的边把对应的点加入集合。朴素Prim的代码复杂度是O(V^2)适合稠密图。如果你用邻接矩阵存图维数又不大这个写法最简洁void prim() { memset(lowcost, 0x3f, sizeof lowcost); lowcost[0] 0; for (int i 0; i n; i) { int u -1, minv INF; for (int j 0; j n; j) { if (!vis[j] lowcost[j] minv) { minv lowcost[j]; u j; } } if (u -1) result INF; // 图不连通 vis[u] true; ans minv; for (int v 0; v n; v) { if (!vis[v] g[u][v] lowcost[v]) { lowcost[v] g[u][v]; } } } }这个lowcost数组就是整个Prim的精华它维护的是当前生成树到每个未加入点的最短边权。5.3 Kruskal算法排序 并查集Kruskal的思路和Prim完全相反它直接对边下手。把所有边按权值从小到大排序然后依次遍历如果一条边连接的两个点还不属于同一个集合就把它们合并同时把这条边加入最小生成树。这个“是否属于同一集合”的判断用并查集实现非常自然。int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void kruskal() { sort(edges, edges m); for (int i 0; i m; i) { int a edges[i].u, b edges[i].v, w edges[i].w; int ra find(a), rb find(b); if (ra rb) continue; fa[ra] rb; ans w; cnt; if (cnt n - 1) break; } }这里涉及到并查集的两个核心优化路径压缩和按秩合并。上面的代码里find函数用了路径压缩查询效率会接近常数级别。如果只写一种优化至少要写路径压缩不然大数据下性能堪忧。Kruskal的时间复杂度主要取决于排序O(E log E)所以最擅长处理稀疏图。它的实现也比Prim直观在我个人刷题经验里实战中Kruskal的使用频率要高于Prim。5.4 Prim vs Kruskal什么场景怎么选如果是稠密图比如点只有一两百个但边接近全连那邻接矩阵的Prim写起来很舒服如果是稀疏图比如几万条边分布在几千个点之间直接用Kruskal排序合并会更稳。这两者的选择标准本质上就是稀疏和稠密的问题。算法思路时间复杂度适用场景Prim从点出发每次找集合外最近的点O(V^2) / O(E log V)稠密图Kruskal按边排序用并查集连接点O(E log E)稀疏图6. 实战避坑指南与常见问题排查6.1 建图阶段最容易踩的坑图论题的bug有相当一部分不在算法本身而在建图。先说邻接表存图如果有重边一般要么取最小权值要么直接把多条边全存进去让算法自行处理。如果是邻接矩阵重边处理起来更麻烦必须在读入时就做min操作。还有无向图漏掉双向建边的问题。有些同学在写DFS模板题时记住要add(u,v)和add(v,u)但一旦遇到复杂的题又重新犯错。无向图不建反向边会直接导致所有后续算法跑出来的结果全是错的而且这种错非常隐蔽因为局部数据可能碰巧正确。再提一个细节如果题目给的是字符型节点比如城市名是字符串那最好先离散化成整数。否则每次比较字符串都会拖慢整个算法而且一旦涉及数组大小字符串做不了索引很容易写出晦涩的代码。6.2 搜索过程里的经典BugDFS最容易犯的错有两个一是忘了在递归返回后恢复状态导致后面的分支被前面分支的标记污染二是搞错了结束条件导致输出一堆重复或缺失的答案。BFS则容易在dist数组上翻车忘记把起点置0或忘记把其他点初始化成无限大。还有一个常见问题就是队列无边界控制导致访问越界二维迷宫题里尤其多。我通常会在收尾处写好方向数组和越界判断并且统一用函数封装这样既不会漏判也不会在某个方向写错正负号。多说一句方向数组rowDir和colDir的对应关系一定要仔细dir0时走“上”dir1时走“下”这个顺序在调试时是很折磨人的。6.3 模板与板子之间搞混怎么办我曾经见过有同学把Dijkstra的代码直接拿来做最小生成树的Prim一开始长得很像真跑起来结果全都错了。它们确实在结构上有相似之处但更新逻辑不同Dijkstra用“起点到当前点的距离”更新邻点Prim用“当前生成树到邻点的最小边权”更新lowcost。把两个模板并排放在一起对比着学比死背效果要好得多。同样Kruskal和最短路的Bellman-Ford也都是在处理边的循环但Kruskal是先排序再挑边Bellman-Ford是无序反复松弛。二者混乱的话代码很容易在逻辑上拼出一些“四不像”。我的习惯是每学一个新算法就把它和最相似的那个旧算法做一次对比分析把差异写到注释里。这个习惯帮我省了非常多调试时间。6.4 从题目限制来反推算法面对一道图论题我的破题顺序一般是看数据范围n、m分别到什么级别看权值是否可能为负判断是否适用Dijkstra看题面问的是单源、全源还是全局连通再决定是搜索、最短路还是最小生成树如果n只有几十直接Floyd也行如果n有十万用堆优化Dijkstra是常规操作如果n和m到百万连Dijkstra堆优化都危险这时就要考虑Johnson重标号之类更进阶的思路了不过在算法基础阶段能把上表里那些算法用对用熟已经足够应付绝大多数场景了。7. 最后交个底我自己的学习心得这一讲的内容量确实不小但你要是顺着“图的存储 → DFS/BFS → 最短路 → 最小生成树”这条线走下来会发现它们不是孤立的考点而是一套解决图问题的方法论。每次拿到新题先想它是“问路”还是“连线”再想它符不符合“无负权”的前提最后套模板思路会顺畅非常多。在刚开始刷题的那些日子里我其实特别容易被各种“优化技巧”带走比如看到SPFA就觉得比Bellman-Ford高级看到堆优化就觉得朴素Dijkstra没用。后来踩了些坑才发现能用简单算法解决的问题就不上复杂的代码短、逻辑清楚、不容易写错才是第一位的。先把每一种基础算法写熟再根据题目要求一点点升级这条路走得最稳。希望这份总结能帮正在学图论的你少走一些弯路。
图论算法全解析：DFS、BFS、最短路与最小生成树实战指南
搜索和图论这块是很多学算法的人又爱又怕的部分。爱的是它跟现实结合得特别紧迷宫寻路、导航规划、网络布线都能用上怕的是概念又多又绕DFS、BFS、最短路、最小生成树听起来像四门课实际上放一起学反而更容易搭出体系感。这篇就按我自己的理解把这几个算法从原理到模板再到避坑完整过一遍希望能给准备面试或者刚入门数据结构的同学一些参考。先交代一下背景我一般会把这讲放在算法课的图谱之后来讲因为图结构本身就靠遍历来驱动而最短路和最小生成树本质上又都是在图这种结构上做优化。换句话说你先把DFS/BFS吃透后面理解最短路、生成树就会顺畅很多它们是同一个思路在不同问题上的延伸。1. 先从整体上拆解这几个算法的关系1.1 图的遍历是所有图论算法的基础不管是最短路也好最小生成树也好第一步都得先能“走”到图的每个节点。而图上的“走法”无非就两种深度优先和广度优先。DFS是一条道走到黑撞了南墙再回头BFS是一层一层往外扩散像水波一样推开。学的时候要有一个很清晰的意识DFS和BFS不只是两个孤立的模板它们解决的是“图能不能被访问到、从一个点能到哪些点”这类连通性问题。我把它们当作整块图论知识的地基来看。比如大家熟悉的拓扑排序用DFS可以写用BFS也能写只是思路不同。再比如无向图的连通分量、有向图的强连通分量本质上也都是DFS的扩展用法。1.2 最短路问题和最小生成树问题的本质区别很多人容易把最短路和最小生成树搞混原因是它们都在求“最小”但对象完全不同。最短路求的是“从a点到b点的最小代价”关心的是路径最小生成树求的是“让所有点连通起来的最小总代价”关心的是边集的取舍。我习惯这样区分如果题目问的是“从某个起点到某个终点的最少花费/最短时间/最少步数”那就是最短路如果题目问的是“要让所有城市通网/通水/通电最少要修多长的线路”那就是最小生成树。一个是单源到单点的局部最优化一个是覆盖全图的全局最优化。再往深了说这两类问题在算法选型上也有很大差异。最短路问题里有单源的Dijkstra也有全源的Floyd最小生成树里有从点出发的Prim也有从边出发的Kruskal。学的时候别急着背模板先把“什么时候用谁”的道理搞清楚下面的代码才不会白抄。1.3 学习路线建议先搜索再最短路最后生成树我上课的习惯是给自己排一条主线先把图的存储方式定下来邻接矩阵、邻接表或者链式前向星接着用DFS/BFS做连通性练习再进入最短路最后才是最小生成树。为什么要这么排因为最短路里要反复进行“松弛操作”本质就是遍历加贪心而Prim算法从写法上看几乎是Dijkstra的孪生兄弟。你把前面基础打牢了后面会发现很多代码模板换个皮就能复用。另外这一讲涉及的算法都对数据规模敏感。比如邻接矩阵存图简单但V到1000以上就开始吃紧优先队列优化的Dijkstra能应付十万级别的点Floyd基本只适合二三百个点的小图。做实战题前一定要先看数据范围这是我踩过无数次坑之后总结出来的第一条铁律。2. 深度优先搜索回溯就是DFS的灵魂2.1 DFS的思维模型一条路走到黑再回头DFS在代码上其实极其简单核心就是递归。每次进入一个节点尝试所有可能的分支如果分支走不通或者走到头了就回到上一个状态继续试别的分支。这个“回到上一个状态”的动作就是回溯。我把DFS的模板写成了固定三步判断当前状态是否满足结束条件满足就记录并返回遍历所有可能的分支逐一尝试每次尝试前做状态标记递归返回后撤销标记在这里第二步和第三步才是重点。递归本身包含了调用栈所以DFS的空间复杂度是O(V)体现在递归深度上但搜索全部方案时时间复杂度往往是O(2^N)甚至O(N!)这是很多人容易忽略的点。如果题目数据范围稍微大一点就要考虑配合剪枝否则跑死也出不来结果。2.2 回溯法的代码模板这里的伪代码我会写得比较通用但放在实际的DFS题目里可以直接套void dfs(当前状态) { if (满足结束条件) { 记录结果; return; } for (每个可能的分支) { 如果分支不合法跳过; 做出选择标记状态; dfs(进入下一层状态); 撤销选择恢复标记; } }这个模板几乎覆盖了全排列、组合、子集、n皇后、岛屿数量这类经典DFS题目。区别只在于“分支的选择”和“状态标记”怎么写。举个例子全排列问题里状态标记是一个used数组当递归到深度等于数组长度时记录答案而n皇后问题的状态标记是列号、主对角线和副对角线的占用情况。这里有个很常见的坑不同题目的“状态撤销”方式可能完全不一样。排列组合类问题通常需要撤销的是布尔数组标记记忆化搜索类问题可能完全不需要撤销。我在初期做题时经常会多写一句撤销反而导致状态错误后来才意识到剪枝和回溯的区别——回溯是“尝试别的可能”剪枝是“提前排除不可能的路径”。2.3 DFS的经典应用从排列组合到图上连通性DFS最常见的入门题是全排列和组合总和这类题练的是对递归层数的控制再往前走一步就是图的连通性问题比如判断一个无向图里有多少个连通分量或者从某个点出发能到达的所有点。其实代码和图的遍历差不多void dfs(int u) { vis[u] true; for (int v : adj[u]) { if (!vis[v]) { dfs(v); } } }这段代码不用回溯因为这里要的是“到达过哪些点”一旦标记了就是访问过了。但它和回溯模板的区别恰好说明了一个重要观点DFS不一定要撤销状态只有当你需要枚举不同路径方案时才必须撤销。这个区分是做DFS题的“分水岭”我见过很多同学在这上面绕很久。2.4 DFS的剪枝技巧写DFS的时候最容易遇到的问题就是超时。本质上是因为搜索空间太大了指数级别的分支数量在一些数据点上根本撑不住。剪枝的思路是在递归早期就判断当前路径是否还有希望走向正确答案如果没有就提前返回。常见的剪枝策略我整理几个可行性剪枝当前路径已经违反约束直接return最优性剪枝即使当前路径继续走完代价也已经超过已知最优解剪掉排序预处理先对候选分支排序把成功率更高的分支放在前面往往能更快找到较优解为剪枝创造机会这些技巧在“组合总和”类问题上特别常用。我第一次遇到组合总和的数据范围加强版时单纯靠回溯会严重超时增加了一个“当前和大于目标值就返回”的判断运行时间直接从不可接受降到几十毫秒。这个教训也说明了一个道理DFS本身是一种暴力枚举的思维方式只有搭配剪枝才能真正落地在工业场景中。3. 广度优先搜索BFS在层级与最短路径中的独特地位3.1 BFS的核心队列与扩散层BFS的逻辑比DFS更贴近人的直觉。它在图上遵循一个严格的顺序先访问起点再访问起点相邻的所有点接着访问它们的相邻点一层一层向外扩展。为了保证这种层序顺序BFS必须借助队列。我用一句话概括BFS的本质越先出队的节点离起点的距离越近且这个距离一定是最短距离前提是图中所有边的权值相同。因此BFS天然适合解决两类问题一类是“最少步数/最短路径”另一类是“层序遍历”比如树的层序遍历、多源扩散模拟。3.2 BFS模板用队列模拟层序推进下面是最标准的BFS模板配套一个dist数组记录到每个点的最短步数void bfs(int s) { queueint q; dist[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { // 未访问过 dist[v] dist[u] 1; q.push(v); } } } }注意这里我用了dist数组来代替vis数组因为用它判断是否访问过的同时还可以顺便记录距离。如果是二维网格上的迷宫问题只需要把“点”打包成坐标数组换成二维即可核心逻辑是一样的。3.3 BFS在最短路径中的经典使用场景BFS最典型的一个应用是“迷宫最短步数”。假设二维迷宫里有起点、终点和若干障碍物每次只能上下左右走一格问从起点到终点最少走多少步。地图规模在几百乘几百的范围内用BFS都非常稳。为什么不用DFS因为DFS找到的第一条路径不一定是最短路径你必须把全部分支都搜完才能确定答案效率很差而BFS的层序扩展天然保证第一次到达终点的路径就是最短路径。另一个被反复拿出来考的场景是“多源BFS”比如多个火源同时蔓延或者多个快递站点同时开始送货要计算某个位置被覆盖到的最早时间。处理方式也简单给队列里一次性塞入所有起点dist数组初始化成0剩下的扩展示意和单源BFS完全一样。3.4 A*算法与BFS的差异先说结论A算法是在BFS基础上加入了启发式评估的升级版。BFS只看当前扩散到哪里完全不管哪个方向更有潜力A则设计一个评估函数 f(n) g(n) h(n)其中g(n)是起点到当前点的实际代价h(n)是当前点到终点的估计代价然后优先扩展f(n)最小的节点。我用一个对比表来看它们的优缺点维度BFSA*算法搜索策略盲目层序扩展启发式优先扩展搜索空间大尤其在复杂地图上更小因为朝目标方向搜索最优性边权相同时保证最优启发函数满足可采纳性时保证最优实现复杂度低中高需维护优先队列与启发函数适用场景迷宫步数、无权图最短路径游戏寻路、大规模地图导航在游戏AI寻路里A基本是标配因为它的搜索范围远小于BFS实时性更好。但BFS的代码简单、思想直观面试里问基础题时出现频率极高。学的时候建议先吃透BFS再往A延伸不要一上来就纠结启发函数怎么设计。实际工程里启发函数往往只用一个曼哈顿距离或欧几里得距离就能取得很好的效果反而是在代码的优先级队列维护上容易出bug。4. 最短路算法单源、多源、全源的全梳理不管你是搞后端、客户端还是算法岗最短路都是绕不开的高频考点。现实中导航、物流配送、社交网络的“几度人脉”背后都能归约成最短路问题。但算法本身有很多口味必要选错了就是在错误的方向上浪费时间。先放一张总览表方便后面展开讲算法适用场景时间复杂度核心思想Dijkstra堆优化非负权图单源最短路O((VE)logV)贪心优先队列Bellman-Ford可处理负权边单源最短路O(VE)松弛n-1轮SPFA负权边的常见选择有负环判断能力玄学平均O(kE)队列优化Bellman-FordFloyd全源最短路点数较少O(V^3)动态规划4.1 Dijkstra贪心思想与堆优化Dijkstra每次从尚未确定最短路的点中挑出当前距离起点最近的点然后用它去尝试更新相邻点的距离。这里最核心的前提是“所有边的权值非负”因为只有这样才能保证当前取出的最近点以后不可能再被其他点更新一旦出队它的最短路就确定了。堆优化就是用优先队列维护候选点。每次更新的代码长这样void dijkstra(int s) { memset(dist, 0x3f, sizeof dist); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }注意一下if (d dist[u]) continue;这行它能过滤掉那些已经被更小距离优化过的旧队列条目。这一行如果漏了算法可能在自己的数据面前乱套这是入坑Dijkstra后最容易犯的错误之一。4.2 Bellman-Ford与SPFA处理负权边Dijkstra解决不了负权边因为一旦有负数边贪心的“当前最近点一定不会被更新”就失效了。比如起点到A点是5起点到B点是10但B到A有一条-6的边A的最短路径实际上是通过B走的4Dijkstra在起点直接取A的态度就会漏掉这个最优解。Bellman-Ford的思路是进行n-1轮松弛每轮遍历所有边尝试用已知的dist[u] w更新dist[v]。因为一条最短路最多包含n-1条边所以反复松弛n-1轮后一定能收敛。如果第n轮还有边能更新那就说明图里存在负环。SPFA是Bellman-Ford的队列优化只有上一轮被更新过的点才有资格更新别人的距离。这样在很多实际图中速度会快很多但复杂度仍然不稳定最坏情况可能会退化到O(VE)挂大数据点的题时心里要有数。4.3 Floyd从动态规划视角看全源最短路Floyd虽然代码短但理解起来更绕。它其实是动态规划dp[k][i][j]表示“只允许经过前k个中间节点时从i到j的最短距离”。状态转移就是要么不经过第k个节点要么经过第k个节点取两者的最小值。写成二维滚动数组后就是大家最熟悉的三层循环for (int k 0; k n; k) { for (int i 0; i n; i) { for (int j 0; j n; j) { dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); } } }这里有个很关键的点k必须放在最外层循环。如果把i和j放在外层dp状态的含义就乱了算出来的结果会出错。这个我在现场debug过好几次都是因为觉得三层循环无所谓顺序结果怎么跑都差几个数。Floyd适合n小于等于300到500的场景因为O(n^3)在1000个点时就开始吃力了。但它实现零门槛既能求任意两点间距离又能顺带做传递闭包在小规模应用题里非常香。4.4 最短路算法怎么选看数据范围和权值符号我自己的选择逻辑是这样的如果权值全非负优先用堆优化的Dijkstra这是性能最好的通用单源方案如果存在负权边但没有负环用Bellman-Ford或SPFA如果只是小规模图点不超过几百个也要求多个点对之间的最短距离直接用Floyd最省事如果明确知道有负环那道题的考点就不再是最短路本身而是负环检测了说实话Dijkstra的出场率远远高于其他两个这是面试题里最常见的考查点。负权相关的题出得不多但一旦出就是区分度很大的题目所以混个眼熟也很重要。5. 最小生成树为什么是“树”并且是“最小”的5.1 最小生成树到底在求什么最小生成树的定义其实很直白在原图上选n-1条边让n个点保持连通同时所有边权之和最小。为什么是n-1条边因为这正好构成一棵树的边数再多一条就会成环少一条就不连通。算法领域里给了个严谨的定义无环且连通则必为一棵树。实际场景很好理解假设一个园区有若干个机房机房之间可能有各种光纤线路但运营商不希望你全铺一遍而是让你挑最省钱的一组线路保证每个机房都能间接或直接连通这就是一个最小生成树问题。5.2 Prim算法从一个点开始“生长”Prim算法的思路特别像Dijkstra初始化时从任意一个点出发把这个点加入生成树集合然后重复n-1次每次从“当前生成树集合”到“集合外”的所有边中挑一条权值最小的边把对应的点加入集合。朴素Prim的代码复杂度是O(V^2)适合稠密图。如果你用邻接矩阵存图维数又不大这个写法最简洁void prim() { memset(lowcost, 0x3f, sizeof lowcost); lowcost[0] 0; for (int i 0; i n; i) { int u -1, minv INF; for (int j 0; j n; j) { if (!vis[j] lowcost[j] minv) { minv lowcost[j]; u j; } } if (u -1) result INF; // 图不连通 vis[u] true; ans minv; for (int v 0; v n; v) { if (!vis[v] g[u][v] lowcost[v]) { lowcost[v] g[u][v]; } } } }这个lowcost数组就是整个Prim的精华它维护的是当前生成树到每个未加入点的最短边权。5.3 Kruskal算法排序 并查集Kruskal的思路和Prim完全相反它直接对边下手。把所有边按权值从小到大排序然后依次遍历如果一条边连接的两个点还不属于同一个集合就把它们合并同时把这条边加入最小生成树。这个“是否属于同一集合”的判断用并查集实现非常自然。int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void kruskal() { sort(edges, edges m); for (int i 0; i m; i) { int a edges[i].u, b edges[i].v, w edges[i].w; int ra find(a), rb find(b); if (ra rb) continue; fa[ra] rb; ans w; cnt; if (cnt n - 1) break; } }这里涉及到并查集的两个核心优化路径压缩和按秩合并。上面的代码里find函数用了路径压缩查询效率会接近常数级别。如果只写一种优化至少要写路径压缩不然大数据下性能堪忧。Kruskal的时间复杂度主要取决于排序O(E log E)所以最擅长处理稀疏图。它的实现也比Prim直观在我个人刷题经验里实战中Kruskal的使用频率要高于Prim。5.4 Prim vs Kruskal什么场景怎么选如果是稠密图比如点只有一两百个但边接近全连那邻接矩阵的Prim写起来很舒服如果是稀疏图比如几万条边分布在几千个点之间直接用Kruskal排序合并会更稳。这两者的选择标准本质上就是稀疏和稠密的问题。算法思路时间复杂度适用场景Prim从点出发每次找集合外最近的点O(V^2) / O(E log V)稠密图Kruskal按边排序用并查集连接点O(E log E)稀疏图6. 实战避坑指南与常见问题排查6.1 建图阶段最容易踩的坑图论题的bug有相当一部分不在算法本身而在建图。先说邻接表存图如果有重边一般要么取最小权值要么直接把多条边全存进去让算法自行处理。如果是邻接矩阵重边处理起来更麻烦必须在读入时就做min操作。还有无向图漏掉双向建边的问题。有些同学在写DFS模板题时记住要add(u,v)和add(v,u)但一旦遇到复杂的题又重新犯错。无向图不建反向边会直接导致所有后续算法跑出来的结果全是错的而且这种错非常隐蔽因为局部数据可能碰巧正确。再提一个细节如果题目给的是字符型节点比如城市名是字符串那最好先离散化成整数。否则每次比较字符串都会拖慢整个算法而且一旦涉及数组大小字符串做不了索引很容易写出晦涩的代码。6.2 搜索过程里的经典BugDFS最容易犯的错有两个一是忘了在递归返回后恢复状态导致后面的分支被前面分支的标记污染二是搞错了结束条件导致输出一堆重复或缺失的答案。BFS则容易在dist数组上翻车忘记把起点置0或忘记把其他点初始化成无限大。还有一个常见问题就是队列无边界控制导致访问越界二维迷宫题里尤其多。我通常会在收尾处写好方向数组和越界判断并且统一用函数封装这样既不会漏判也不会在某个方向写错正负号。多说一句方向数组rowDir和colDir的对应关系一定要仔细dir0时走“上”dir1时走“下”这个顺序在调试时是很折磨人的。6.3 模板与板子之间搞混怎么办我曾经见过有同学把Dijkstra的代码直接拿来做最小生成树的Prim一开始长得很像真跑起来结果全都错了。它们确实在结构上有相似之处但更新逻辑不同Dijkstra用“起点到当前点的距离”更新邻点Prim用“当前生成树到邻点的最小边权”更新lowcost。把两个模板并排放在一起对比着学比死背效果要好得多。同样Kruskal和最短路的Bellman-Ford也都是在处理边的循环但Kruskal是先排序再挑边Bellman-Ford是无序反复松弛。二者混乱的话代码很容易在逻辑上拼出一些“四不像”。我的习惯是每学一个新算法就把它和最相似的那个旧算法做一次对比分析把差异写到注释里。这个习惯帮我省了非常多调试时间。6.4 从题目限制来反推算法面对一道图论题我的破题顺序一般是看数据范围n、m分别到什么级别看权值是否可能为负判断是否适用Dijkstra看题面问的是单源、全源还是全局连通再决定是搜索、最短路还是最小生成树如果n只有几十直接Floyd也行如果n有十万用堆优化Dijkstra是常规操作如果n和m到百万连Dijkstra堆优化都危险这时就要考虑Johnson重标号之类更进阶的思路了不过在算法基础阶段能把上表里那些算法用对用熟已经足够应付绝大多数场景了。7. 最后交个底我自己的学习心得这一讲的内容量确实不小但你要是顺着“图的存储 → DFS/BFS → 最短路 → 最小生成树”这条线走下来会发现它们不是孤立的考点而是一套解决图问题的方法论。每次拿到新题先想它是“问路”还是“连线”再想它符不符合“无负权”的前提最后套模板思路会顺畅非常多。在刚开始刷题的那些日子里我其实特别容易被各种“优化技巧”带走比如看到SPFA就觉得比Bellman-Ford高级看到堆优化就觉得朴素Dijkstra没用。后来踩了些坑才发现能用简单算法解决的问题就不上复杂的代码短、逻辑清楚、不容易写错才是第一位的。先把每一种基础算法写熟再根据题目要求一点点升级这条路走得最稳。希望这份总结能帮正在学图论的你少走一些弯路。
