LeetCode Algorithm 797. 所有可能的路径
本文将详细介绍LeetCode上的算法题目"797. 所有可能的路径"的解法。该题目要求我们找出从给定的起始节点到目标节点的所有可能路径。在下文中，我们将逐步解释问题的背景和要求，并提供一种基于深度优先搜索(DFS)的解决方案。
问题背景和要求
在给定的有向无环图中，节点从0到n-1编号。每个节点用一个列表来表示其邻居节点。现在，给定起始节点start和目标节点target，我们需要找到所有从start到target的可能路径。
我们需要返回一个包含所有路径的列表，每个路径以列表形式表示，例如:[[0,1,3],[0,2,3]]。每个路径必须满足的条件是从起始节点0到目标节点target的每个路径，而且不能有环存在。例如，在路径[0,1,3]中，节点1不能再次出现。
示例
让我们通过一个示例来更好地理解这个问题的要求和限制。
示例输入
graph = [[1,2],[3],[3],[]]
start = 0
target = 3
在这个例子中，我们有一个有向无环图，其邻居关系如下所示：
0 ------> 1
| \
| \
↓ \
2 ----> 3
给定的起始节点是0，目标节点是3。我们的目标是找到所有从0到3的可能路径。
解决方案
为了解决这个问题，我们可以使用深度优先搜索(DFS)来遍历所有可能的路径。在DFS的过程中，我们需要跟踪当前路径和已访问的节点，以避免重复访问。
我们可以定义一个递归函数helper来实现DFS。在每次递归调用中，我们需要判断当前节点是否为目标节点。如果是，我们将当前路径添加到结果列表中。否则，我们将遍历当前节点的邻居节点，并对每个邻居节点进行递归调用。
下面是基于Python的实现代码：
def allPathsSourceTarget(graph):
paths = []
target = len(graph) - 1
def dfs(curr_node, path):
if curr_node == target:
paths.append(path)
else:
for neighbor in graph[curr_node]:
dfs(neighbor, path + [neighbor])
dfs(0, [0])
return paths
在主函数allPathsSourceTarget中，我们初始化结果列表paths和目标节点target。然后，我们调用递归函数dfs，传入起始节点0和初始路径[0]。
在dfs函数中，我们首先检查当前节点是否为目标节点。如果是，我们将当前路径添加到结果列表中。否则，我们需要遍历当前节点的邻居节点。对于每个邻居节点，我们通过相应的递归调用，将邻居节点添加到当前路径中并继续探索。
算法分析
下面将对上述算法进行分析。
时间复杂度
在最坏情况下，图中的每个节点都与其他节点相连。因此，时间复杂度为O(n * 2^n)，其中n是节点的数量。
空间复杂度
在递归过程中，最多可能有2^n条路径。每条路径的长度最多为n。所以，空间复杂度是O(n * 2^n)。
总结
本文介绍了LeetCode上算法题目"797. 所有可能的路径"的解决方法。通过深度优先搜索算法，我们可以找到从给定的起始节点到目标节点的所有可能路径。经过算法分析，我们了解到该算法的时间复杂度和空间复杂度。
通过这道题目的解析，我们学习到了如何使用DFS算法解决路径相关的问题，并且对DFS的原理和应用有了更深入的认识。希望本文对你理解并解决类似问题有所帮助！