1. 题目解读与核心思路图论这道开胃菜到底在考什么训练营走到第四十九天二叉树、回溯、贪心、动规都过了一遍终于到了图论开篇。今天这题“98. 所有可达路径”看起来很简单很多人扫一眼题目就觉得“不就是DFS把所有路走一遍吗”但我建议大家把这道题当成一个分水岭来对待从这题开始你的DFS要从“树上走路”切换到“图上寻路”这两种场景有着本质差异。而这题恰好就是训练营安排的图论第一课目的很明确——让你先把图的存储和DFS模板焊死在脑子里后面什么最短路径、拓扑排序、并查集才接得住。先把这个题目的真实面貌说清楚。它并不是直接让你调接口返回结果而是模拟了一个经典的ACM式输入输出第一行给出两个整数 N 和 M表示图里有 N 个节点和 M 条有向边接下来 M 行每行两个整数 S 和 E表示有一条从 S 指向 E 的边。要求你输出从节点 1 出发到达节点 N 的所有路径每一行输出一条完整路径节点编号之间用空格分隔如果 1 到 N 没有任何可达路径就输出 -1。举个例子输入 5 5 1 2 1 3 2 4 3 4 4 5 输出 1 2 4 5 1 3 4 5这个例子中从 1 出发要走到 5有两条路先到 2 再到 4 最后到 5或者先到 3 再到 4 最后到 5。输出顺序要求尽量按字典序也就是说同一条路径内部节点编号从小到达排列多条路径之间也按这种顺序输出。为什么训练营要把这道题放在图论最前面我的理解有三层用意。第一层让你直观感受“图”这个数据结构它不再是二叉树那样每个节点至多两个孩子、路径唯一的场景而是从一个节点可能发散出很多条边同一个节点也会被很多条路径经过。第二层考察你对递归和回溯的熟练度搜索路径本质上就是把DFS的过程“画”出来每一条路径就是递归树里从根到叶子的一条完整分支回溯则是还原现场保证一条路径搜索完不影响下一条。第三层逼你处理真实的输入输出和边界情况这正是刷题网站和实际面试笔试的区别。力扣上有个经典题“所有可能的路径”也是同样的逻辑但人家直接把邻接表塞给你你只管写核心函数而这题要求你自己建图、自己读数据、自己控制输出格式工程感更强。我在训练营群里见过不少同学二叉树回溯滚瓜烂熟一到这题却卡住。卡住的原因往往不是DFS本身而是对“图的存储”和“递归的共享状态”理解不够透彻。这篇文章就把这两个点彻底掰开揉碎顺带把邻接矩阵、邻接表、visited数组该不该用这些争议点一次性讲明白。2. 图的存储方式邻接矩阵和邻接表怎么选差别在哪里2.1 邻接矩阵用二维数组把整个图摊开邻接矩阵的思路很好懂声明一个 (N1) x (N1) 的二维数组 graphgraph[s][e] 等于 1 表示存在从 s 到 e 的有向边等于 0 表示没有边。需要注意的一点是这里节点编号是从 1 到 N所以数组两个维度都要比 N 多开一格避免索引错位。int[][] graph new int[n 1][n 1]; for (int i 0; i m; i) { int s sc.nextInt(); int e sc.nextInt(); graph[s][e] 1; }构建过程没什么技术含量但在遍历的时候邻接矩阵的表达很优雅在DFS中枚举当前节点 cur 的所有邻居只需要固定行号从 1 到 N 扫描列for (int next 1; next n; next) { if (graph[cur][next] 1) { // 说明存在 cur - next 这条边可以往下走 } }这种写法的好处是遍历天然有序。因为列号从小到大扫描所以找到的邻居自然是按节点编号升序排列的最终输出的路径也天然满足字典序要求不需要额外排序。坏处也很明显空间复杂度是 O(N^2)。如果 N 到 5000开一个 5000x5000 的二维数组压力就很大了。而且如果图是稀疏的大部分格子都是 0很浪费。2.2 邻接表更紧凑、更常用的存储方式邻接表是竞赛和工程里更常用的方案为每个节点准备一个列表列表中存放它所有能到达的邻居节点。Java 里最常见的写法是ArrayListInteger[] graph初始化时遍历数组给每个位置 new 一个空列表ArrayListInteger[] graph new ArrayList[n 1]; for (int i 0; i n; i) { graph[i] new ArrayList(); } for (int i 0; i m; i) { int s sc.nextInt(); int e sc.nextInt(); graph[s].add(e); }很多同学会问为什么用数组而不是ListListInteger。说实话两种写法都能跑但ArrayListInteger[]的可读性更强下标直接代表节点编号写起来也顺手。如果你担心泛型数组的坑也可以用ListListInteger graph new ArrayList()效果相同。遍历邻居时邻接表和邻接矩阵完全是一个画风for (int next : graph[cur]) { // 直接拿到一个邻居节点 }邻接表最大的优势是只存储实际存在的边空间复杂度 O(NM)稀疏图下优势巨大。但它默认不保证邻居顺序如果题目要求输出路径按字典序排列你需要对每个节点的邻居列表排序或者在读入后统一排一次序。这一点特别容易漏后面我会重点讲。2.3 两种存储方式对比什么时候用哪个我直接给结论。如果 N 的范围很小比如 100 以内邻接矩阵随便用省心省事遍历顺序可控。如果 N 上了 1000 甚至更大优先考虑邻接表防止内存超限。另外要看你后续要拓展什么算法有些算法用邻接矩阵实现起来更直观比如 Floyd 多源最短路而 DFS、BFS、Dijkstra、拓扑排序这些用邻接表写起来更自然。对比维度邻接矩阵邻接表空间复杂度O(N^2)O(NM)判断两点是否有边O(1)需要遍历列表遍历某个节点的所有邻居O(N)O(该节点出度)邻居顺序是否天然升序是否需要排序适用场景稠密图、N较小稀疏图、N较大、通用这道题两版代码我都写过实测下来训练营给的测试数据规模不大邻接矩阵完全可行而且判断边、控制输出顺序都非常方便。但如果想通过这题把基本功打扎实我更建议邻接表也写一遍毕竟面试写算法时邻接表出现频率更高。3. DFS搜索所有路径递归、回溯和“共享状态”这三点必须同时理解3.1 递归函数设计的四个关键要素图论里用DFS找所有路径递归函数本质上是一个“带着当前路径继续走”的过程。设计递归函数时我习惯按四个要素来扣参数传递什么、什么时候返回、单层递归做什么、返回值要不要。对于这道题递归函数可以设计成这样static void dfs(int cur, int target) { if (cur target) { result.add(new ArrayList(path)); return; } for (int next : graph[cur]) { path.add(next); dfs(next, target); path.remove(path.size() - 1); } }参数传递的是当前节点 cur 和目标节点 target。路径本身不通过参数传递而是放在一个全局的 path 列表里。这里有个很重要的设计决策为什么 path 要搞成全局共享的而不是作为参数传下去因为如果每次递归都复制一个新列表固然安全但复制开销大而且回溯的“恢复现场”逻辑就体现不出来了。训练营这题的核心目的之一就是让你体会回溯所以共享 path 是最佳实践。终止条件也很清晰当前节点等于目标节点时说明一条完整路径已经走完把 path 的副本存入结果集合然后返回。注意这里必须new ArrayList(path)也就是做一次拷贝否则后续回溯会把这个列表的内容改掉导致结果集里存的全是同一个引用最终看到的结果全是空的或者全是最后一条路径。这个坑我在后面问题排查里会专门再讲一次因为它实在太经典了。单层递归的逻辑就是枚举当前节点的所有邻居把邻居先加入 path然后递归深入等递归返回后再把它从 path 里移除。这个“加入-递归-移除”的三段式操作就是回溯的完整循环。那返回值呢这题的递归函数返回 void 就够了因为所有结果都收集在全局的 result 集合里。不需要像动态规划那样返回一个计算值。很多同学写DFS时会惯性想着返回一个布尔值或者列表实际上只有当我们需要从递归中“获得信息”时才需要返回值收集型搜索一般不需要。3.2 为什么必须“恢复现场”用一个比喻讲透回溯关于回溯为什么必须把 path 恢复到进入递归之前的状态我用一个非常简单的生活类比来解释。想象你在走一个迷宫手里拿着一张纸记录走过的路。你选择一条岔路往前走把这条路名写在纸上走到死胡同或者找到出口后你必须回到岔路口把刚才写的那条路名从纸上划掉才能去试下一条岔路。如果不划掉纸上记录的就不仅是当前这条路的轨迹还混了上一条路已经走过的内容整个记录就废了。代码里path.remove(path.size() - 1)就是那个“划掉”的动作。它执行的时间点是在以 next 为起点的那一整棵递归子树全部跑完之后。换句话说dfs(next) 返回时无论它内部经历了多少层递归、产生了多少条路径最终状态都保证 path 和进入 dfs(next) 之前一模一样。这是递归函数设计里的“契约”一个递归调用不能对外层调用者留下污染。理解了这个契约回溯就没什么神秘的了。这条契约在所有需要遍历“全部方案”的题目里都成立。排列问题、组合问题、子集问题、棋盘搜索问题全部是同样的套路。所以训练营把这题放在图论开头也是在变相提醒你回溯不仅仅是回溯算法章节的内容它本质上是DFS遍历所有分支时的标配操作。3.3 到底要不要用 visited 数组有环和无环的区别很多同学看到“图”就条件反射地加一个 visited 布尔数组结果发现这道题加了反而出错。原因在于这道题默认是有向无环图也就是 DAG。如果不存在环那么同一个节点最多出现在某一条路径中一次但你完全可能在不同的路径中重复访问同一个节点。举个例子路径 1-2-5 和路径 1-3-2-5 都经过了节点 2这是合法的。如果在这个前提下用一个全局的 visited 数组标记过的节点以后再也不能访问那你第一次通过路径 1-2 访问过节点 2 之后第二次从 1-3-2 这条路就再也走不过去了正确答案就会被丢掉。那有环的图怎么办如果真的碰到可能存在环的题目visited 数组的用法要有讲究不是在进入节点后永久标记而是标记“当前这轮递归路径上已经经过的节点”在做完这条路径的遍历后要取消标记。这样既能防止在一条路径里无限绕圈又不影响其他路径再次经过这个节点。看一下模板if (visited[next]) continue; visited[next] true; path.add(next); dfs(next, target); path.remove(path.size() - 1); visited[next] false;注意最后一行的visited[next] false这个动作和path.remove一样也是回溯的一部分。这正好呼应了上一小节说的“现场恢复”不仅 path 要恢复所有在递归过程中改变的状态都要恢复。这道题因为题目保证无环所以 visited 完全不需要但你心里要清楚它在什么情况下才必要。3.4 完整可运行的邻接表版本代码把前面的东西拼起来我给出一个可以直接提交的邻接表版本语言用 Java这也是训练营里很多同学用的主力语言。import java.util.*; public class Main { static ListListInteger result new ArrayList(); static ListInteger path new ArrayList(); static ArrayListInteger[] graph; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); graph new ArrayList[n 1]; for (int i 0; i n; i) { graph[i] new ArrayList(); } for (int i 0; i m; i) { int s sc.nextInt(); int e sc.nextInt(); graph[s].add(e); } // 保证每个节点的邻居按编号升序排列从而保证输出字典序 for (int i 1; i n; i) { Collections.sort(graph[i]); } path.add(1); dfs(1, n); if (result.isEmpty()) { System.out.println(-1); } else { for (ListInteger p : result) { StringBuilder sb new StringBuilder(); for (int i 0; i p.size(); i) { if (i 0) sb.append( ); sb.append(p.get(i)); } System.out.print(sb); System.out.println(); } } } static void dfs(int cur, int target) { if (cur target) { result.add(new ArrayList(path)); return; } for (int next : graph[cur]) { path.add(next); dfs(next, target); path.remove(path.size() - 1); } } }这份代码量不大但信息密度很高。main 方法里做了四件事读入 N 和 M、初始化邻接表、读入所有边、给邻居列表排序。然后调用 dfs 开始搜索。dfs 干了三件事判断是否到达目标、遍历邻居、做加入和回溯的循环。再说一下邻接矩阵版本。核心差异只在 main 里的建图方式和 dfs 里遍历邻居的方式static int[][] graph; static int n; // main里建图 graph new int[n 1][n 1]; for (int i 0; i m; i) { graph[sc.nextInt()][sc.nextInt()] 1; } // dfs里遍历 static void dfs(int cur, int target) { if (cur target) { result.add(new ArrayList(path)); return; } for (int next 1; next n; next) { if (graph[cur][next] 1) { path.add(next); dfs(next, target); path.remove(path.size() - 1); } } }邻接矩阵版本因为没有排序问题输出天然满足字典序读起来也更直观。如果你刚开始学图论建议先把邻接矩阵版本写通再改成邻接表版本这样对两种结构的差异会有特别直观的感受。3.5 主函数里 path 的初始化和边界情况还有一个细节在调用 dfs 之前我先把节点 1 加进了 path也就是path.add(1)。这一步非常关键。因为题目要求输出的路径包含起点和终点如果你不在递归前把起点放进去那搜索到的每一条路径都会缺一个头。那为什么不把起点的加入放在 dfs 内部呢也可以但处理起来要么在递归入口额外判断要么在终止条件里单独拼都很别扭。直接在调用前把起点塞进 path递归过程就完全统一了每次进入 dfs(cur)path 的末尾永远就是当前节点 cur。这样“当前路径”这个语义不会乱。边界情况也得想一想。如果 N 等于 1也就是起点就是终点此时 path 初始为 [1]调用 dfs(1, 1) 后立刻触发终止条件result 里会有一条路径“1”输出就是 1。这在逻辑上是自洽的。当然实际测试数据很少会这么极端但写代码的人应该对这类边界有掌控力。4. 工程细节输入输出格式、字典序、空路径处理4.1 为什么这道题比力扣版更考验工程感如果你已经刷过力扣 797 题可能会觉得这题写起来怎么这么啰嗦又是 Scanner 读数据又是 StringBuilder 拼输出还要判断 result 为空时输出 -1。这是有意的。真实面试和在线笔试环境中你拿到的往往就是这种文本形式的输入输出而不是封装好的函数接口。很多同学在力扣上写得飞起一到笔试环境连数据怎么读都忘记这就是缺乏练习。训练营把这题设计成 ACM 式核心意图就是逼你过了这一关。Java 里读数据我用 Scanner 就够了N 和 M 的规模一般不会太大。如果你确认数据量很大、输入行数很多可以换成BufferedReader加快读取速度但在这题的范围内没必要。4.2 输出格式的三个易错点输出部分的细节简直是小坑集合。第一个易错点行末不能有多余空格。很多人用 for 循环直接System.out.print(p.get(i) )结果每行最后一个节点后面跟着一个空格。判题系统很多是逐字符比对多余空格直接 WA。所以我用 StringBuilder 拼接在 i 0 时才加空格这样行尾干净。第二个易错点多条路径之间需要换行。如果你用的是System.out.print拼完一条路径不换行那两条路径会黏在一起输出就错乱了。上面代码里我在每条路径结尾单独打印一个换行稳妥。第三个易错点无路径时必须输出 -1而且 -1 后面也必须有换行。用System.out.println(-1)就很安全不要用System.out.print(-1)。这种小细节每年笔试不知道放倒多少人。4.3 字典序到底是靠什么保证的题目要求路径按字典序输出我在前面提到邻接表需要排序。如果你用的是邻接矩阵遍历邻居时列号从小到大天然有序如果你用邻接表就要在 dfs 之前对每个节点的邻居列表排序for (int i 1; i n; i) { Collections.sort(graph[i]); }这一步别漏。我见过一个同学写完了代码逻辑全对就是因为没有排序输出顺序和标准答案不同怎么查都查不出来。后来对照输出才发现邻居顺序反了。为什么排序邻居就能保证最终路径有序因为 DFS 是深度优先枚举相同的节点前缀下遍历到的第一个邻居编号小那么以它为起点的整棵递归子树都会先被完整搜完所以形成的所有路径自然按字典序排列。5. 常见问题与排查技巧实录5.1 结果集里的路径全是空的或者全是最后一条这是回溯初学者最容易踩的坑也非常有迷惑性。有人甚至在本地 debug 时发现 result 集合打印出来是一个空列表列表或者所有元素完全一样。原因其实很统一在加入结果时没有拷贝 path直接result.add(path)。由于 path 是共享的可变对象后续每次删除节点都会把同一个对象的内容改掉。最终 result 里存的多个引用实际都指向同一块内存里面要么是空列表要么是最后一条路径。解决办法永远只有一句话result.add(new ArrayList(path))。无论你用什么语言思路都是拷贝一份快照而不是存引用。Python 里对应的是result.append(path[:])C 里对应result.push_back(path)因为 C 的 vector 默认是值拷贝。这算是我在整个训练营里看到过频率最高的一类问题希望大家一次看明白不要再交学费。5.2 死循环或栈溢出环的问题如果测试数据没有保证无环而你又不做任何处理DFS 会在环里无限递归最终栈溢出。判断是否栈溢出其实很简单如果程序跑着跑着什么都没输出就抛 StackOverflowError十有八九就是有环。处理方式在上面第 3.3 节已经给了模板定义一个 visited 数组标记当前递归路径上的节点进入递归前检查递归结束后取消标记。但注意这题常规数据下用不到这个数组。什么时候需要你警觉呢如果题目描述里没说清楚图是否有环默认当作可能有环来处理更安全添加上 visited 逻辑顶多多写三行性能影响也可忽略。5.3 输出路径数量正确但顺序不对这个问题的根源基本只有一个邻接表没有排序或者排序代码写错位置。常见错误是把排序放在了建图之前等边都读完了列表又变成无序状态。记得一定是所有边读完之后再做统一排序。还有一个小坑是如果边输入本身已经是按字典序排列的那排序对应的 compare 规则不正确而报错。所以直接Collections.sort就好了别自己写比较器画蛇添足。5.4 读入时报数组越界或空指针如果你初始化邻接表时循环写成了for (int i 0; i n; i)而节点编号是从 1 到 N那么访问 graph[n] 时就会数组越界。这类问题在本地一跑就能暴露解决也不难数组长度初始化成 n1循环条件写成 i n。空指针更容易出现声明了ArrayListInteger[] graph new ArrayList[n1]但没有 for 循环给每个元素 new 一个列表然后直接graph[s].add(e)必然空指针。这个问题我在不少同学代码里都见过大家总是以为 new 了一个对象数组里面的元素就自动创建好了实际上数组里存的全是 null。记住数组初始化只创建了“装列表的格子”每个格子里还得手动放一个空列表。5.5 从力扣版移植过来时间接错了节点编号力扣版“所有可能的路径”节点编号是从 0 到 n-1起点是 0终点是 n-1。而这题是 1 到 N起点是 1终点是 N。移植代码时最容易漏改的就是这两个地方初始化数组大小、递归终止条件、邻居遍历范围。我建议不要在旧代码上直接改干脆重写一遍把编号习惯彻底换过来否则特别容易出现隐性 bug。6. 关于这道题的复盘和几个后续联想题目本身不复杂但复盘时我特别想强调一个点初次接触图论时不要因为题目简单就匆匆跳过。把每个细节都做扎实邻接表和邻接矩阵各敲一遍递归函数的四要素自己说一遍回溯这个动作的意义用自己的话讲一遍。这三件事做完你对 DFS 的掌握会比只刷三五十道回溯题更牢固因为它把“遍历节点的所有邻居”和“恢复现场”这两个核心动作直接焊进了条件反射里。我个人的一点体会是刚接触这题那会儿我也踩过 5.1 里那个拷贝坑当时 debug 得一头雾水怎么看 result 都是空。后来打印了一下 path 的变化过程才意识到问题出在共享引用上。从那以后凡是往结果集里添加一个可变对象我写代码时都会条件反射地问自己一句这里要不要拷贝这个习惯让我在后来的组合总和、子集、八皇后等一票回溯题里基本没再犯过同类错误。顺着这题往后的学习路径也很清晰能打印所有路径说明你已经能在图上做深度遍历了再往后就是广度遍历、最短路径、拓扑排序、并查集、最小生成树。很多看起来高大上的图算法底层无非就是在“怎么存图”和“怎么遍历图”这两个基本动作上叠加额外规则。把今天这题的存储和遍历功底打好后面遇到任何图论题心里都会踏实的多。