[Design] Implemention of DFS using a Stack

First Word

This post talks about how to implement DFS without recursion.

We have studied 2 kinds of DFS in the post DFS, BFS and space efficiency. We will skip “true DFS” here, and only talk about “pseudo-DFS” implementation.

Remember, space usage of psudo-DFS is O(depth x branching factor).

Analysis

A DFS without recursion is basically the same as BFS - but use a stack instead of a queue as the data structure.

More details are discussed in this thread.

Implementation

The following code come from this post.

DFS(source):
  s <- new stack
  visited <- {} //empty set
  s.push(source)
  while (s.empty() == false):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    //do something with current
    for each node v such that (source,v) is an edge:
        s.push(v)