Offensive Security Researcher & Quantum Cryptography Analyst

Depth-First Search (DFS) Algorithm: Comprehensive Explanation and Implementation in C

Abdul Wahab Junaid
Depth-First Search (DFS) - Comprehensive Explanation and Implementation in C

Depth-First Search is the other half of the classic traversal pair alongside BFS, and honestly it’s the one I reach for more often in practice. Instead of expanding outward in layers, DFS commits to a path and follows it as deep as possible before backtracking. That “go deep first, backtrack when stuck” behavior makes it a natural fit for problems involving structure discovery — cycle detection, topological ordering, connectivity, and pathfinding in mazes where I don’t care about shortest distance but do care about exploring exhaustively.

History and Background

DFS has roots that go back further than most people expect. It was formalized as a maze-traversal strategy in the 19th century by mathematician Charles Pierre Trémaux, whose method for solving mazes without getting lost is essentially DFS with backtracking. In computer science, DFS was popularized and rigorously analyzed by Robert Tarjan in the early 1970s, whose work applying DFS to problems like strongly connected components and biconnectivity turned it from a simple traversal trick into one of the most powerful tools in graph algorithm design. It’s now a cornerstone of algorithms education and appears in essentially every algorithms textbook, most notably CLRS.

Problem Statement

Given a graph G = (V, E) and a starting vertex (or the need to cover all vertices even in a disconnected graph), the goal is to visit every reachable vertex exactly once, in a way that fully explores each branch before backtracking, and to record useful structural information along the way such as discovery/finish times, parent relationships, and edge classifications.

Core Concepts

How It Works

  1. Pick a starting vertex, mark it visited, and record its discovery time.
  2. Look at its neighbors one at a time. For the first unvisited neighbor, recurse into it (go deeper).
  3. Continue this recursive descent until reaching a vertex with no unvisited neighbors.
  4. Backtrack to the previous vertex, record its finish time, and try its next unvisited neighbor.
  5. Repeat until every vertex reachable from the start has been visited; if the graph is disconnected, restart the process from any remaining unvisited vertex.

Working Principle

DFS relies on a Last-In-First-Out (LIFO) structure — either the actual call stack through recursion, or an explicit stack if implemented iteratively. This is what produces the “dive deep, then backtrack” behavior: the most recently discovered vertex is always the next one explored. This ordering is precisely what makes DFS so good at revealing structural properties like cycles (a back edge appears exactly when I encounter a vertex that’s still on the current stack) and hierarchical relationships (the parenthesis structure of discovery/finish times mirrors nested scopes).

Mathematical Foundation

The parenthesis theorem is the core mathematical result behind DFS: for any two vertices u and v, exactly one of the following holds:

$$[d[u], f[u]] \text{ and } [d[v], f[v]] \text{ are entirely disjoint}$$

$$[d[u], f[u]] \text{ is nested entirely within } [d[v], f[v]] \text{ (v is an ancestor of u)}$$

$$[d[v], f[v]] \text{ is nested entirely within } [d[u], f[u]] \text{ (u is an ancestor of v)}$$

where d[x] and f[x] denote the discovery and finish times of vertex x. This nesting property is what enables correct classification of edges and underlies algorithms like topological sort and SCC detection. The running time is:

$$T(V, E) = O(V + E)$$

since each vertex is visited once and each edge examined once (or twice in an undirected graph).

Diagrams

flowchart TD
    A[Start DFS at vertex u] --> B[Mark u visited, record discovery time]
    B --> C{Unvisited neighbor v exists?}
    C -- Yes --> D[Recurse into v]
    D --> C
    C -- No --> E[Record finish time for u, backtrack]
    E --> F{More vertices unvisited in graph?}
    F -- Yes --> A
    F -- No --> G[Done]

Pseudocode

DFS(G):
    for each vertex u in G.V:
        visited[u] = false
        parent[u] = NIL
    time = 0
    for each vertex u in G.V:
        if visited[u] == false:
            DFS-VISIT(G, u)

DFS-VISIT(G, u):
    time = time + 1
    discovery[u] = time
    visited[u] = true
    for each v in G.adj[u]:
        if visited[v] == false:
            parent[v] = u
            DFS-VISIT(G, v)
    time = time + 1
    finish[u] = time

Step-by-Step Example

Using this directed graph:

1 -> 2
1 -> 3
2 -> 4
3 -> 4
4 -> 5

Starting DFS from vertex 1:

  1. Visit 1 (discovery time 1).
  2. From 1, go to 2 (discovery time 2).
  3. From 2, go to 4 (discovery time 3).
  4. From 4, go to 5 (discovery time 4). 5 has no unvisited neighbors, finish time 5.
  5. Backtrack to 4. No more unvisited neighbors, finish time 6.
  6. Backtrack to 2. No more unvisited neighbors, finish time 7.
  7. Backtrack to 1. Try neighbor 3 (discovery time 8). Its neighbor 4 is already visited, so finish time 9 for vertex 3.
  8. Backtrack to 1. No more neighbors, finish time 10.

Final traversal order: 1, 2, 4, 5, 3.

Time Complexity

Space Complexity

Correctness Analysis

DFS’s correctness follows from a simple inductive argument: DFS-VISIT is only called on unvisited vertices, and it’s marked visited immediately upon entry, which prevents infinite loops even in cyclic graphs. Because the outer loop tries every vertex as a starting point if it hasn’t been visited yet, every vertex in the graph — even in disconnected components — is guaranteed to be visited exactly once. The parenthesis theorem, provable by induction on discovery/finish time ordering, guarantees the well-formed nesting property that many derivative algorithms (like SCC and topological sort) depend on.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct {
    int adj[MAX_VERTICES][MAX_VERTICES];
    int numVertices;
} Graph;

int visited[MAX_VERTICES];
int discoveryTime[MAX_VERTICES];
int finishTime[MAX_VERTICES];
int timer = 0;

void initGraph(Graph *g, int n) {
    g->numVertices = n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g->adj[i][j] = 0;
}

void addEdge(Graph *g, int u, int v) {
    g->adj[u][v] = 1; /* directed edge; add g->adj[v][u]=1 for undirected */
}

void dfsVisit(Graph *g, int u) {
    visited[u] = 1;
    discoveryTime[u] = ++timer;
    printf("Visiting: %d (time %d)\n", u, discoveryTime[u]);

    for (int v = 0; v < g->numVertices; v++) {
        if (g->adj[u][v] == 1 && !visited[v]) {
            dfsVisit(g, v);
        }
    }

    finishTime[u] = ++timer;
    printf("Finished: %d (time %d)\n", u, finishTime[u]);
}

void dfs(Graph *g) {
    for (int i = 0; i < g->numVertices; i++) {
        visited[i] = 0;
    }
    timer = 0;

    for (int u = 0; u < g->numVertices; u++) {
        if (!visited[u]) {
            dfsVisit(g, u);
        }
    }
}

int main(void) {
    Graph g;
    initGraph(&g, 5);

    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 4);

    dfs(&g);

    return 0;
}

Sample Input and Output

Input: Directed graph with edges (0,1), (0,2), (1,3), (2,3), (3,4).

Output:

Visiting: 0 (time 1)
Visiting: 1 (time 2)
Visiting: 3 (time 3)
Visiting: 4 (time 4)
Finished: 4 (time 5)
Finished: 3 (time 6)
Finished: 1 (time 7)
Visiting: 2 (time 8)
Finished: 2 (time 9)
Finished: 0 (time 10)

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version