Depth First Search (DFS)

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 poped from the stack instead of before they are enqueueed.

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

Full Repo

Relevant Files:

Click here for build and run instructions