图论开篇：DFS与回溯求解所有可达路径的完整指南

今天训练营走到第四十九天，正式开了图论这个大头。前面连续刷了十几天的动态规划，思路一下从“状态转移”切到“图的深搜”，说实话第一天有点被搞懵。不过今天这道卡码网 98 题《所有可达路径》属于图论里最典型、最值得反复吃透的入门题：给你一个有向图，找出从节点 1 到节点 N 的所有路径，并按字典序输出。它背后整套 DFS 加回溯的写法，后面几十道图论题几乎全部复用。

这篇文章我打算把题目理解、建图细节、多语言代码、常见坑位一次性讲透。不管你是训练营打卡到这儿的新手，还是想回头把 DFS 模板好好整理一遍的刷题党，都可以直接参考。题不难，但里面的细节足够你踩上几轮的。

1. 题目理解与整体思路拆解

1.1 这道题到底在问什么

题目输入结构很清晰：第一行两个正整数 N 和 M，代表图里有 N 个节点、M 条有向边。节点编号从 1 到 N。接下来 M 行，每行给出两个正整数 u 和 v，表示一条从 u 指向 v 的边。输出的是所有从节点 1 出发、最终到达节点 N 的路径，每条路径单独一行，节点编号之间用空格分隔。如果根本不存在任何一条从 1 到 N 的路径，输出 -1。

举一个最简单的例子。输入：

3 3 1 3 1 2 2 3

这时候节点 1 可以先去 3，也可以先去 2 再去 3，所以输出两行：

1 2 3 1 3

注意输入里先给了 1 3 这条边，再给的 1 2，但输出必须先输出 1 2 3，再输出 1 3。这就是题目要求的“字典序输出”。所谓字典序，就是把每条路径当成一个由数字组成的序列，逐位比较大小。1 2 3 和 1 3 的第一位都是 1，第二位 2 比 3 小，所以 1 2 3 排前面。

理解了这一步，整道题的核心就出来了：不是找最短路径，也不是判断连通性，而是把每条可达路径全部枚举出来。数量不定、长度不定、深挖到底再回头，这种枚举型任务，几乎就是为 DFS 量身定做的。

1.2 为什么图论开篇一定要先碰它

我在训练营刷到第四十九天，最大的感受是：图论这章真正的“地基”不是并查集、不是最短路径，而是最简单的 DFS。98 题把 DFS 的壳子完整地展示了一遍：怎么进节点、怎么判断终点、怎么收集结果、怎么回溯撤销选择。

这几个动作你看着简单，但没写过几遍就是容易乱。尤其是回溯到底该放在哪一行、递归终止时要不要 return、当前节点什么时候加入路径，这些细节后面做岛屿问题、做各种网格 DFS 时全都会用上。可以说，98 题是先给你一把最朴素的“图搜索”钥匙，后面所有题都是在这把钥匙上加各种限制条件。

另外一个容易被忽略的价值：它逼着你把“建图”这件事做干净。节点编号从 1 开始，数组要多开一个；边是有向边，不能顺手加两条；输出要求字典序，建完图就要排序。这些问题单独看都很小，但组合在一起，就能筛掉一大批只会在力扣上写核心函数的选手。

1.3 DFS 而不是 BFS：路径收集的关键差异

走到这道题面前，很多人第一反应是：图搜索不也能用 BFS 吗？确实能，但你来写写看就知道有多别扭。BFS 天生适合求最短距离、分层遍历，因为它是一层层向外扩展的，每个节点第一次被访问时的深度就是最短距离。可你现在要的是“所有完整路径”，不是某一条最优路径。

如果强行用 BFS，每个节点入队时必须带上“从起点到当前节点的完整路径副本”。每扩展一层，都要复制一份路径数组，路径越长、分支越多，空间开销就越离谱。而且最后你还要过滤掉那些不以 N 结尾的路径。代码写出来又长又丑，完全没有必要。

