DFS is analogous to searching a maze in that it dives as deep into the graph as
possible and only back tracks when absolutely necessary. It is identical to BFS
with two exceptions. First, it uses a Stack instead of a
Queue. Second, items are conquered after being `pop`

ed from the stack instead
of before they are `enqueue`

ed.

## Applications

- Connectivity - In a network, ensure that every node is reachable.

## Asymptotic Complexity

\(O(m + n)\)

## Pseudo Code

```
G = input graph
s = stack data structure
v = starting vertex
side effects: marks all vertices conquered that are reachable from v
s->push(v)
while s is not empty:
v = s->pop
if v is NOT conquered:
conquer(v)
for each edge in v:
w = edge->head
s->push(w)
```

DFS also lends itself to a rather elegant recursive implementation that does not require any additional data structures.

```
G = input graph
v = starting vertex
side effects: marks all vertices conquered that are reachable from v
conquer(v)
for each edge in v:
w = edge->head
if w is NOT conquered:
recurse (G, w)
```

## Source Code

Relevant Files:

Click here for build and run instructions