力扣 797. 所有可能的路径 解析JS、Java、python、Go、c++

深度优先搜索解所有可能的路径问题

题目描述

力扣链接
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

提示：

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i（即不存在自环）
graph[i] 中的所有元素 互不相同
保证输入为 有向无环图（DAG）

解题思路

由于是有向无环图，可以使用深度优先搜索（DFS）遍历所有可能路径。通过回溯法维护当前路径，在到达终点时保存路径到结果集[[2]][[5]]。

关键实现步骤

1. 维护两个数据结构：
   • ans：存储所有合法路径
   • path：记录当前遍历路径（栈结构）
2. 从节点0开始DFS
3. 遍历当前节点的所有邻居：
   • 将邻居节点加入路径
   • 递归处理邻居节点
   • 回溯时弹出最后加入的节点
4. 当到达终点n-1时，将当前路径加入结果集

代码实现

Java版本

class Solution {//最终返回结果List<List<Integer>> ans = new ArrayList();//保存其中的一条结果Deque<Integer> stack = new ArrayDeque();public List<List<Integer>> allPathsSourceTarget(int[][] graph) {//graph[i] 是一个从节点 i 可以访问的所有节点的列表//因为从节点0开始stack.offerLast(0);//调用dfs(graph,0,graph.length-1);return ans;}public void dfs(int[][] graph,int x,int n){//x表示当前遍历的节点 n表示要到达的节点if(x == n){//如果x == n 说明遍历到了最后节点 将stack作为一个结果存入ans.add(new ArrayList<Integer>(stack));return;}//graph[x] 表示当前节点x的所有邻居节点for(int y:graph[x]){//遍历节点x的每个邻居节点//1、将y存入stack.offerLast(y);//递归dfs(graph,y,n);//回溯stack.pollLast();}}
}

JavaScript版本

var allPathsSourceTarget = function(graph) {const ans = [];const dfs = (curr, path) => {if (curr === graph.length - 1) {ans.push([...path]);return;}for (const neighbor of graph[curr]) {path.push(neighbor);dfs(neighbor, path);path.pop();}};dfs(0, [0]);return ans;
};

C++版本

class Solution {
public:vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {vector<vector<int>> ans;vector<int> path = {0};dfs(graph, 0, graph.size()-1, path, ans);return ans;}private:void dfs(vector<vector<int>>& graph, int curr, int target, vector<int>& path, vector<vector<int>>& ans) {if (curr == target) {ans.push_back(path);return;}for (int neighbor : graph[curr]) {path.push_back(neighbor);dfs(graph, neighbor, target, path, ans);path.pop_back();}}
};

Go版本

func allPathsSourceTarget(graph [][]int) [][]int {var ans [][]intvar path = []int{0}var dfs func(int)dfs = func(curr int) {if curr == len(graph)-1 {ans = append(ans, append([]int{}, path...))return}for _, neighbor := range graph[curr] {path = append(path, neighbor)dfs(neighbor)path = path[:len(path)-1]}}dfs(0)return ans
}

Python版本

class Solution:def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:ans = []path = [0]n = len(graph)def dfs(curr):if curr == n - 1:ans.append(list(path))returnfor neighbor in graph[curr]:path.append(neighbor)dfs(neighbor)path.pop()dfs(0)return ans

复杂度分析

• 时间复杂度：O(2^N * N)，每个节点最多有2种选择（选或不选），路径最长为N
• 空间复杂度：O(N)，递归栈深度和路径存储空间[[6]][[8]]

总结

该问题展示了DFS在图遍历中的典型应用。通过维护路径栈实现回溯，可以高效地遍历所有可能路径。不同语言实现时需要注意：

1. Go/Python需要显式复制路径切片
2. JavaScript通过闭包简化参数传递
3. C++使用vector引用传递提升效率[[4]][[9]]

参考：[[1]][[2]][[5]][[7]]