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
- Connectivity - In a network, ensure that every node is reachable.
\(O(m + n)\)
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)
Click here for build and run instructions