4
$\begingroup$

I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case.

I was wondering if there is an iterative implementation of DFS that requires an $O(n)$ size stack instead of heavy $O(n+m)$ stack. I know that this is a worst case analysis, but I am concerned with this and want this to be really bounded.

Just as a reference, I am copying the algorithm from this solution, where vertices can be pushed into stack more than once and in the worst case, the stack size can be $O(n+m)$:

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)
$\endgroup$
2
  • $\begingroup$ Only keeping the topmost copy should work, no? $\endgroup$
    – adrianN
    Aug 4 '16 at 13:46
  • $\begingroup$ @adrianN That's right, and to be honest, I already knew the answer. But I wanted this question to be here, just for people to be aware of this difference. $\endgroup$
    – orezvani
    Aug 4 '16 at 23:50
3
$\begingroup$

You can keep only the topmost copy of a node on the stack:

dfs(source):
   s <- empty stack
   visited <- {}
   on_stack <- map<node,stack element>
   s.push(source)
   on_stack.add(source,s.top())
   while s is not empty:
      current = s.pop()
      on_stack.remove(current)
      if visited.contains(current):
         continue
      # handle current
      visited.add(current)
      for v a neighbor of current:
         if on_stack.contains(v):
            stack_element <- on_stack.get(v)
            unlink stack_element from s
         stack.push(v)
         on_stack.add(v,s.top())

If your stack is a linked list, the asymptotic runtime stays the same. I doubt however that it will be much faster in practice unless your graphs are very dense, because the constants involved are much bigger.

$\endgroup$
3
  • $\begingroup$ You could store references from the nodes to their entries in the stack to remove them more efficiently. $\endgroup$
    – Raphael
    Aug 5 '16 at 7:56
  • $\begingroup$ I do. I'll edit my answer to make it clearer. $\endgroup$
    – adrianN
    Aug 5 '16 at 7:59
  • $\begingroup$ Depends what you call a stack? To me it is a linear data structure that only accesses the topmost element. $\endgroup$ Aug 5 '16 at 22:31
2
$\begingroup$

You can have a look on DFS-B in http://web.cs.unlv.edu/larmore/Courses/CSC477/bfsDfs.pdf

DFS-A can have multiple copies on the stack at the same time. However, the total number of iterations of the innermost loop of DFS-A cannot exceed the number of edges of G, and thus the size of S cannot exceed m. The running time of DFS-A is O(n + m). It is possible to write a DFS algorithm where no vertex is ever in the stack in more than one place, but it is somewhat trickier. We give such an algorithm, DFS-B, below.

DFS-B(G,s)
    for all v in V[G] do
        visited[v] := false
    end for

    S := EmptyStack
    visited[s] := true
    Push(S,s)

    while not Empty(S) do
        u := Pop(S)

        if there is at least one unvisited vertex in Adj[u] then
            Pick w to be any unvisited vertex in Adj[u]
            Push(S,u)
            visited[w] := true
            Push(S,w)
        end if
    end while
$\endgroup$
0
1
$\begingroup$

I think an even better approach is the solution on C# which I developed for similar problem - https://github.com/kostadinmarinov/scc

dfs(verticies, getNeighbours):
    visited <- {}

    return recursiveSelect(
        filter(verticies, (vertex): visited does not contain vertex),
        (vertex): dfsNext(vertex, visited, getNeighbours))

dfsNext(vertex, visited, getNeighbours):
    visited.add(vertex)

    for each neighbour in getNeighbours(vertex) do
        if visited does not contain neighbour then
            yield neighbour
        end if
    end for

filter(source, predicade):
    for each element in source do
        if predicade(element) then
            yield element
        end if
    end for

recursiveSelect(source, childSelector):
    stack := empty stack
    enumerator := source.getEnumerator()

    while enumerator has next OR stack is not empty do
        if enumerator has next then
            element := enumerator.current
            yield element

            stack.push(enumerator)
            enumerator := childSelector(element).getEnumerator()
        end if
        else if (stack is not empty) then
            enumerator := stack.pop()
        end if
    end while

The last method is taken from https://stackoverflow.com/a/30441479/7995961

Here the stack frame is automatically generated by the iterator's state machine which we just push in our stack. This implemented with that extension method is just a perfect generic transformer of recursive algorithms to iterative ones without changing the design of the algorithm.

PS: The above is a generic solution for any recursive algo. Here is a simplified version of the same workflow as the generic one for the specific case of DFS algo:

dfs(verticies, neighbours):
    stack := empty stack
    visited <- []

    for each entryVertex in verticies do
        if not visited[entryVertex] then
            stack.push([entryVertex, -1])

            while stack is not empty do (
                [vertex, i] := stack.pop();

                if i = -1 then
                    visited[vertex] := true
                    i := 0
                end if
            end while

            while i < neighbours[vertex].length do
                if not visited[neighbours[vertex][i]] then
                    stack.push([vertex, i])
                    stack.push([neighbours[vertex][i], -1])
                    break;
                end if

                i := i + 1
            end while
        end if
    end for

As you see in the stack we need to keep the state of iteration also - it could be either an enumerator object or the index of a list. This is also combined with immediate interruption of the execution for the current vertex and going into the last found not visited neighbour. The state of iteration (list index) defines also 2 more states - before the loop (i = -1) and after the loop (i = n). It's very helpful in case of steps before and visiting the neighbours.

$\endgroup$
2
  • $\begingroup$ This is not a programming site. Please replace your code with pseudocode. $\endgroup$ Sep 12 '19 at 15:08
  • $\begingroup$ I hope the reworked version is fitting the pseudocode. I was not sure about things like "yield", but it's a common feature in many programming languages and means "terminate the current execution with remembering the stack and next instruction and return value". $\endgroup$ Sep 13 '19 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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