DFS 就不一样了。递归调用的本质是维护一个调用栈，这个栈天然记录着你从起点一路走来的每个节点。进入下一层就把新节点 push 到路径里，递归返回就把这个节点 pop 掉。这套“进入时选、离开时撤销”的操作就是回溯。它让路径收集变成了一件非常自然的事，你不需要额外维护复杂的数据结构，只需要理解递归的每一层对应图里的一个节点。

这里我给一个记忆锚点：DFS 是“不撞南墙不回头”，回溯是“撞了墙还要退回来换条路走”。有向图里每到一个节点，就试试它能去的所有方向，试完一条就回来试下一条，直到把所有可能的路都走遍。这就是所有可达路径这个问题的标准解法。

2. 建图与输出细节

2.1 邻接表还是邻接矩阵

写图题第一步永远是怎么存图。这道题两种方案都能过，但我的建议是无脑选邻接表。原因很简单：邻接表用多少存多少，复杂度是 O(N + M)，对于大部分刷题场景都足够。邻接矩阵需要开 N 乘 N 的二维数组，N 稍微大一点空间就顶不住了，遍历时的无效判断也会拖慢速度。

两种存图方式的关键差异我直接列表对比：

如果你的 N 只有十几二十，邻接矩阵确实写起来更省事，连排序都省了，因为矩阵行本身就是按下标从小到大遍历的。但训练营题解普遍采用邻接表，为了后续做更复杂的图论题，趁早把邻接表的建立和遍历练顺手更划算。这道题我直接用vector<vector<int>>这样的邻接表结构，下标从 1 到 N。

建表时有个别忽视的细节：数组要开 N + 1 个，下标 0 的位置直接空着。很多初学图论的人在这里踩坑，读入边的时候用的是节点编号，如果开 N 个，节点 N 就存不进去了。虽然很多平台不报越界，但结果是行为未定义，时好时坏，非常磨人。

2.2 字典序输出：先排序再深搜

字典序是这道题最容易出错的隐藏考点。题目不会单独给你一个测试用例说“注意排序”，但比较器在后台跑着，你不排序，答案顺序就是错的。

为什么邻接表排序能做到全局字典序？因为 DFS 每次面临的是“当前节点下一步去哪”，这个选择顺序决定了整条路径的相对顺序。只要保证每个节点访问邻接点的顺序都是升序，那么先产生的路径一定按字典序排在前面。这是一个可以严格推理的性质：路径 A 和路径 B 第一次出现分叉时，字典序比较的就是分叉位置两个下一跳节点的大小。每个分叉点都从小到大选择，自然满足了全局字典序。

所以建图读入所有边之后，对每个节点的邻接表做一次升序排序就够了。千万别把排序放到 DFS 递归里面，那样每层递归都重新 sort，复杂度直接爆炸。用 C++ 写就是：

for (int i = 1; i <= n; i++) { sort(graph[i].begin(), graph[i].end()); }

这还是我上面说的样例那样：输入先给了 1 3 再给 1 2，如果你不对 1 的邻接表排序，DFS 先走 3，输出就会变成 1 3、1 2 3，和正确答案完全反了。这种错误在本地往往发现不了，因为很多人用的样例恰好是有序输入的，只有提交之后才会翻车。

2.3 输入输出处理的小心机

因为训练营配套的评测网站用的是标准输入输出，所以 main 函数里的 IO 处理一定要严谨。C++ 里直接cin读，数据量不大，不需要刻意加速。输出的时候，每条路径用空格分开，行末不能有多余空格。很多刷题新手喜欢在最后一个元素后面也加一个空格，本地看没什么问题，评测系统比对字符串时就会被判 Presentation Error，非常可惜。

我处理行末空格的方法是：循环拼接时判断一下是不是第一个元素，不是的话先输出一个空格再输出数字。这样保证行尾干净。如果图不可达，判断一下结果集合是否为空，为空就直接输出 -1 并结束程序。注意 -1 也要换行，别问我是怎么知道的。

另外一个温馨提示：如果使用 Java，用System.out.print一个个输出就行，不需要为了性能引入太复杂的输出流，毕竟路径总数有限。Python 里就更加简单，路径转成字符串用" ".join()，自动就把空格处理好了。

3. 核心代码实现拆解

