Leetcode 797. All Paths From Source to Target
Problem Explanation
You are given a directed, acyclic graph (DAG) made up of N nodes. The graph is described by an array where the index i
represents a node and the elements of graph[i]
represent its outgoing edges. You need to find all possible paths from node 0 to node N-1 and return the paths in any order. However, within each path, nodes should be in order.
Taking the example of [[1,2], [3], [3], []]
, the nodes and their respective edges are represented as follows:
1 2 30 -> 1, 2 41 -> 3 52 -> 3 63 ->
This can be visually represented as:
1 2 30--->1 4| | 5v v 62--->3
In this case, there are two paths from node 0 to node N-1 (which is node 3 in this case): 0 -> 1 -> 3
and 0 -> 2 -> 3
Solution Approach
This problem can be solved using a depth-first search (DFS) algorithm. DFS is typically used for traversing or searching through a graph (or tree) and allows us to visit every possible node in the graph.
Our DFS function will start at node 0 (the source), from where it will explore all possible paths to node N-1 (the target). As it traverse through the graph, it will keep adding nodes to the current path. If it reaches the target node, the current path is added to the list of all paths. If it reaches a node with no further outgoing edges, it backtracks by removing the last node from the current path and continue exploring other possible paths.
More specifically, for each node u
, we traverse each v
in graph[u]
. If v
is our target (the node N-1), we add our path to the result. For non-target nodes, we add v
to our path and recursively call our DFS function with v
as our new node.
Here is a step-by-step walk through of the above approach using the given example:
- Start at node
0
. Path =[0]
- Traverse to node
1
(which is the first element ingraph[0]
). Path =[0,1]
- Traverse to node
3
(which is the only element ingraph[1]
). Since this is our target, we add the path[0,1,3]
to our result and backtrack to node1
. Path =[0,1]
- As there are no more elements in
graph[1]
, we backtrack to node0
. Path =[0]
- Traverse to node
2
(which is the next element ingraph[0]
). Path =[0,2]
- Traverse to node
3
(which is the only element ingraph[2]
). Add the path[0,2,3]
to our result. Now, as there are no more nodes to visit, our search ends.
Our final output is [[0,1,3],[0,2,3]]
which represents all possible paths from node 0
to node 3
.
Python Solution
1 2python 3class Solution: 4 def allPathsSourceTarget(self, graph): 5 def dfs(u, path): 6 if u == len(graph) - 1: # if we reach target, add path to result 7 res.append(path) 8 return 9 for v in graph[u]: # for each node, traverse all its neighbors 10 dfs(v, path + [v]) # recursively call dfs with new node 11 12 res = [] 13 dfs(0, [0]) # start dfs from node 0 14 return res
Java Solution
1
2java
3import java.util.*;
4
5class Solution {
6 List<List<Integer>> res = new ArrayList<>();
7
8 public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
9 dfs(graph, 0, new LinkedList<Integer>() {{
10 add(0);
11 }});
12 return res;
13 }
14
15 private void dfs(int[][] graph, int u, LinkedList<Integer> path) {
16 if (u == graph.length - 1) { // if we reach target, add path to result
17 res.add(new ArrayList<>(path));
18 return;
19 }
20 for (int v : graph[u]) { // for each node, traverse all its neighbors
21 path.add(v); // add the node to path
22 dfs(graph, v, path); // recursively call dfs with new node
23 path.removeLast(); // backtrack if necessary
24 }
25 }
26}
JavaScript Solution
1
2javascript
3var allPathsSourceTarget = function(graph) {
4 let res = [];
5 dfs(graph, 0, [0]);
6 return res;
7
8 function dfs(graph, u, path) {
9 if(u === graph.length - 1) {
10 res.push(path);
11 return;
12 }
13 for(let v of graph[u]) {
14 dfs(graph, v, [...path, v]);
15 }
16 }
17};
C++ Solution
1
2cpp
3#include <vector>
4
5class Solution {
6 std::vector<std::vector<int>> res;
7
8public:
9 std::vector<std::vector<int>> allPathsSourceTarget(std::vector<std::vector<int>>& graph) {
10 std::vector<int> path{0};
11 dfs(graph, 0, path);
12 return res;
13 }
14
15 void dfs(std::vector<std::vector<int>>& graph, int u, std::vector<int>& path) {
16 if(u == graph.size()-1) {
17 res.push_back(path);
18 return;
19 }
20 for(auto &v: graph[u]) {
21 path.push_back(v);
22 dfs(graph, v, path);
23 path.pop_back();
24 }
25 }
26};
C# Solution
1
2csharp
3public class Solution {
4 List<IList<int>> result = new List<IList<int>>();
5 int target;
6 int[][] graph;
7
8 public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
9 target = graph.Length - 1;
10 this.graph = graph;
11 DFS(0, new List<int>(new int[]{ 0 }));
12 return result;
13 }
14
15 public void DFS(int node, List<int> path) {
16 if(node == target)
17 result.Add(new List<int>(path));
18
19 foreach(int nei in graph[node]) {
20 path.Add(nei);
21 DFS(nei, path);
22 path.RemoveAt(path.Count - 1);
23 }
24 }
25}
In the python, java, javascript, c++ and c# code, both the BFS and DFS algorithm loops through each element of the graph and traverses it. If the target is reached, it is added to the result. The path is backtracked if necessary. The main difference between the codes is how the elements are represented and traversed in different languages.## Ruby Solution
1
2ruby
3def all_paths_source_target(graph)
4 res = []
5 dfs(graph, 0, [0], res)
6 return res
7end
8
9def dfs(graph, node, path, res)
10 if node == graph.length - 1
11 res << path.dup
12 return
13 end
14
15 graph[node].each do |nei|
16 path << nei
17 dfs(graph, nei, path, res)
18 path.pop
19 end
20end
The ruby code follows the same approach of BFS and DFS algorithm seen in the previous codes. In Ruby however, handling of collections like graphs and arrays is different and operations can be performed on them using different collection methods provided natively by Ruby.
Swift Solution
1
2swift
3class Solution {
4 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
5 var res = [[Int]]()
6 dfs(graph, 0, [0], &res)
7 return res
8 }
9
10 private func dfs(_ graph: [[Int]], _ node: Int, _ path: [Int], _ res: inout [[Int]]) {
11 if node == graph.count - 1 {
12 res.append(path)
13 return
14 }
15
16 for nei in graph[node] {
17 dfs(graph, nei, path + [nei], &res)
18 }
19 }
20}
In Swift, the Breadth-First-Search(BFS) and Depth-First-Search(DFS) algorithm is implemented similarly to Java, Python, and JavaScript. The path is backtracked if necessary. The graph traversal operations, adding elements to list and calling recursive function with new parameters are achieved in the same way.
Kotlin Solution
1
2kotlin
3class Solution {
4 fun allPathsSourceTarget(graph: Array<IntArray>) : List<List<Int>> {
5 val paths: MutableList<List<Int>> = mutableListOf()
6 val pathNodes: Stack<Int> = Stack()
7 pathNodes.push(0)
8 dfs(0, graph, pathNodes, paths)
9 return paths
10 }
11
12 private fun dfs(node: Int, graph: Array<IntArray>, pathNodes: Stack<Int>, paths: MutableList<List<Int>>) {
13 if (node == graph.size - 1) {
14 paths.add(pathNodes.toList())
15 } else {
16 for (nextNode in graph[node]) {
17 pathNodes.push(nextNode)
18 dfs(nextNode, graph, pathNodes, paths)
19 pathNodes.pop()
20 }
21 }
22 }
23}
Similar to the previous solutions, Kotlin uses DFS to navigate through the graph. The current node is pushed onto the stack and the function is recursively called again for that node. If the node is a target, the current path is added to the list of all paths. If the current node does not have any neighbors or if all its neighbors have been explored then we backtrack using pathNodes.pop()
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.