Depth-First Search and Edge Types

From rings to a deep dive

The previous guide gave you breadth-first search, which fans out from the source in widening rings: all vertices one edge away, then all two edges away, and so on. Depth-first search flips that temperament completely. Instead of patiently exploring everything nearby, DFS commits to a single neighbor and plunges as deep as it can, following one edge after another into the unknown until it reaches a vertex with no unvisited neighbors. Only then does it back up one step and try the next option. BFS is a cautious surveyor; DFS is an explorer who walks straight into the cave until the tunnel ends.

Mechanically the only change from BFS is the data structure that holds 'where to go next'. BFS uses a queue (first in, first out), so the oldest-discovered frontier vertex is explored next, producing rings. DFS uses a stack (last in, first out) — most naturally the call stack of recursion — so the newest-discovered vertex is explored next, producing a dive. Swap a queue for a stack and the whole personality of the search inverts. Everything else, the adjacency-list scan of neighbors and the 'visited' marks that stop you revisiting, stays exactly the same.

DFS(u):
  color[u] = gray;  time = time+1;  disc[u] = time   # entering u
  for each neighbor v of u:
    if color[v] == white:        # v never seen -> tree edge
      parent[v] = u
      DFS(v)
  color[u] = black; time = time+1;  fin[u] = time     # leaving u

Recursive DFS with discovery/finish timestamps. White = undiscovered, gray = on the current path (in progress), black = fully done. The disc and fin numbers are the key to everything below.

The DFS tree and the parenthesis idea

Just as BFS records a parent for each vertex and builds a BFS tree, DFS records a parent every time it steps into a fresh vertex, building a DFS tree (a forest, if the graph is disconnected and you restart the search from each unvisited vertex). But the DFS tree tends to be tall and stringy — long descending paths — where the BFS tree was short and bushy. That shape is the whole point: it captures the order in which the search dived and surfaced, and that order is recorded by two timestamps per vertex, its discovery time (when DFS first colors it gray) and its finish time (when DFS colors it black and returns).

These timestamps obey a beautiful, rigid rule called the parenthesis structure. Picture writing an opening bracket '(u' when DFS discovers u and a closing 'u)' when it finishes u. Because DFS fully finishes a vertex before returning to its parent, these brackets always nest perfectly — like '( ( ) ( ) )' — never crossing like '( [ ) ]'. Concretely: for any two vertices u and v, their discovery–finish intervals are either completely disjoint, or one is entirely nested inside the other. And the nesting is not a coincidence — interval of v sits inside interval of u exactly when v is a descendant of u in the DFS tree.

Four kinds of edge

Here is where DFS earns its keep. As the search runs, every edge it examines falls into exactly one of four categories, and the category is decided purely by the color of the far endpoint at the moment you look at it. This sorting is called edge classification, and learning to read it turns DFS from a way of visiting a graph into a way of understanding its structure. A tree edge is one DFS uses to discover a brand-new vertex — the far endpoint is white. These are exactly the edges of the DFS tree, and there are at most n-1 of them per tree.

The other three are the 'leftover' (non-tree) edges, distinguished by where the far endpoint sits relative to you. A back edge points to a gray vertex — an ancestor still open on your current path; you have just looped back onto your own trail. A forward edge points to a black vertex that is a descendant you already finished (you reach it again by a shortcut). A cross edge points to a black vertex that is neither ancestor nor descendant — a different subtree, or an earlier-finished part of the same one. The reliable test uses the timestamps: comparing disc and fin of the two endpoints tells you which case you are in without ever drawing the tree.

Why back edges mean cycles

The single most important payoff of edge classification is this clean theorem: a directed graph has a cycle if and only if DFS finds a back edge. That 'if and only if' is what makes it an algorithm rather than a hopeful heuristic, so let us see why both directions hold — this is cycle detection, and it runs in the same O(n + m) time as the search itself, where m is the number of edges.

Easy direction — a back edge forces a cycle. A back edge (u, v) points from u to an ancestor v that is still gray, meaning v is open on the current path. So the DFS tree already holds a path of tree edges from v down to u; add the back edge u to v and that path closes into a cycle. No back edge can be innocent.
Hard direction — every cycle creates a back edge. Suppose the graph has a cycle. Among its vertices, let w be the first one DFS discovers. While w is still gray, DFS will (directly or through descendants) explore the cycle and eventually examine the edge entering w from the previous vertex on the cycle. At that moment w is still an open ancestor — gray — so that edge is classified as a back edge.
So 'cycle exists' and 'a back edge appears' are logically equivalent. To turn this into code you do not even need full timestamps: keep a gray set (the vertices currently on the recursion stack) and report a cycle the instant you scan an edge whose far end is gray. That is the whole detector.

A frequent trap to flag here: in an undirected graph the test is almost the same but you must ignore the immediate parent. Because an undirected edge is scanned from both ends, the edge you just used to enter a vertex would otherwise look like a back edge to its own parent and falsely shout 'cycle'. Skip that one edge and the rule 'a back edge means a cycle' holds again — and undirected DFS is tidier still, since only tree and back edges occur, never forward or cross edges.

What the edge types unlock

Reading edges is not an end in itself; it is a master key. The absence of any back edge in a directed graph means no cycles, i.e. the graph is a DAG — and the next guide shows that listing vertices by decreasing finish time then yields a valid topological order, because a vertex always finishes after all the vertices reachable from it. Cross and tree edges, read together, also let a single DFS sweep label every connected component of an undirected graph: each restart of the search from a fresh white vertex begins a new component.

The deeper structural results in this rung run on the very same fuel. Strongly connected components are found by two DFS passes whose correctness is a parenthesis-structure argument about finish times. Articulation points and bridges are found in a single DFS by tracking, for each vertex, the earliest ancestor any back edge can climb to — again, a question purely about back edges. The recurring lesson, the one to carry up the ladder: DFS does not just reach every vertex like a tank of fuel — its discovery and finish times encode the graph's nesting structure, and almost every fast graph algorithm is a way of reading that encoding.

One honest note on cost and limits to close on. DFS, like BFS, runs in O(n + m) time and uses O(n) extra space for colors, timestamps, and the recursion stack — which is also its main practical caveat: on a graph with a path of a million vertices, the recursion can blow the call stack, so deep DFS is often rewritten with an explicit stack. And remember that DFS answers reachability and structure, not distance: unlike BFS it does not give shortest paths in edge count, because it dives down one long route before ever considering a shorter parallel one. Pick the search to match the question.