It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem:
Given a directed acyclic graph (DAG) of n nodes labeled from
n - 1, find all possible paths from node
n - 1and 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
Here is a solution which uses DFS and maintains the current path in the graph with a stack
def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]: ans = list() stk = list() def dfs(x: int): if x == len(graph) - 1: ans.append(stk[:]) # stk[:] returns a copy of stk return for y in graph[x]: stk.append(y) dfs(y) stk.pop() stk.append(0) dfs(0) return ans
If recursion and stacks are equivalent, then there must exist an iterative solution that uses two stacks, one to implement DFS and another to maintain the current path (same purpose as
stk). However, I'm struggling to come up with one. The trick park is maintaining
stk. When using recursion,
stk is simply the call stack, but that's no longer true with an explicit stack, because nodes from different branches may co-exist in it.
Question: how to write an iterative version of the DFS solution presented above?