3.1 DFS 函数的三个关键设计

写 DFS 函数前，心里要先有张图：每个节点就是递归一层，当前路径用一个全局数组维护。于是三个关键设计就出来了。

第一个是递归终止条件。什么时候算找到一条路径？当然是当前节点编号等于 N 的时候。把当前路径收集进结果集合，然后直接 return。这个 return 不能省，否则会继续遍历 N 节点的邻接点，得到一堆多余的路径。当然如果题目数据里 N 节点没有出边，你不 return 它也自然结束了，但显式 return 语义更清晰，也防止万一后面数据里有从 N 出发的边。

第二个是横向遍历。在每个节点，把它的所有邻接点依次尝试一遍。先path.push_back(next)，然后递归进入下一层，等递归回来了再path.pop_back()。这一 push 一 pop 就是回溯的本体。很多人背模板时只记住了这两行，但没理解为什么递归回来要 pop：因为路径是共享的，这个节点尝试完了，如果不撤销，下一条路径就会把它错误地带进去。

第三个是起点处理。我习惯把 1 提前放进 path，然后从dfs(graph, 1)开始。这样递归函数里不需要再判断“当前路径是否只有起点”，会让代码更统一。但要注意，如果 N 恰好等于 1，这种写法在进入 dfs 时立刻满足终止条件，直接收集 [1]，逻辑上也是对的。

3.2 C++ 完整可运行版本

直接上代码，这套写法和训练营题解风格保持一致，我加了注释方便跟着看。

#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<vector<int>> result; vector<int> path; void dfs(const vector<vector<int>>& graph, int x, int n) { if (x == n) { result.push_back(path); return; } for (int next : graph[x]) { path.push_back(next); dfs(graph, next, n); path.pop_back(); } } int main() { int n, m; cin >> n >> m; vector<vector<int>> graph(n + 1); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u].push_back(v); } // 每个节点的邻接表排序，保证字典序输出 for (int i = 1; i <= n; i++) { sort(graph[i].begin(), graph[i].end()); } path.push_back(1); dfs(graph, 1, n); if (result.empty()) { cout << -1 << endl; return 0; } for (const auto& p : result) { for (int i = 0; i < p.size(); i++) { if (i > 0) cout << " "; cout << p[i]; } cout << endl; } return 0; }

这个版本里最核心的就是dfs函数那几行。path.push_back(next)代表“选择这条路往下走”，递归调用返回之后path.pop_back()代表“这条路走完了，把节点拿掉，换下一个方向”。整个遍历过程就是不断选择、递归、撤销、再选择。

3.3 Java / Python / Go 对照实现

因为训练营里很多同学在学校用的是 Java 或者 Python，我也把这两个版本放出来。Go 是后来群里有人问我才补的，现在一起给上。

Java 版本要注意new ArrayList<>(path)拷贝，否则所有结果都会引用同一个 path 对象。

import java.util.*; public class Main { static List<List<Integer>> result = new ArrayList<>(); static List<Integer> path = new ArrayList<>(); static void dfs(List<List<Integer>> graph, int x, int n) { if (x == n) { result.add(new ArrayList<>(path)); return; } for (int next : graph.get(x)) { path.add(next); dfs(graph, next, n); path.remove(path.size() - 1); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int u = sc.nextInt(); int v = sc.nextInt(); graph.get(u).add(v); } for (int i = 1; i <= n; i++) { Collections.sort(graph.get(i)); } path.add(1); dfs(graph, 1, n); if (result.isEmpty()) { System.out.println(-1); return; } for (List<Integer> p : result) { for (int i = 0; i < p.size(); i++) { if (i > 0) System.out.print(" "); System.out.print(p.get(i)); } System.out.println(); } } }

Python 版本写起来最短，但path.copy()和path.pop()这两个细节一个都不能漏。

def dfs(graph, x, n, path, result): if x == n: result.append(path.copy()) return for nxt in graph[x]: path.append(nxt) dfs(graph, nxt, n, path, result) path.pop() def main(): import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n + 1)] for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) for i in range(1, n + 1): graph[i].sort() result = [] dfs(graph, 1, n, [1], result) if not result: print(-1) else: for p in result: print(" ".join(map(str, p))) if __name__ == "__main__": main()

