Depth-First Search (DFS)

Where BFS spreads outward in concentric layers, DFS dives down one path until it cannot go further, then backtracks to try other options. It is the natural way to explore a graph if you think of it as a maze: at every junction, pick an unexplored door and walk through; if you hit a dead end, walk back and pick the next door.

DFS is most naturally written recursively — each call handles one vertex and recurses on each unvisited neighbor. The call stack itself plays the role of the stack of vertices we have entered but not yet finished.

It has two essential timestamps per vertex:

• disc[u] — the time we enter u (discovery time).
• fin[u] — the time we leave u (finish time, after recursing on all its neighbors).

The intervals [disc[u], fin[u]] of any two vertices either nest (one is contained in the other) or are disjoint — they never partially overlap. This parenthesis structure is the secret behind many DFS-based algorithms.

During DFS, every edge (u, v) falls into one of four categories, based on the colors of u and v at the moment we look at the edge:

• Tree edge — v is white (unvisited). Take the edge and recurse — (u, v) becomes part of the DFS tree.
• Back edge — v is gray (in progress, an ancestor of u). This signals a cycle.
• Forward edge — v is black and a descendant of u. Possible only in directed graphs.
• Cross edge — v is black and not a descendant of u. Possible only in directed graphs.

Colors at a glance:

In an undirected graph, every non-tree edge is a back edge — there are no forward or cross edges. That single fact is why undirected cycle detection is a one-line check: "during DFS, did we ever see an edge to a gray, non-parent vertex?"

Run DFS from vertex 1 on this undirected graph; neighbors are visited in numerical order. Step forward and backward with the ← / → arrow keys or the buttons below.

Watch the white/gray/black coloring in action:

• Gray (amber) vertices are on the recursion stack — entered but not yet finished. The stack panel shows exactly the current chain of recursive calls.
• Black (green) vertices are finished — their recursive call has returned.
• Each vertex's disc/fin label fills in as the timer t ticks: once on entry, once on exit.
• Green edges are tree edges; the dashed amber edge is the one currently being examined. Edges leading to a gray, non-parent vertex are back edges — proof of a cycle.

Final intervals after the run completes:

Intervals nest cleanly — the children of u in the DFS tree are exactly the vertices whose intervals lie inside [disc[u], fin[u]]. The DFS tree produced here is:

Recursion is the natural way to write DFS, but it costs stack memory — roughly one frame per active vertex. For graphs with V ≈ 10⁶ you may overflow the call stack. The cure is an explicit stack:

The trick is to remember where you were in each vertex's neighbor list — push (u, iterator) pairs instead of just u, so when you return to u you continue scanning rather than starting over.

In contest C++ this is usually unnecessary unless V exceeds ~10⁵; for everything smaller, the recursive version is clearer and just as fast.

DFS is the workhorse of graph algorithms. Once you have it, many problems become short programs:

• Cycle detection — undirected: any non-parent back edge; directed: any back edge (gray-to-gray).
• Topological sort of a DAG — order vertices by decreasing finish time.
• Connected components in undirected graphs.
• Strongly connected components (Tarjan's, Kosaraju's) — both run DFS twice and read off intervals or low-link values.
• Bridge and articulation point finding (Tarjan's algorithm).
• Backtracking and search — N-Queens, maze solving, Sudoku — all DFS over an implicit graph of states.

The recursive DFS with colors and timestamps — exactly what the visualization animates. DFS-VISIT(u) colors u gray on entry, recurses into every white neighbor, and colors u black on exit. The C++ tab runs it on the visualization's graph and also includes the iterative explicit-stack variant for very deep graphs.

Every vertex is entered at most once (marked at first visit). For each entered vertex u, we iterate through its adjacency list once — total work O(deg(u)).

Summing: O(V) + O(Σ deg(v)). The degree sum equals 2E (undirected) or E (directed), so total time is O(V + E) with an adjacency list.

• Time: O(V + E) with an adjacency list; O(V²) with a matrix.
• Space: O(V) for the color/disc/fin arrays, plus O(depth) for the call stack — worst case O(V) on a path-shaped graph.