Medium

题目描述

给你一个有 n 个节点的 有向无环图（DAG），节点编号从 0 到 n - 1，请你找出所有从节点 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）

解题思路

这道题要求找出从节点 0 到节点 n-1 的所有可能路径，是一个典型的图遍历问题。

主要思路：

由于题目保证了图是有向无环图（DAG），我们可以使用深度优先搜索（DFS）+ 回溯的方法来解决。从起始节点 0 开始，递归地探索每一个可能的邻接节点，当到达目标节点 n-1 时，将当前路径加入结果集。

算法步骤：

  1. 初始化结果列表和当前路径，将起始节点 0 加入当前路径
  2. 从节点 0 开始进行 DFS 遍历
  3. 对于当前节点，遍历其所有邻接节点：
    • 将邻接节点加入当前路径
    • 如果邻接节点是目标节点，将当前路径的副本加入结果
    • 否则递归探索该邻接节点
    • 回溯：将邻接节点从当前路径中移除
  4. 返回所有找到的路径

这种方法的优势在于不需要额外的访问标记数组，因为图是无环的，不会出现重复访问的情况。算法的时间复杂度取决于路径的数量，在最坏情况下为指数级别。

代码实现

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

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def dfs(node, target, path, result):
            if node == target:
                result.append(path[:])
                return
            
            for next_node in graph[node]:
                path.append(next_node)
                dfs(next_node, target, path, result)
                path.pop()
        
        result = []
        path = [0]
        dfs(0, len(graph) - 1, path, result)
        return result

public class Solution {
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        var result = new List<IList<int>>();
        var path = new List<int> { 0 };
        DFS(graph, 0, graph.Length - 1, path, result);
        return result;
    }
    
    private void DFS(int[][] graph, int node, int target, 
                     List<int> path, IList<IList<int>> result) {
        if (node == target) {
            result.Add(new List<int>(path));
            return;
        }
        
        foreach (int next in graph[node]) {
            path.Add(next);
            DFS(graph, next, target, path, result);
            path.RemoveAt(path.Count - 1);
        }
    }
}

var allPathsSourceTarget = function(graph) {
    const result = [];
    const target = graph.length - 1;
    
    function dfs(node, path) {
        if (node === target) {
            result.push([...path]);
            return;
        }
        
        for (const neighbor of graph[node]) {
            path.push(neighbor);
            dfs(neighbor, path);
            path.pop();
        }
    }
    
    dfs(0, [0]);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^N × N)，其中 N 是节点数量。在最坏情况下，可能存在 2^N 条路径，每条路径长度最多为 N
空间复杂度O(2^N × N)，用于存储所有可能的路径。递归调用栈的深度最多为 N

相关题目