Python 初学者最常犯的错误是result.append(path)而不是result.append(path.copy())。Python 的 list 是引用类型，path之后一旦pop，结果集合里已保存的路径也会跟着变。最后打印出来的可能全是同一个路径，或者全是空的。这个问题极其隐蔽，但做一次就长记性了。

Go 版本适合已经开始写 Go 的同学，切片操作需要理解背后的容量和共享机制。

package main import ( "bufio" "fmt" "os" "sort" "strconv" "strings" ) var result [][]int var path []int func dfs(graph [][]int, x, n int) { if x == n { tmp := make([]int, len(path)) copy(tmp, path) result = append(result, tmp) return } for _, nxt := range graph[x] { path = append(path, nxt) dfs(graph, nxt, n) path = path[:len(path)-1] } } func main() { scanner := bufio.NewScanner(os.Stdin) scanner.Scan() parts := strings.Split(scanner.Text(), " ") n, _ := strconv.Atoi(parts[0]) m, _ := strconv.Atoi(parts[1]) graph := make([][]int, n+1) for i := 1; i <= n; i++ { graph[i] = []int{} } for i := 0; i < m; i++ { scanner.Scan() parts = strings.Split(scanner.Text(), " ") u, _ := strconv.Atoi(parts[0]) v, _ := strconv.Atoi(parts[1]) graph[u] = append(graph[u], v) } for i := 1; i <= n; i++ { sort.Ints(graph[i]) } path = append(path, 1) dfs(graph, 1, n) writer := bufio.NewWriter(os.Stdout) defer writer.Flush() if len(result) == 0 { fmt.Fprintln(writer, -1) return } for _, p := range result { s := make([]string, len(p)) for i, v := range p { s[i] = strconv.Itoa(v) } fmt.Fprintln(writer, strings.Join(s, " ")) } }

Go 里path = path[:len(path)-1]这一步在功能上等于 pop。但如果你在递归前把path传给下一个函数，并且子函数里 append 可能扩容，那么底层数组可能已经不是原来那个了。因此收集路径时一定要copy到一个新切片，不能直接append(result, path)。

3.4 不回溯会怎样：常见错误演示

刷这种题最经典的自毁操作，就是把path.pop_back()那一行删掉。删掉之后代码长这样：

for (int next : graph[x]) { path.push_back(next); dfs(graph, next, n); }

递归结构还在，但每层递归返回后，刚才加入路径的 next 永远留在 path 里。比如从 1 走到 2，递归返回后 path 里还是 [1,2]，再去试 1 的另一个邻接点 3，path 就变成了 [1,2,3]。后面的递归继续往里加，最终你会得到一条超长、包含大量重复节点的错误路径。运气好只是错误答案，运气不好直接栈溢出。

理解这件事的关键在于：path 不是“每个节点私有的副本”，而是整个搜索过程共享的“当前路径记录”。你进入一个节点要留下标记，离开时自然要擦掉标记。如果你把递归想象成在一个迷宫里探路，手上的绳子就是 path。走到死路退回来时，绳子必须收回一段，否则下一条路线就无法从分岔口重新开始。

所以“回溯”不是模板里多出来的一行废话，它是 DFS 枚举所有路径的必要条件。没了它，DFS 就退化成一条走到黑的瞎撞。

4. 处理不可达、环与复杂度的边界问题

4.1 不可达时输出 -1

题目要求：如果从 1 到 N 一条路径都不存在，输出 -1。实现上最直观的做法就是把所有路径收集到 result 里，最后统一判断result.empty()。路径数量是有限且可控的，这个判断完全不会有性能压力。

有人会选择在 DFS 过程中用一个计数器，只要找到过路径就标记一下。这也能做，但代码会多一个全局变量，还需要保证每个 DFS 分支都正确访问。统一收集再判断，逻辑最清晰，也不容易漏状态。写这种基础题，我倾向于牺牲一个变量换来大脑的清爽。

