Discrete Mathsfor Engineers

3. The Algorithm

In this part, we formalize Depth-First Search using the classical presentation from Introduction to Algorithms (CLRS).

DFS is not just an intuition about “going deep”. It is a precise graph traversal procedure with well-defined state, recursion structure, and timestamps.

3.1 State Maintained by DFS

For each vertex u ∈ V, DFS stores:

• color[u] — exploration state
• π[u] — predecessor (parent) in the DFS tree
• d[u] — discovery time
• f[u] — finish time

These values allow DFS to do much more than just traverse the graph. They encode structural information that will be essential later for edge classification, cycle detection, and topological sorting.

3.2 The Meaning of Colors

3.3 Main Procedure — DFS

The global DFS procedure initializes all vertices and then scans the graph. If it finds a WHITE vertex, it starts a new DFS tree rooted at that vertex.

DFS(G):

    for each vertex u in V[G]:
        color[u] = WHITE
        π[u] = NIL

    time = 0

    for each vertex u in V[G]:
        if color[u] == WHITE:
            DFS-VISIT(G, u)

3.4 Recursive Procedure — DFS-VISIT

The real exploration happens inside the recursive subroutine:

DFS-VISIT(G, u):

    time = time + 1
    d[u] = time
    color[u] = GRAY

    for each v in Adj[u]:
        if color[v] == WHITE:
            π[v] = u
            DFS-VISIT(G, v)

    color[u] = BLACK
    time = time + 1
    f[u] = time

This procedure captures the full deep-exploration logic: discover a vertex, recursively visit unvisited neighbors, and only then finish the current vertex.

3.5 Discovery and Finish Times

DFS assigns two timestamps to every vertex:

• d[u] — when u is first discovered
• f[u] — when the exploration of u is complete

These timestamps are one of the most important features of DFS. They turn a traversal into a structural analysis tool.

3.6 Parent Pointers and DFS Trees

Whenever DFS discovers a WHITE vertex v from a vertex u, it sets:

These parent pointers define the DFS tree rooted at the vertex that started the exploration.

If the graph has multiple disconnected regions, DFS builds a collection of trees, called a DFS forest.

3.7 Why DFS May Produce a Forest

DFS starts a new recursive exploration every time it encounters a vertex that is still WHITE in the outer loop.

Therefore:

• If the graph is fully reachable from a single source, DFS produces one tree.
• If the graph has multiple disconnected components, DFS produces multiple trees.