Depth First Search

Depth First Search

Depth first search, or DFS, explores a graph by going as deep as possible along one branch before backing up to try another. It is the workhorse behind cycle detection, connectivity checks, and topological ordering.

Stack or recursion

DFS naturally uses a stack, often the call stack through recursion. From the current node, pick an unvisited neighbor, descend into it, and repeat. When a node has no unvisited neighbors, backtrack to the previous node and continue.

Marking nodes visited prevents revisiting and protects against infinite loops in graphs with cycles.

What it reveals

The order in which DFS enters and leaves nodes carries information. Recording finish times supports topological sort, while detecting a node still on the current path reveals a cycle. DFS also identifies connected components by launching a fresh search from each unvisited node.

Like BFS, DFS touches every node and edge once, so its cost scales with the graph size.

Key idea

DFS plunges down one path until stuck, then backtracks, making it the basis for cycles, components, and ordering.