还有一个容易忽略的边界：如果 N 等于 1，那起点就是终点，路径只有一条：1。上面 C++ 代码里，path 初始化为 [1]，进入 dfs 后立刻满足x == n，收集 [1]，然后返回。所以代码天然正确处理了这个情况，不需要额外判断。

4.2 图里有环怎么办

这其实是一个非常值得讨论的边界问题。严格来说，如果在搜索时遇到环，比如 1 能到 2，2 能回到 1，那么 DFS 沿着 1->2->1->2 这条路会永远走不完。不加任何限制的话，递归栈会爆炸。

但绝大多数刷题场景里，这道题给出的输入数据默认不会有环，或者题目语义默认“路径”指简单路径，不重复经过同一个节点。卡码网 98 题的题解里普遍也不加 visited 数组，因为数据限制保证了不会出现无限循环。你看到别人代码里没有 visited，不代表有环也能过。

如果真遇到可能带环的输入，处理方式是在当前递归路径上维护一个布尔数组，标记哪些节点已经在 path 里。进入节点前判断，已经标记过就跳过；递归返回时撤销标记。这样保证了每条简单路径不包含重复节点，也不会无限兜圈。但注意，加了这层限制后，路径含义变成了“简单路径”，和题目默认语义可能产生偏差。所以正常情况下不要画蛇添足，先确认题目数据约束再说。

4.3 所有路径数量与性能权衡

“输出所有路径”这类问题的时间复杂度最坏是指数级以上的，这是它和“求最短路径”的本质区别。一个完全有向图里，从 1 到 N 的路径数量可以是惊人的，接近 (N-2)! 的量级。所以评测数据里 N 通常不会给得太大，这题考查重点不是大数据量下的优化，而是搜索模板本身是否正确。

还有一个点：路径数量多的时候，输出本身就可能成为瓶颈。所以这类题目的输出处理也要注意效率，别在循环里做太重的字符串拼接。C++ 直接 cout 加空格没问题，Java 大量 print 也问题不大，Python 如果路径特别多，可以考虑用列表收集后一次性 join。

性能上还有一个实用建议：邻接表排序只需要在建图完成后做一次，不要在递归函数里反复排序。每次递归排序会把 O(N log M) 乘到路径数量上，超时的时候很难排。排序本身是为了字典序服务的，一次性排好，DFS 全程受益。

5. 训练营第 49 天：一道开篇题带来的方法论

5.1 这一天的刷题节奏

训练营到了图论第一天，节奏跟前面动态规划不太一样。动态规划题目动辄需要推导状态转移方程，经常会卡很久。而 98 题这种图搜索题，主要是模板记忆加细节打磨，第一道题通常一个小时左右可以过得比较完整。

我建议的流程是：先看题面，理解输入输出，然后不急着看题解，自己手写一个 DFS。写不出来也没关系，卡五分钟以后再看题解，重点看回溯放在哪一行。看完后合上题解，自己重新默写一遍。这一遍写熟练之后，马上用自己的代码跑题目样例和几个自测构造的用例，确认字典序和 -1 分支正确。

这道题很有价值的一点是，它用最简单的方式训练你在图论题里的“肌肉记忆”。后续很多题只是在这个框架上加 visited 数组、加方向数组、加去重逻辑。第一天把 DFS 骨架打进潜意识，后面会省非常多时间。

5.2 这道题和后面题目的连接

在训练营的图论章节里，98 题之后你会碰到的经典题型，比如岛屿数量、岛屿最大面积、飞地数量、太平洋大西洋水流问题，核心都是网格 DFS。网格 DFS 本质上就是在二维网格上做“所有可达位置”的搜索，只是相邻方向变成了上下左右四个方向。你一定会在那些题里反复看到“进入节点标记、递归访问、回溯撤销”的影子。

后面的最短路相关题目，比如 dijkstra、Bellman-Ford，虽然改用了更复杂的算法，但底层仍然是从起点出发沿着图的边向外扩展。理解 DFS 能帮你建立起“从起点不断向外探索”的直觉。甚至回溯章节里的全排列、组合题，本质上也是在一棵隐式的树或者图上做 DFS。

