所有路径:需要存储路径的 DFS 模板
# 📃 题目描述
题目链接:
- 剑指 Offer II 110. 所有路径 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 797. 所有可能的路径 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个有 n 个节点的有向无环图,用二维数组 graph 表示,请找到所有从 0 到 n-1 的路径并输出(不要求按顺序)。
graph 的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些结点(译者注:有向图是有方向的,即规定了 a→b 你就不能从 b→a ),若为空,就是没有下一个节点了。
示例 1:
输入:graph = [[1,2],[3],[3],[]]
输出:[[0,1,3],[0,2,3]]
解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
# 🔔 解题思路
搜索一个节点到另一个节点的所有路径,BFS 和 DFS 都可以,不过 DFS 效率更高
深度优先搜索通常用递归实现。
- 从节点 0 出发开始搜索
- 每当搜索到节点 i 时,先将该节点添加到路径中去
- 如果该节点正好是节点 n-1,那么就找到了一条从节点 0 到节点 n-1 的路径
- 如果不是,则从 graph[i] 找到每个相邻的节点并用同样的方法进行搜索
- 当从节点 i 出发能够抵达的所有节点都搜索完毕之后,将回到前一个节点搜索其他与之相邻的节点。在回到前一个节点之前,需要将节点 i 从路径中删除。
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
// 起点加入 p
path.add(0);
dfs(0, graph, res, path);
return res;
}
// dfs 从 source 到 n - 1 的路径
private void dfs(int source, int[][] graph, List<List<Integer>> res, List<Integer> path) {
if (source == graph.length - 1) {
res.add(new ArrayList<>(path));
return;
}
// 从 source 到 n - 1 的路径 = 从 source 到 neighboor + 从 neighboor 到 n - 1 的路径
for (int neighbor : graph[source]) {
path.add(neighbor);
dfs(neighbor, graph, res, path);
path.remove(path.size() - 1);
}
}
}
可以发现,上述代码中没有判断一个节点是否已经访问过。在做图搜索的时候通常需要判断一个节点是否已经访问过,这样可以避免反复访问环中的节点。由于这个题目已经明确图是一个有向无环图,因此没有必要担心重复访问环中的节点。
另外,可能有的读者觉得上述代码和实现回溯法的代码很相像,这是因为回溯法从本质上来说就是深度优先搜索。
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10