### 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)
```