所以这道题千万别觉得简单就随手划过。它是最小的、能跑通的、带完整输入输出的图搜索模型。后面所有图论题，都可以看作在这个模型上加条件。

5.3 关于打卡的几点体会

刷到第四十九天，我对打卡这件事有个很深的体会：不要怕“简单题”。98 题第一眼看上去没有任何算法难度，但它暴露了我不少问题。比如我第一次写完，样例过了，提交却不是字典序；加了排序后又因为回溯位置写错，路径被重复叠加。每次栽在这种基础题上，反而比做难问题时收获更大。

训练营里比较推荐的做法是记录“一题多写”。今天这道题，我分别用 C++、Python、Go 各写了一遍。切换语言的过程会让你更加清楚地看到哪些是语言特性带来的坑，哪些是算法本质。比如 Go 的切片引用问题，你光看 C++ 永远意识不到，但写一遍就懂了。

还有就是要重视自测。不要只拿题目给的样例测完就交。自己构造一个 N=1 的边界，一个 1 和 N 不连通的图，一个有多个出边的中间节点，把输出逐行核对。这种习惯比多刷十道题还值钱。

6. 常见问题与排查技巧实录

6.1 问题速查表

我把做这道题最容易碰见的问题整理成一个速查表，方便你写代码时候对照排查。

这些坑都存在得非常具体，你只要踩过一次，基本就记住了。

6.2 我踩过的三个坑

第一个坑是字典序。我第一次做的时候只想着 DFS 模板，建完图直接开始搜，也不管输入顺序。样例给的是有规律的数据，一跑就过。但提交之后发现答案顺序不对，才意识到题目要求字典序。这里的关键不是“要排序”这个结论，而是“为什么要排序”。因为 DFS 的遍历顺序直接决定了输出顺序，而遍历顺序取决于邻接表的存储顺序。

第二个坑是回溯位置。我早期的有些代码会把path.pop_back()写在if (x == n)判断块里，导致到达终点后没有撤销最后一个节点，下一条路径错得离谱。正确的逻辑应该是：无论当前路径是否到达终点，只要这个节点作为某个选择被尝试过，递归返回后都要撤销。换句话说，一个节点的加入和撤销是成对出现的，它跟“是否到达终点”无关。

第三个坑是 Go 的切片。append(result, path)这种写法在我写 Go 的前期经常出问题。path底层数组在递归过程中是不断被复用的，一旦保存的是引用，后续 pop 会修改已经被写入结果的内容。正是这个坑让我彻底理解了为什么语言层面要强调“拷贝”。现在不管用什么语言写路径收集，我都会下意识确认到底存的是副本还是引用。

6.3 调试建议

调试 DFS 类题目，最有效的工具就是打印当前路径。在进入递归时加一行输出：当前走到了节点 x，现有路径为 ...。跑一遍小样例，你就能看到每一条路径是怎么被尝试的，回溯是否生效。

我个人的习惯是先用一个非常小的图做实验，比如 4 个节点、4 条边，手工推一遍所有路径，然后让程序跑出来。如果程序输出的路径集合完全覆盖手工结果、顺序字典序正确、行末没有多余空格，基本就可以提交了。

还有一个比较推荐的做法：把“收集路径”和“输出路径”分开。先在 DFS 里只收集结果，等搜索彻底结束再统一输出。这样调试时可以在递归结束后打点检查 result 的所有内容，避免边搜索边输出导致难以发现问题。

最后说一个小技巧：如果你不确定自己的 DFS 会不会死循环，先构造一个带环的小图去跑，看程序会不会终止。这比任何静态分析都直观。

我个人在做完这道题之后，把 DFS 模板的各个部分重新默写了三遍，反复对照“当前节点”“递归调用”“回溯撤销”三者之间的关系。现在回头看，第四十九天这天的收获远比一道简单题看起来大得多。这道题后面接的岛屿系列、最短路系列我都走得比较顺，很大程度上就是因为在 98 题上把 DFS 的底子打扎实了。如果你正卡在训练营图论的起点，别着急，把这题吃透，后面会轻松很多。