0797 All Paths From Source to Target#
Problem#
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.
The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).
Examples#
Example 1:
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Example 2:
Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
Constraints:#
n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i (i.e., there will be no self-loops).
All the elements of graph[i] are unique.
The input graph is guaranteed to be a DAG.
# DFS
def allPathsSourceTarget(graph):
n = len(graph)
def dfs(path):
# stop when s == t
if path[-1] == n-1:
# return results
res.append(path)
# recursion on neighbors:
# Note we cannot use path.append(v) here as list.append() returns None
for v in graph[path[-1]]:
dfs(path+[v])
res = []
path = [0]
dfs(path)
return res
# test
graph = [[1,2],[3],[3],[]]
print(allPathsSourceTarget(graph))
[[0, 1, 3], [0, 2, 3]]
# The following commented block is a wrong implementation
'''
def allPathsSourceTarget(graph):
n = len(graph)
path = []
def dfs(graph, s, t):
path.append(s)
# stop when s == t
if s == t:
# return results
res.append(path)
#if we add return here, the result will be [].
#because we have pop() the node s from path, so the path is empty,
#and if we don't add return here, we will get the result [0,1,3] and [0,2,3]
# recursion
for v in graph[s]:
dfs(graph, v, t)
# remove node s from path
path.pop()
res = []
dfs(graph, 0, n-1)
return res
'''
# A fix is:
def allPathsSourceTarget(graph):
n = len(graph)
path = []
def dfs(graph, s, t, path):
print("in node:",s)
path.append(s)
print(path)
# stop when s == t
if s == t:
# return results
res.append(path)
print("s==t")
print(res)
return
# recursion
for v in graph[s]:
dfs(graph, v, t, path)
# remove node s from path
path.pop()
res = []
dfs(graph, 0, n-1, path)
return res
# test
graph = [[1,2],[3],[3],[]]
print(allPathsSourceTarget(graph))
in node: 0
[0]
in node: 1
[0, 1]
in node: 3
[0, 1, 3]
s==t
[[0, 1, 3]]
in node: 2
[0, 1, 2]
in node: 3
[0, 1, 2, 3]
s==t
[[0, 1, 2, 3], [0, 1, 2, 3]]
[[0, 1], [0, 1]]
# A fix is:
def allPathsSourceTarget(graph):
n = len(graph)
path = []
def dfs(graph, s, t, path):
# add s to path
path.append(s)
# stop when s == t
if s == t:
# return results -> this is python/java related
# if we dont use path[:], which copies as a new list the original list, the res will be empty.
# the reason is:
# there is only one `path` during the DFS recursions. Once the recursion finishes, and goes back to the root, due to the use of `pop`, path will be empty.
# python copies the object address to realize the transferring of the object at different layers. if we dont copy the path after each call, the same address will be appended to res, which in the end will be empty due to the pop operation.
res.append(path[:])
# the key of backtracking is to go back to original state by undo previous actions.
print("s=====t")
print(path)
# if we use return here, we have to pop the last element in the path to ensure path goes to its original state before the recusion call
path.pop()
return
# recursion
for v in graph[s]:
dfs(graph, v, t, path)
# undo adding s to path
path.pop()
res = []
dfs(graph, 0, n-1, path)
return res
# test
graph = [[1,2],[3],[3],[]]
print(allPathsSourceTarget(graph))
s=====t
[0, 1, 3]
s=====t
[0, 2, 3]
[[0, 1, 3], [0, 2, 3]]
# Another fix is:
def allPathsSourceTarget(graph):
n = len(graph)
path = []
def dfs(graph, s, t, path):
print("in node:",s)
path.append(s)
print(path)
# stop when s == t
if s == t:
# return results
res.append(path[:])
# recursion
for v in graph[s]:
dfs(graph, v, t, path)
# remove node s from path
path.pop()
res = []
dfs(graph, 0, n-1, path)
return res
# test
graph = [[1,2],[3],[3],[]]
print(allPathsSourceTarget(graph))
in node: 0
[0]
in node: 1
[0, 1]
in node: 3
[0, 1, 3]
in node: 2
[0, 2]
in node: 3
[0, 2, 3]
[[0, 1, 3], [0, 2, 3]]
# Another fix is:
def allPathsSourceTarget(graph):
n = len(graph)
path = []
def dfs(graph, s, t, path):
print("in node:",s)
path.append(s)
print(path)
# stop when s == t
if s == t:
# return results
res.append(path[:])
# here we dont need pop because we use a copy of path for recursion, which means the original path variable will not be changed during recusive calls.
# recursion
for v in graph[s]:
dfs(graph, v, t, path[:])
# remove node s from path
path.pop()
res = []
dfs(graph, 0, n-1, path)
return res
# test
graph = [[1,2],[3],[3],[]]
print(allPathsSourceTarget(graph))
in node: 0
[0]
in node: 1
[0, 1]
in node: 3
[0, 1, 3]
in node: 2
[0, 2]
in node: 3
[0, 2, 3]
[[0, 1, 3], [0, 2, 3]]
Note the fix is possible because list[:] is used in the recursive call to avoid global changes of path every call, which lead to intraceable outputs.
# BFS solution:
def allPathsSourceTarget(graph):
target = len(graph) - 1
paths, targets = [[0]], []
while paths:
print(paths)
path = paths.pop(0)
edges = graph[path[-1]]
if not edges:
continue
for edge in edges:
if edge==target:
targets.append(path+[edge])
else:
paths = [path+[edge]] + paths
return targets
# test
graph = [[1,2],[3],[3],[]]
print(allPathsSourceTarget(graph))
[[0]]
[[0, 2], [0, 1]]
[[0, 1]]
[[0, 2, 3], [0, 1, 3]]