Builds on Flood Fill, which you haven’t finished yet.
Traverse an Adjacency List and Carry a Result (All Paths From Source to Target)
A directed graph has n nodes, numbered 0 to n - 1, and it has no cycle. A directed graph with no cycle is called a DAG. An edge goes from one node to another and can be followed in that direction only.
The graph is given as graph, an adjacency list: graph[i] lists every node that node i has an edge to. A path is a list of nodes in which each node has an edge to the next one.
Find every path that starts at node 0 and ends at node n - 1. Return all of them, in any order.
Graph Paths
adjacency list ➔ walk with one shared path ➔ copy at the target ➔ undo| 1 | from typing import List |
| 2 | |
| 3 | def all_paths(graph: List[List[int]], source: int, target: int) -> List[List[int]]: |
| 4 | """Every path from source to target in a directed graph that has no cycle, given as |
| 5 | an adjacency list. |
| 6 | Precondition: the graph has no cycle, so every walk ends. Finding a cycle is the |
| 7 | Cycle Detection card's job. |
| 8 | Time: O(2^V * V) | Space: O(V) |
| 9 | """ |
| 10 | paths: List[List[int]] = [] # Every finished path, each one a copy |
| 11 | path = [source] # The nodes from source to the node being visited |
| 12 | |
| 13 | def dfs(node: int) -> None: |
| 14 | # 1. Save A Copy At The Target: |
| 15 | # path[:] is a snapshot, because path keeps changing after this call returns. |
| 16 | if node == target: |
| 17 | paths.append(path[:]) |
| 18 | return |
| 19 | |
| 20 | # 2. Extend The Path, Walk, Then Undo: |
| 21 | # No visited set: a node on two paths must be walked once for each path. |
| 22 | for nxt in graph[node]: |
| 23 | path.append(nxt) |
| 24 | dfs(nxt) |
| 25 | path.pop() |
| 26 | |
| 27 | dfs(source) |
| 28 | return paths |
dfs(node) is called, path holds the nodes from source to node, and when dfs(node) returns, path is the same as it was before the call.Every path from source to target is a separate answer, so a node that lies on two paths must be walked once for each path, and the walk keeps no visited set. One shared list path holds the nodes from source to the current node: path.append(nxt) before dfs(nxt), and path.pop() after it. When the walk reaches target, save path[:], a copy, because path keeps changing after the call returns. The graph has no cycle, so every walk ends. The trap is the visited check from Flood Fill: if nxt in seen: continue skips the second path to a shared node, so [[1, 2], [3], [3], []] returns one path instead of two.
See it run
All Paths From Source to Target, step by step
paths saved 0
Each circle is a node and each arrow is an edge. The row path is the route from node 0 to the node being visited. The row paths holds the saved copies.
nowthe node the walk is aton patha node in the shared list pathsaveda node of a path that was copied into paths2nd patha node that the walk reaches a second time, by a different path
The graph has 4 nodes. The target is node 3. path starts as [0], and paths is empty.
Gotcha 1 of 4
- The trap
Gotcha 1: Skipping a node that was already visited, as Flood Fill does
Mistakefor nxt in graph[node]: if nxt in seen: continue seen.add(nxt) path.append(nxt)Fixfor nxt in graph[node]: path.append(nxt)What happens: Flood Fill marks a cell once, because it needs each cell once. This card needs each path once, and a node can lie on several paths. In the example, node 3 is reached first by the path
[0, 1, 3]. Node 3 is then inseen, soif nxt in seen: continueskips it on the path through node 2. The path[0, 2, 3]is never found.Example: All Paths From Source to Target (LC 797): graph = [[1, 2], [3], [3], []], source = 0, target = 3Mistake: returns [[0, 1, 3]]Fix: returns [[0, 1, 3], [0, 2, 3]]
- You only need to know which nodes the walk can reach, or how many groups there are, as in Keys and Rooms (LC 841). A visited set then makes the walk touch each node once, and no path list is needed. See Flood Fill
- The directed graph can have a cycle, and you must find it, as in Course Schedule (LC 207). This card assumes that no cycle exists. See Cycle Detection
- The input is a binary tree and a path must end at a leaf, as in Path Sum II (LC 113). A tree needs no adjacency list, and each node has only a left and a right child. See Root-to-Leaf Paths
Deep Dive
Why path holds exactly the route to the current node
path starts as [0]. Before each call dfs(nxt), the code runs path.append(nxt). After the call returns, the code runs path.pop().
So when dfs(node) is called, path holds the nodes from node 0 to node. When dfs(node) returns, path is the same as before the call, because every append inside it has a matching pop.
Example: graph = [[1, 2], [3], [3], []]. The walk appends 1 and 3, saves the path, and pops 3 and 1. Then path is [0] again, and the neighbour 2 extends the same path.
Why a copy is saved, and why there is no visited set
paths.append(path[:]) stores the values of path at that moment. If the code stored path itself, every saved answer would be the same list. At the end that list is [0], so Example 1 would return [[0], [0]].
Flood Fill marks a cell as seen because it needs each cell once. This card needs each path once, and a node can lie on several paths. Node 3 lies on [0, 1, 3] and on [0, 2, 3].
With if nxt in seen: continue, the second path to node 3 is skipped, and Example 1 returns [[0, 1, 3]]. The graph has no cycle, so without a visited set every walk still ends.
One trace: node 3 is reached twice
The board runs allPathsSourceTarget on LeetCode's Example 1: graph = [[1, 2], [3], [3], []].
The walk appends 1, then 3. Node 3 is the target, so the copy [0, 1, 3] is saved. Two pops return path to [0].
The walk appends 2, then 3 again. This is the step marked with the trap tag: a visited set would skip it. Instead the copy [0, 2, 3] is saved.
The final answer is [[0, 1, 3], [0, 2, 3]], the same as LeetCode's output.
The cost, and carrying a value instead of a path
In the worst case every node has an edge to every later node. Then there are 2^(V - 2) paths, and each copy costs up to V. The time is O(2^V * V), and the extra space is O(V) for path and the recursion.
The same walk carries other results. Time Needed to Inform All Employees (LC 1376) carries the minutes so far, and takes the largest value. Employee Importance (LC 690) carries a sum. Clone Graph (LC 133) carries a map from each node to its copy, and that map must also act as a visited set, because that graph can have cycles.
60-Second Pitch
"I use a depth-first search with one shared path. The path starts with node 0. For each neighbour I append it to the path, call dfs, and pop it when the call returns, so the path always holds the route to the current node. At the last node I save a copy of the path, because the path keeps changing. I keep no visited set, because a node can lie on many paths and each path is a separate answer. The graph has no cycle, so every walk ends. The worst case has 2 to the power of n minus 2 paths, so the time is O(2^n * n) and the extra space is O(n)."
Common Questions
- Why is there no visited set, when Flood Fill needs one?
Flood Fill needs each cell once. This card needs each path once, and one node can lie on many paths. A visited set would skip the second path to a shared node. A graph with no cycle also needs no visited set to stop the walk.
- What happens if the graph has a cycle?
The walk goes around the cycle forever, and Python raises a RecursionError. Skip a node that is already in
path, or use the Cycle Detection card first.- Why
path[:]and notpath? pathis one list that keeps changing. Storing it stores the same list many times. By the end every pop has run, so all saved answers would equal[0].- How many paths can there be?
At most 2^(n - 2), when every node has an edge to every later node. With n up to 15 this is 8192 paths, so listing them all is affordable.
SWE Reasoning
Spot it
- The statement asks for all possible paths between two nodes, not a count and not a yes or no.
- The graph is directed, has no cycle, and is given as an adjacency list.
- The graph is small, because the answer can have 2^(n - 2) paths.
- If the statement asks only whether a node is reachable, a visited set is enough and this is a different card.
The invariant, step by step
path = [0],paths = [], andtarget = len(graph) - 1.dfs(node)first checksnode == target. At the target it savespath[:]and returns.- Otherwise, for each
nxtingraph[node]:path.append(nxt),dfs(nxt),path.pop(). - When
dfs(node)returns,pathis the same as before the call. dfs(0)ends, andpathsholds every path.
Traps
- A visited set.
if nxt in seen: continueloses the second path to a shared node. - Saving
pathwithout a copy. Every answer becomes the same list. - A missing
path.pop(). The second answer starts with the nodes of the first. - A graph with a cycle. The walk never ends and Python raises a RecursionError.
Practice
Builds on Flood Fill, which you haven’t finished yet.
Traverse an Adjacency List and Carry a Result (All Paths From Source to Target)
A directed graph has n nodes, numbered 0 to n - 1, and it has no cycle. A directed graph with no cycle is called a DAG. An edge goes from one node to another and can be followed in that direction only.
The graph is given as graph, an adjacency list: graph[i] lists every node that node i has an edge to. A path is a list of nodes in which each node has an edge to the next one.
Find every path that starts at node 0 and ends at node n - 1. Return all of them, in any order.
Graph Paths
adjacency list ➔ walk with one shared path ➔ copy at the target ➔ undo| 1 | from typing import List |
| 2 | |
| 3 | def all_paths(graph: List[List[int]], source: int, target: int) -> List[List[int]]: |
| 4 | """Every path from source to target in a directed graph that has no cycle, given as |
| 5 | an adjacency list. |
| 6 | Precondition: the graph has no cycle, so every walk ends. Finding a cycle is the |
| 7 | Cycle Detection card's job. |
| 8 | Time: O(2^V * V) | Space: O(V) |
| 9 | """ |
| 10 | paths: List[List[int]] = [] # Every finished path, each one a copy |
| 11 | path = [source] # The nodes from source to the node being visited |
| 12 | |
| 13 | def dfs(node: int) -> None: |
| 14 | # 1. Save A Copy At The Target: |
| 15 | # path[:] is a snapshot, because path keeps changing after this call returns. |
| 16 | if node == target: |
| 17 | paths.append(path[:]) |
| 18 | return |
| 19 | |
| 20 | # 2. Extend The Path, Walk, Then Undo: |
| 21 | # No visited set: a node on two paths must be walked once for each path. |
| 22 | for nxt in graph[node]: |
| 23 | path.append(nxt) |
| 24 | dfs(nxt) |
| 25 | path.pop() |
| 26 | |
| 27 | dfs(source) |
| 28 | return paths |
dfs(node) is called, path holds the nodes from source to node, and when dfs(node) returns, path is the same as it was before the call.Every path from source to target is a separate answer, so a node that lies on two paths must be walked once for each path, and the walk keeps no visited set. One shared list path holds the nodes from source to the current node: path.append(nxt) before dfs(nxt), and path.pop() after it. When the walk reaches target, save path[:], a copy, because path keeps changing after the call returns. The graph has no cycle, so every walk ends. The trap is the visited check from Flood Fill: if nxt in seen: continue skips the second path to a shared node, so [[1, 2], [3], [3], []] returns one path instead of two.
See it run
All Paths From Source to Target, step by step
paths saved 0
Each circle is a node and each arrow is an edge. The row path is the route from node 0 to the node being visited. The row paths holds the saved copies.
nowthe node the walk is aton patha node in the shared list pathsaveda node of a path that was copied into paths2nd patha node that the walk reaches a second time, by a different path
The graph has 4 nodes. The target is node 3. path starts as [0], and paths is empty.
Gotcha 1 of 4
- The trap
Gotcha 1: Skipping a node that was already visited, as Flood Fill does
Mistakefor nxt in graph[node]: if nxt in seen: continue seen.add(nxt) path.append(nxt)Fixfor nxt in graph[node]: path.append(nxt)What happens: Flood Fill marks a cell once, because it needs each cell once. This card needs each path once, and a node can lie on several paths. In the example, node 3 is reached first by the path
[0, 1, 3]. Node 3 is then inseen, soif nxt in seen: continueskips it on the path through node 2. The path[0, 2, 3]is never found.Example: All Paths From Source to Target (LC 797): graph = [[1, 2], [3], [3], []], source = 0, target = 3Mistake: returns [[0, 1, 3]]Fix: returns [[0, 1, 3], [0, 2, 3]]
- You only need to know which nodes the walk can reach, or how many groups there are, as in Keys and Rooms (LC 841). A visited set then makes the walk touch each node once, and no path list is needed. See Flood Fill
- The directed graph can have a cycle, and you must find it, as in Course Schedule (LC 207). This card assumes that no cycle exists. See Cycle Detection
- The input is a binary tree and a path must end at a leaf, as in Path Sum II (LC 113). A tree needs no adjacency list, and each node has only a left and a right child. See Root-to-Leaf Paths
Deep Dive
Why path holds exactly the route to the current node
path starts as [0]. Before each call dfs(nxt), the code runs path.append(nxt). After the call returns, the code runs path.pop().
So when dfs(node) is called, path holds the nodes from node 0 to node. When dfs(node) returns, path is the same as before the call, because every append inside it has a matching pop.
Example: graph = [[1, 2], [3], [3], []]. The walk appends 1 and 3, saves the path, and pops 3 and 1. Then path is [0] again, and the neighbour 2 extends the same path.
Why a copy is saved, and why there is no visited set
paths.append(path[:]) stores the values of path at that moment. If the code stored path itself, every saved answer would be the same list. At the end that list is [0], so Example 1 would return [[0], [0]].
Flood Fill marks a cell as seen because it needs each cell once. This card needs each path once, and a node can lie on several paths. Node 3 lies on [0, 1, 3] and on [0, 2, 3].
With if nxt in seen: continue, the second path to node 3 is skipped, and Example 1 returns [[0, 1, 3]]. The graph has no cycle, so without a visited set every walk still ends.
One trace: node 3 is reached twice
The board runs allPathsSourceTarget on LeetCode's Example 1: graph = [[1, 2], [3], [3], []].
The walk appends 1, then 3. Node 3 is the target, so the copy [0, 1, 3] is saved. Two pops return path to [0].
The walk appends 2, then 3 again. This is the step marked with the trap tag: a visited set would skip it. Instead the copy [0, 2, 3] is saved.
The final answer is [[0, 1, 3], [0, 2, 3]], the same as LeetCode's output.
The cost, and carrying a value instead of a path
In the worst case every node has an edge to every later node. Then there are 2^(V - 2) paths, and each copy costs up to V. The time is O(2^V * V), and the extra space is O(V) for path and the recursion.
The same walk carries other results. Time Needed to Inform All Employees (LC 1376) carries the minutes so far, and takes the largest value. Employee Importance (LC 690) carries a sum. Clone Graph (LC 133) carries a map from each node to its copy, and that map must also act as a visited set, because that graph can have cycles.
60-Second Pitch
"I use a depth-first search with one shared path. The path starts with node 0. For each neighbour I append it to the path, call dfs, and pop it when the call returns, so the path always holds the route to the current node. At the last node I save a copy of the path, because the path keeps changing. I keep no visited set, because a node can lie on many paths and each path is a separate answer. The graph has no cycle, so every walk ends. The worst case has 2 to the power of n minus 2 paths, so the time is O(2^n * n) and the extra space is O(n)."
Common Questions
- Why is there no visited set, when Flood Fill needs one?
Flood Fill needs each cell once. This card needs each path once, and one node can lie on many paths. A visited set would skip the second path to a shared node. A graph with no cycle also needs no visited set to stop the walk.
- What happens if the graph has a cycle?
The walk goes around the cycle forever, and Python raises a RecursionError. Skip a node that is already in
path, or use the Cycle Detection card first.- Why
path[:]and notpath? pathis one list that keeps changing. Storing it stores the same list many times. By the end every pop has run, so all saved answers would equal[0].- How many paths can there be?
At most 2^(n - 2), when every node has an edge to every later node. With n up to 15 this is 8192 paths, so listing them all is affordable.
SWE Reasoning
Spot it
- The statement asks for all possible paths between two nodes, not a count and not a yes or no.
- The graph is directed, has no cycle, and is given as an adjacency list.
- The graph is small, because the answer can have 2^(n - 2) paths.
- If the statement asks only whether a node is reachable, a visited set is enough and this is a different card.
The invariant, step by step
path = [0],paths = [], andtarget = len(graph) - 1.dfs(node)first checksnode == target. At the target it savespath[:]and returns.- Otherwise, for each
nxtingraph[node]:path.append(nxt),dfs(nxt),path.pop(). - When
dfs(node)returns,pathis the same as before the call. dfs(0)ends, andpathsholds every path.
Traps
- A visited set.
if nxt in seen: continueloses the second path to a shared node. - Saving
pathwithout a copy. Every answer becomes the same list. - A missing
path.pop(). The second answer starts with the nodes of the first. - A graph with a cycle. The walk never ends and Python raises a RecursionError.