# 797. 所有可能的路径 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解
访问原文链接：[797. 所有可能的路径 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解](https://leetcode.blog/zh/leetcode/797-all-paths-from-source-to-target)，体验更佳！
力扣链接：[797. 所有可能的路径](https://leetcode.cn/problems/all-paths-from-source-to-target), 难度等级：**中等**。
## LeetCode “797. 所有可能的路径”问题描述
给你一个有 `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）**
## 思路 1
## “深度优先搜索”的模式
深度优先搜索（DFS）是一种经典的图遍历算法，其核心特点是**“尽可能深”**地探索图的分支。DFS 从起始顶点出发，沿着一条路径不断深入，直到到达没有未访问邻接点的顶点，然后回溯到最近的分叉点继续探索。这一过程通过**递归**或**显式栈（迭代法）**实现，形成“后进先出”的搜索顺序，因此 DFS 在非加权图中能快速找到离起点较远的深层节点。
**与 BFS 的对比**：
1. **搜索顺序**：DFS 优先探索深度方向，而广度优先搜索（BFS）按层逐层扩展，形成“先进先出”的队列结构。
2. **适用场景**：DFS 更适合强连通分量或回溯类问题（如迷宫所有路径），而 BFS 擅长最短路径（未加权图）或邻近节点探索（如社交网络好友推荐）。
**DFS 的独特性**：
- **不完全性**：若图无限深或存在环路（未标记已访问），DFS 可能无法终止，而 BFS 总能找到最短路径（未加权图）。
- **“一支笔走到底”** 的搜索风格，使其在回溯剪枝或记录路径时更具灵活性，但也可能错过近邻最优解。
总之，DFS 以深度优先的策略揭示图的纵向结构，其回溯特性与栈的天然结合，使其在路径记录和状态空间探索中表现突出，但需注意处理环路和最优解缺失的局限性。
## 步骤
1. 初始化一个空列表 `paths`，用于存储所有找到的有效路径。
2. 初始化一个堆栈来管理 DFS 遍历。堆栈中的每个元素将存储一个 pair（或元组），其中包含当前 `node` 和到达该节点所采用的 `path`。
3. 将起始状态加入到堆栈：初始节点 `0` 和一个空的路径列表（例如 `(0, [])`）。
4. 当堆栈不为空时：
- 从堆栈中弹出顶部元素，检索当前 `node` 及其关联的 `path`。
- 通过将当前 `node` 附加到从堆栈中弹出的 `path` 来创建一个 `currentPath` 数组，它表示通往当前节点并包含当前节点的路径。
- 检查当前 `node` 是否为目标节点（`n - 1`，其中 `n` 是节点总数）。
- 如果它是目标节点，则将 `currentPath` 添加到 `paths` 数组中，因为已经找到了从源节点到目标节点的完整路径。
- 如果不是目标节点，则遍历当前 `node` 可访问的所有 `neighbor` 节点（即遍历 `graph[node]`）。
- 对于每个 `neighbor`，将一个新的 pair（`neighbor` 节点和 `currentPath`）加入到堆栈中。这为遍历探索从邻居节点延伸的路径做好准备。
5. 循环结束后（堆栈为空），返回 `paths` 数组，其中包含从节点 `0` 到节点 `n - 1` 的所有已发现路径。
## 复杂度
- 时间复杂度: `Too complex`.
- 空间复杂度: `Too complex`.
## Python
```python
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
paths = []
stack = [(0, [])]
while stack:
node, path = stack.pop()
if node == len(graph) - 1:
paths.append(path + [node])
continue
for target_node in graph[node]:
stack.append((target_node, path + [node]))
return paths
```
## Java
```java
class Solution {
public List> allPathsSourceTarget(int[][] graph) {
List> paths = new ArrayList<>();
// Each element in the stack is a pair: (current_node, current_path)
Stack>> stack = new Stack<>();
List initialPath = new ArrayList<>();
stack.push(new Pair<>(0, initialPath));
int targetNode = graph.length - 1;
while (!stack.isEmpty()) {
var current = stack.pop();
int node = current.getKey();
var path = current.getValue();
var nextPath = new ArrayList<>(path);
nextPath.add(node);
if (node == targetNode) {
paths.add(nextPath);
continue;
}
for (int neighbor : graph[node]) {
stack.push(new Pair<>(neighbor, nextPath));
}
}
return paths;
}
}
```
## C++
```cpp
class Solution {
public:
vector> allPathsSourceTarget(vector>& graph) {
vector> paths;
// Stack stores pairs of (current_node, current_path)
stack>> s;
s.push({0, {}}); // Start at node 0 with an empty path initially
int targetNode = graph.size() - 1;
while (!s.empty()) {
auto node_path = s.top();
s.pop();
int node = node_path.first;
vector path = node_path.second;
// Add the current node to the path
path.push_back(node);
if (node == targetNode) {
paths.push_back(path); // Found a path to the target
continue;
}
// Explore neighbors
for (int neighbor : graph[node]) {
s.push({neighbor, path});
}
}
return paths;
}
};
```
## JavaScript
```javascript
/**
* @param {number[][]} graph
* @return {number[][]}
*/
var allPathsSourceTarget = function(graph) {
const paths = [];
// Stack stores arrays: [current_node, current_path]
const stack = [[0, []]]; // Start at node 0 with an empty path
const targetNode = graph.length - 1;
while (stack.length > 0) {
const [node, path] = stack.pop();
// Create the new path by appending the current node
const currentPath = [...path, node];
if (node === targetNode) {
paths.push(currentPath); // Found a path
continue;
}
// Explore neighbors
for (const neighbor of graph[node]) {
stack.push([neighbor, currentPath]); // Push neighbor and the path so far
}
}
return paths;
};
```
## C#
```csharp
public class Solution {
public IList> AllPathsSourceTarget(int[][] graph)
{
var paths = new List>();
// Stack stores tuples: (current_node, current_path)
var stack = new Stack<(int node, List path)>();
stack.Push((0, new List())); // Start at node 0
int targetNode = graph.Length - 1;
while (stack.Count > 0)
{
var (node, path) = stack.Pop();
var currentPath = new List(path);
currentPath.Add(node);
if (node == targetNode)
{
paths.Add(currentPath); // Found a path
continue;
}
// Explore neighbors
foreach (int neighbor in graph[node])
{
stack.Push((neighbor, currentPath)); // Push neighbor and the path so far
}
}
return paths;
}
}
```
## Go
```go
type StackItem struct {
Node int
Path []int
}
func allPathsSourceTarget(graph [][]int) [][]int {
var paths [][]int
stack := []StackItem{{Node: 0, Path: []int{}}} // Start at node 0
targetNode := len(graph) - 1
for len(stack) > 0 {
currentItem := stack[len(stack) - 1] // Pop from stack
stack = stack[:len(stack) - 1]
node := currentItem.Node
path := currentItem.Path
newPath := append([]int(nil), path...)
newPath = append(newPath, node)
if node == targetNode {
paths = append(paths, newPath) // Found a path
continue
}
for _, neighbor := range graph[node] {
stack = append(stack, StackItem{Node: neighbor, Path: newPath})
}
}
return paths
}
```
## Ruby
```ruby
# @param {Integer[][]} graph
# @return {Integer[][]}
def all_paths_source_target(graph)
paths = []
# Stack stores arrays: [current_node, current_path]
stack = [[0, []]] # Start at node 0 with an empty path
target_node = graph.length - 1
while !stack.empty?
node, path = stack.pop
# Create the new path by appending the current node
current_path = path + [node]
if node == target_node
paths << current_path # Found a path
next
end
# Explore neighbors
graph[node].each do |neighbor|
stack.push([neighbor, current_path])
end
end
paths
end
```
## Other languages
```java
// Welcome to create a PR to complete the code of this language, thanks!
```
## 思路 2
## “深度优先搜索”的模式
深度优先搜索（DFS）是一种经典的图遍历算法，其核心特点是**“尽可能深”**地探索图的分支。DFS 从起始顶点出发，沿着一条路径不断深入，直到到达没有未访问邻接点的顶点，然后回溯到最近的分叉点继续探索。这一过程通过**递归**或**显式栈（迭代法）**实现，形成“后进先出”的搜索顺序，因此 DFS 在非加权图中能快速找到离起点较远的深层节点。
**与 BFS 的对比**：
1. **搜索顺序**：DFS 优先探索深度方向，而广度优先搜索（BFS）按层逐层扩展，形成“先进先出”的队列结构。
2. **适用场景**：DFS 更适合强连通分量或回溯类问题（如迷宫所有路径），而 BFS 擅长最短路径（未加权图）或邻近节点探索（如社交网络好友推荐）。
**DFS 的独特性**：
- **不完全性**：若图无限深或存在环路（未标记已访问），DFS 可能无法终止，而 BFS 总能找到最短路径（未加权图）。
- **“一支笔走到底”** 的搜索风格，使其在回溯剪枝或记录路径时更具灵活性，但也可能错过近邻最优解。
总之，DFS 以深度优先的策略揭示图的纵向结构，其回溯特性与栈的天然结合，使其在路径记录和状态空间探索中表现突出，但需注意处理环路和最优解缺失的局限性。
## “递归”的模式
递归（Recursion）是计算机科学和数学中的一个重要概念，指的是 一个函数在其定义中 **直接或间接调用自身** 的方法。
### 递归的核心思想
- **自我调用**：函数在执行过程中调用自身。
- **基线情况**：相当于终止条件。到达基线情况后，就可以返回结果了，不需要再递归调用，防止无限循环。
- **递归步骤**：问题逐步向“基线情况”靠近的步骤。
## 步骤
1. 初始化一个空数组 `paths`，用于存储从源节点到目标节点找到的所有有效路径。
2. 定义一个递归深度优先搜索 (DFS) 函数，例如 `dfs`，它将当前 `node` 和 `path`（即迄今为止访问过的节点列表，用于到达当前节点）作为输入。
3. 在 `dfs` 函数内部：
- 通过将当前 `node` 附加到 `path` 来创建一个新的路径列表。我们将其称为 `newPath`。
- 检查当前 `node` 是否为目标节点（`n - 1`，其中 `n` 是节点总数）。
- 如果是目标节点，则表示我们找到了一条完整的路径。将 `newPath` 添加到主 `paths` 数组中，并从此递归调用返回。
- 如果当前 `node` 不是目标节点，则遍历所有可从当前 `node` 访问的 `neighbor` 节点（即遍历 `graph[node]`）。
- 对于每个 `neighbor`，以 `neighbor` 作为新的当前节点，以 `newPath` 作为到达该节点的路径，对 `dfs` 进行递归调用 (`dfs(neighbor, newPath)`)。
4. 通过使用源节点 `0` 和空的初始路径 (`dfs(0, [])`) 调用 `dfs` 函数来启动该过程。
5. 初始 `dfs` 调用完成后，返回包含所有已发现路径的 `paths` 数组。
## 复杂度
- 时间复杂度: `Too complex`.
- 空间复杂度: `Too complex`.
## Python
```python
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
self.paths = []
self.graph = graph
self.target = len(graph) - 1
self.dfs(0, []) # Start DFS from node 0 with an empty initial path
return self.paths
def dfs(self, node, path):
current_path = path + [node]
if node == self.target: # Base case
self.paths.append(current_path)
return
for neighbor in self.graph[node]: # Recursive step: Explore neighbors
self.dfs(neighbor, current_path)
```
## Java
```java
class Solution {
private List> paths;
private int[][] graph;
private int targetNode;
public List> allPathsSourceTarget(int[][] graph) {
this.paths = new ArrayList<>();
this.graph = graph;
this.targetNode = graph.length - 1;
List initialPath = new ArrayList<>();
dfs(0, initialPath); // Start DFS from node 0 with an empty initial path
return paths;
}
private void dfs(int node, List currentPath) {
List newPath = new ArrayList<>(currentPath);
newPath.add(node);
if (node == targetNode) { // Base case
paths.add(newPath);
return;
}
for (int neighbor : graph[node]) { // Recursive step: Explore neighbors
dfs(neighbor, newPath);
}
}
}
```
## C++
```cpp
class Solution {
public:
vector> allPathsSourceTarget(vector>& graph) {
_graph = graph;
vector initial_path; // Empty initial path
dfs(0, initial_path); // Start DFS from node 0
return _paths;
}
private:
vector> _paths;
vector> _graph;
void dfs(int node, vector current_path) {
current_path.push_back(node);
if (node == _graph.size() - 1) { // Base case
_paths.push_back(current_path);
return;
}
for (int neighbor : _graph[node]) { // Recursive step: Explore neighbors
dfs(neighbor, current_path);
}
}
};
```
## JavaScript
```javascript
let paths
let graph
var allPathsSourceTarget = function (graph_) {
paths = []
graph = graph_
dfs(0, [])
return paths
}
function dfs(node, currentPath) {
const newPath = [...currentPath, node]
if (node === graph.length - 1) { // Base case
paths.push(newPath)
return
}
for (const neighbor of graph[node]) { // Recursive step: Explore neighbors
dfs(neighbor, newPath)
}
}
```
## C#
```csharp
public class Solution
{
private IList> paths;
private int[][] graph;
private int targetNode;
public IList> AllPathsSourceTarget(int[][] graph)
{
this.paths = new List>();
this.graph = graph;
this.targetNode = graph.Length - 1;
Dfs(0, new List());
return paths;
}
private void Dfs(int node, List currentPath)
{
var newPath = new List(currentPath);
newPath.Add(node);
if (node == targetNode) // Base case
{
paths.Add(newPath);
return;
}
foreach (int neighbor in graph[node]) // Recursive step: Explore neighbors
{
Dfs(neighbor, newPath);
}
}
}
```
## Go
```go
var (
paths [][]int
graph [][]int
targetNode int
)
func allPathsSourceTarget(graph_ [][]int) [][]int {
paths = [][]int{}
graph = graph_
targetNode = len(graph) - 1
dfs(0, []int{})
return paths
}
func dfs(node int, currentPath []int) {
newPath := append([]int(nil), currentPath...)
newPath = append(newPath, node)
if node == targetNode { // Base case
paths = append(paths, newPath)
return
}
for _, neighbor := range graph[node] { // Recursive step: Explore neighbors
dfs(neighbor, newPath)
}
}
```
## Ruby
```ruby
def all_paths_source_target(graph)
@paths = []
@graph = graph
dfs(0, [])
@paths
end
def dfs(node, current_path)
new_path = current_path + [node]
if node == @graph.size - 1 # Base case
@paths << new_path
return
end
@graph[node].each do |neighbor| # Recursive step: Explore neighbors
dfs(neighbor, new_path)
end
end
```
## Other languages
```java
// Welcome to create a PR to complete the code of this language, thanks!
```
## 思路 3
## “深度优先搜索”的模式
深度优先搜索（DFS）是一种经典的图遍历算法，其核心特点是**“尽可能深”**地探索图的分支。DFS 从起始顶点出发，沿着一条路径不断深入，直到到达没有未访问邻接点的顶点，然后回溯到最近的分叉点继续探索。这一过程通过**递归**或**显式栈（迭代法）**实现，形成“后进先出”的搜索顺序，因此 DFS 在非加权图中能快速找到离起点较远的深层节点。
**与 BFS 的对比**：
1. **搜索顺序**：DFS 优先探索深度方向，而广度优先搜索（BFS）按层逐层扩展，形成“先进先出”的队列结构。
2. **适用场景**：DFS 更适合强连通分量或回溯类问题（如迷宫所有路径），而 BFS 擅长最短路径（未加权图）或邻近节点探索（如社交网络好友推荐）。
**DFS 的独特性**：
- **不完全性**：若图无限深或存在环路（未标记已访问），DFS 可能无法终止，而 BFS 总能找到最短路径（未加权图）。
- **“一支笔走到底”** 的搜索风格，使其在回溯剪枝或记录路径时更具灵活性，但也可能错过近邻最优解。
总之，DFS 以深度优先的策略揭示图的纵向结构，其回溯特性与栈的天然结合，使其在路径记录和状态空间探索中表现突出，但需注意处理环路和最优解缺失的局限性。
## 步骤
1. 初始化一个空列表 `paths`，用于存储从源节点到目标节点找到的所有有效路径。
2. 创建一个可变列表 `path`，用于跟踪当前正在探索的路径，初始仅包含源节点 `0`。
3. 实现一个使用回溯法探索路径的递归 DFS 函数：
- 基线情况：如果当前节点是目标节点 (`n-1`)，则复制当前路径并将其添加到 `paths` 列表中。
- 递归步骤：对于当前节点的每个邻居：
- 将邻居添加到当前路径。
- 使用此邻居递归调用 DFS 函数。
- 递归调用返回后，从路径中删除邻居（回溯）。
4. 从源节点 `0` 开始 DFS。
5. DFS 完成后，返回收集到的 `paths`。
## 复杂度
- 时间复杂度: `Too complex`.
- 空间复杂度: `Too complex`.
## Python
```python
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
self.paths = []
self.graph = graph
self.path = [0] # Important
self.dfs(0)
return self.paths
def dfs(self, node):
if node == len(self.graph) - 1:
self.paths.append(self.path.copy()) # Important
return
for neighbor in self.graph[node]:
self.path.append(neighbor) # Important
self.dfs(neighbor)
self.path.pop() # Important
```
## Java
```java
class Solution {
private List> paths = new ArrayList<>();
private List path = new ArrayList<>(List.of(0)); // Important - start with node 0
private int[][] graph;
public List> allPathsSourceTarget(int[][] graph) {
this.graph = graph;
dfs(0);
return paths;
}
private void dfs(int node) {
if (node == graph.length - 1) { // Base case
paths.add(new ArrayList<>(path)); // Important - make a copy
return;
}
for (int neighbor : graph[node]) { // Recursive step
path.add(neighbor); // Important
dfs(neighbor);
path.remove(path.size() - 1); // Important - backtrack
}
}
}
```
## C++
```cpp
class Solution {
public:
vector> allPathsSourceTarget(vector>& graph) {
_graph = graph;
_path = {0}; // Important - start with node 0
dfs(0);
return _paths;
}
private:
vector> _paths;
vector> _graph;
vector _path;
void dfs(int node) {
if (node == _graph.size() - 1) { // Base case
_paths.push_back(_path); // Important - copy is made automatically
return;
}
for (int neighbor : _graph[node]) { // Recursive step
_path.push_back(neighbor); // Important
dfs(neighbor);
_path.pop_back(); // Important - backtrack
}
}
};
```
## JavaScript
```javascript
/**
* @param {number[][]} graph
* @return {number[][]}
*/
var allPathsSourceTarget = function(graph) {
const paths = [];
const path = [0]; // Important - start with node 0
function dfs(node) {
if (node === graph.length - 1) { // Base case
paths.push([...path]); // Important - make a copy
return;
}
for (const neighbor of graph[node]) { // Recursive step
path.push(neighbor); // Important
dfs(neighbor);
path.pop(); // Important - backtrack
}
}
dfs(0);
return paths;
};
```
## C#
```csharp
public class Solution
{
private IList> paths = new List>();
private List path = new List { 0 }; // Important - start with node 0
private int[][] graph;
public IList> AllPathsSourceTarget(int[][] graph)
{
this.graph = graph;
Dfs(0);
return paths;
}
private void Dfs(int node)
{
if (node == graph.Length - 1)
{ // Base case
paths.Add(new List(path)); // Important - make a copy
return;
}
foreach (int neighbor in graph[node])
{ // Recursive step
path.Add(neighbor); // Important
Dfs(neighbor);
path.RemoveAt(path.Count - 1); // Important - backtrack
}
}
}
```
## Go
```go
func allPathsSourceTarget(graph [][]int) [][]int {
paths := [][]int{}
path := []int{0} // Important - start with node 0
var dfs func(int)
dfs = func(node int) {
if node == len(graph) - 1 { // Base case
// Important - make a deep copy of the path
paths = append(paths, append([]int(nil), path...))
return
}
for _, neighbor := range graph[node] { // Recursive step
path = append(path, neighbor) // Important
dfs(neighbor)
path = path[:len(path) - 1] // Important - backtrack
}
}
dfs(0)
return paths
}
```
## Ruby
```ruby
# @param {Integer[][]} graph
# @return {Integer[][]}
def all_paths_source_target(graph)
@paths = []
@graph = graph
@path = [0] # Important - start with node 0
dfs(0)
@paths
end
def dfs(node)
if node == @graph.length - 1 # Base case
@paths << @path.clone # Important - make a copy
return
end
@graph[node].each do |neighbor| # Recursive step
@path << neighbor # Important
dfs(neighbor)
@path.pop # Important - backtrack
end
end
```
## Other languages
```java
// Welcome to create a PR to complete the code of this language, thanks!
```
亲爱的力扣人，为了您更好的刷题体验，请访问 [LeetCode.blog](https://leetcode.blog/zh)。
本站敢称力扣题解最佳实践，终将省你大量刷题时间！
原文链接：[797. 所有可能的路径 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解](https://leetcode.blog/zh/leetcode/797-all-paths-from-source-to-target).
GitHub 仓库: [leetcode-python-java](https://github.com/leetcode-python-java/leetcode-python-java).