Depth-first search (DFS) explores one branch of a graph as far as possible before returning to earlier branching points.

The traversal can be implemented recursively or with an explicit stack. Each vertex is marked when first visited so cycles do not cause repeated exploration.

With adjacency lists, DFS runs in

$$O(|V|+|E|)$$

time.

The traversal produces a depth-first forest and exposes structural information through discovery and return order. These orderings support later algorithms for cycle detection, topological ordering and graph decomposition.

BFS and DFS visit the same reachable vertices but impose different exploration orders. Their usefulness comes from the properties created by those orders, not merely from reaching every vertex.