2
$\begingroup$

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 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]).

Here is a solution which uses DFS and maintains the current path in the graph with a stack stk.

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?

$\endgroup$
1
  • $\begingroup$ If I am understanding it correctly, fo you want an implementation just using an explicit stack, without recursion? $\endgroup$ Aug 28, 2021 at 18:11

1 Answer 1

2
$\begingroup$

Does this pseudocode help? Let me know of any clarifications.

stack_0.push(0) // stack containing only vertex 0
stack_of_stacks = empty
stack_of_stacks.push((stack_0, vertex 0)) // added a tuple of stack and vertex 0

while stack_of_stacks is not empty:

      (temp_stack, temp_vertex) = stack_of_stacks.pop()
      
      if temp_vertex = n-1
            print temp_stack
      else, for every y in graph[temp_vertex]
            new_stack = temp_stack
            new_stack.push(y)
            new_vertex = y
            stack_of_stacks.push((new_stack, new_vertex))
end
$\endgroup$
3
  • $\begingroup$ I assume new_stack = temp_stack makes a copy of temp_stack? While that's a valid solution (+1), using a "stack of stacks" not only blows time complexity up, but also makes space complexity quadratic. Perhaps there is an iterative version of the algorithm that consumes approximately the same resource as the recursive version? $\endgroup$
    – nalzok
    Aug 30, 2021 at 15:16
  • $\begingroup$ @nalzok I do not understand how the space complexity is quadratic. In fact, both the space complexity and the time complexity are exponential in $n$, since the number of paths can be exponential. Moreover, since you have to print all the paths, it is not possible to obtain better than exponential time complexity. $\endgroup$ Aug 30, 2021 at 16:52
  • 1
    $\begingroup$ Regarding the space complexity, I didn't count the output space. See this question for more details (it's more of a definition issue :). $\endgroup$
    – nalzok
    Aug 30, 2021 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.