LeetCode 797 – All Paths From Source to Target

题目概述

在这道题目中，我们给定一个有向图，图中的节点编号从 0 到 n - 1，图是通过一个邻接表的形式给出的。我们的目标是找到从节点 0 到节点 n-1 的所有路径。

题目要求：

  1. 给定图的邻接表，找到从源节点（0）到目标节点（n-1）的所有路径。
  2. 每条路径为一个从 0 到 n-1 的节点序列。

示例

输入: graph = [[1,2], [3], [3], []]
输出: [[0,1,3], [0,2,3]]
解释: 图中的所有路径是：
[0, 1, 3]
[0, 2, 3]

题目分析

  1. 图的表示：图是通过一个邻接表来表示的，graph[i] 是一个列表，表示从节点 i 出发可以访问的所有节点。
  2. 路径问题：我们需要找到从 0 到目标节点 n-1 的所有路径，可以用图的深度优先搜索（DFS）或广度优先搜索（BFS）来解决这个问题。由于路径是从源节点出发的，因此深度优先搜索是一个自然的选择。

解决思路

  1. DFS 深度优先搜索：可以使用 DFS 进行图的遍历。在每次递归中，我们把当前节点加入路径中，并递归访问其邻接节点。
  2. 递归终止条件：当我们到达目标节点 n-1 时，说明找到了一条路径，此时可以将路径保存。
  3. 回溯：每次递归返回时，需要撤销当前节点的选择，继续探索其它路径。

算法步骤

  1. 定义一个 dfs 函数，递归遍历图的每一条路径。
  2. 在每个节点上，将当前节点加入路径，然后继续递归访问它的邻接节点。
  3. 当到达目标节点 n-1 时，保存当前路径。
  4. 回溯并继续探索其它路径。
  5. 最后返回所有路径。

Python 代码实现

class Solution:
    def allPathsSourceTarget(self, graph):
        self.res = []  # 用于存储所有路径
        self.dfs(graph, 0, [])  # 从源节点 0 开始递归
        return self.res
    
    def dfs(self, graph, node, path):
        # 将当前节点加入路径
        path.append(node)
        
        # 如果到达目标节点 n-1，则保存当前路径
        if node == len(graph) - 1:
            self.res.append(list(path))  # 复制路径，防止后续修改
        else:
            # 遍历当前节点的所有邻接节点
            for neighbor in graph[node]:
                self.dfs(graph, neighbor, path)
        
        # 回溯，将当前节点从路径中移除
        path.pop()

详细解释

  1. allPathsSourceTarget 函数：
    • 这个函数是主函数，接受图 graph 作为输入，初始化一个结果列表 self.res 来存储最终的路径。
    • 然后调用 dfs 函数，传入当前的图、起始节点 0 和一个空的路径 []。
  2. dfs 函数：
    • dfs 是一个递归函数，接受当前图 graph，当前节点 node，以及当前的路径 path。
    • 在每次递归时，首先将当前节点 node 加入到路径 path 中。
    • 如果当前节点是目标节点 n-1，说明路径找到，保存当前路径。
    • 否则，对于每个当前节点的邻接节点，递归调用 dfs 来继续探索路径。
    • 最后，通过 path.pop() 回溯，移除当前节点，继续探索其它路径。

时间复杂度

  • 时间复杂度：每个节点最多会被访问一次，并且每次递归时会将一个节点添加到路径中。最坏情况下，图中有 n 个节点，每个节点有 n 个邻接节点，因此总时间复杂度是 O(2^n)，因为每个节点都可能有多个路径可以走。
  • 空间复杂度：空间复杂度主要由递归的深度和存储路径的空间组成。递归的深度最大为图的节点数 n，因此空间复杂度为 O(n)。此外，我们还要存储所有可能的路径，最坏情况下路径的数量为 2^n，因此空间复杂度为 O(2^n)。

示例

假设输入图 graph = [[1, 2], [3], [3], []]，我们从节点 0 出发，递归遍历图的每一条路径：

  1. 从 0 到 1，然后再到 3，得到路径 [0, 1, 3]。
  2. 从 0 到 2，然后再到 3，得到路径 [0, 2, 3]。

最终返回的结果是 [[0, 1, 3], [0, 2, 3]]。

总结

通过使用 DFS，我们能够高效地找到从源节点到目标节点的所有路径。回溯的思想在路径查找中非常有用，它帮助我们探索所有可能的路径，并在每条路径结束时保存结果。该解法对于小规模图来说非常有效，但在图非常大的时候可能会遇到性能瓶颈。