Offensive Security Researcher & Quantum Cryptography Analyst

Depth-First Search (DFS) Algorithm: Working, Explanation, and Graph Traversal

Abdul Wahab Junaid
Depth first search algorithm and working of this algorithm

Depth first search algorithm and working of this algorithm

I think of depth-first search as the algorithm that explores a graph the way I might navigate a maze by always choosing to go as deep as possible down one path before backtracking. Instead of exploring outward in layers like breadth-first search, DFS commits to a single path, following it as far as it can go, and only turns back when it hits a dead end. This exploration strategy makes DFS the natural fit for problems involving backtracking, cycle detection, topological ordering, and exploring all possible configurations of a search space — it is one of the two traversal strategies I reach for constantly when working with graphs and trees.

History and Background

Depth-first search has roots stretching back to 19th-century maze-solving techniques, most notably formalized by French mathematician Charles Pierre Trémaux, whose maze-traversal algorithm from the 1880s is considered one of the earliest documented depth-first strategies. In computer science, DFS was rigorously formalized and analyzed as a fundamental graph algorithm during the 1970s, most influentially by Robert Tarjan, whose work using DFS to compute strongly connected components (in 1972) and other structural graph properties demonstrated just how powerful the technique could be beyond simple traversal. DFS’s connection to backtracking search also made it foundational to early artificial intelligence and constraint-satisfaction research.

Problem Statement

I need a systematic way to explore every reachable node in a graph or tree, particularly in situations where I need to explore paths fully before considering alternatives — such as detecting cycles, finding connected components, performing topological sorts, or solving problems like maze generation and puzzle solving that require deep, path-committed exploration rather than broad, layer-by-layer exploration.

Core Concepts

How It Works

I carry out DFS through these steps:

  1. I start at a source node, mark it as visited, and process it.
  2. I look at its neighbors, and for the first unvisited neighbor I find, I recursively (or via an explicit stack) dive into that neighbor, repeating this same process.
  3. When I reach a node with no unvisited neighbors, I backtrack to the previous node in the path.
  4. I continue exploring any remaining unvisited neighbors of that previous node, repeating the dive-and-backtrack process until every node reachable from the source has been visited.

Working Principle

The mechanism DFS relies on is depth-first commitment: rather than exploring all neighbors of a node before moving further, I immediately commit to exploring one neighbor fully — descending into its subtree entirely — before even glancing at the node’s other neighbors. This is naturally expressed through recursion, where each recursive call represents “going deeper,” and the call stack automatically remembers the path I took, allowing me to backtrack correctly once a branch is exhausted. This depth-first commitment is exactly what makes DFS so effective for problems involving exhaustive search, since it naturally explores entire branches (and can prune them) before considering alternatives.

Mathematical Foundation

For a graph with V vertices and E edges, DFS visits every vertex once and examines every edge once (or twice for undirected graphs), giving:

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

For recursive implementations, the maximum depth of recursion corresponds to the longest path explored, which in the worst case (a graph shaped like a single long chain) can be:

$$\text{recursion depth} = O(V)$$

DFS discovery and finish times can be used to classify edges formally. For a directed graph, an edge (u, v) is classified based on the relationship between the discovery time $d[u]$, $d[v]$ and finish time $f[u]$, $f[v]$:

$$\text{Tree edge: } v \text{ is undiscovered when } (u,v) \text{ is explored}$$ $$\text{Back edge: } d[u] > d[v] \text{ and } f[v] \text{ is not yet set (v is an ancestor of u)}$$

This classification underlies algorithms like cycle detection (a back edge implies a cycle) and topological sorting (reverse of finish-time order).

Diagrams

flowchart TD
    A[Start: source node] --> B[Mark node visited, process it]
    B --> C{Any unvisited neighbor?}
    C -->|Yes| D[Recurse into that neighbor]
    D --> B
    C -->|No| E[Backtrack to previous node]
    E --> F{Backtrack point has more unvisited neighbors?}
    F -->|Yes| C
    F -->|No| G{Any node left unvisited overall?}
    G -->|Yes| E
    G -->|No| H[Output: All reachable nodes visited]

Pseudocode

DFS(Graph, source)
    create empty set visited
    DFS-VISIT(Graph, source, visited)

DFS-VISIT(Graph, node, visited)
    mark node as visited
    process(node)

    for each neighbor in Graph.adjacent(node)
        if neighbor is not visited
            DFS-VISIT(Graph, neighbor, visited)

Iterative version using an explicit stack:

DFS-ITERATIVE(Graph, source)
    create empty stack S
    create empty set visited
    push source onto S

    while S is not empty
        node = pop S
        if node is not visited
            mark node as visited
            process(node)
            for each neighbor in Graph.adjacent(node)
                if neighbor is not visited
                    push neighbor onto S

Step-by-Step Example

I will run DFS on this graph starting at node S: S — A, S — B, A — C, A — D, B — E, C — F

Step 1: Visit S, mark visited, process it. Neighbors: A, B.

Step 2: Dive into A (first unvisited neighbor of S). Mark visited, process it. Neighbors: C, D.

Step 3: Dive into C (first unvisited neighbor of A). Mark visited, process it. Neighbor: F.

Step 4: Dive into F (only neighbor of C). Mark visited, process it. No unvisited neighbors — backtrack to C.

Step 5: C has no more unvisited neighbors — backtrack to A.

Step 6: A has an unvisited neighbor D — dive into D. Mark visited, process it. No unvisited neighbors — backtrack to A.

Step 7: A has no more unvisited neighbors — backtrack to S.

Step 8: S has an unvisited neighbor B — dive into B. Mark visited, process it. Neighbor: E.

Step 9: Dive into E (only neighbor of B). Mark visited, process it. No unvisited neighbors — backtrack to B, then S. No more unvisited neighbors anywhere.

Traversal order: S, A, C, F, D, B, E

Time Complexity

Space Complexity

DFS requires O(V) space for the visited set. For the recursive implementation, the call stack can grow to O(V) in the worst case (a graph shaped like a single long path), and the same bound applies to the explicit stack in an iterative implementation. Overall space complexity is O(V).

Correctness Analysis

I prove DFS’s correctness by showing it visits every node reachable from the source exactly once. Termination follows from the fact that each node is marked visited before its neighbors are explored, and the visited check prevents re-processing, so the recursion (or stack) must eventually run out of unvisited neighbors to explore. Completeness follows by contradiction: if some node reachable from the source were never visited, then consider the shortest path from the source to that node — every node along that path must have been visited (since DFS explores all edges of every visited node), which would mean the target node itself must have been discovered as a neighbor of the last visited node on that path, contradicting the assumption that it was never visited. Therefore, every reachable node is guaranteed to be visited.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

#define MAX_VERTICES 100

// Simple adjacency list representation
int adjList[MAX_VERTICES][MAX_VERTICES];
int adjCount[MAX_VERTICES];
int visited[MAX_VERTICES];

// Recursive DFS visit function
void dfsVisit(int node) {
    visited[node] = 1;
    printf("%d ", node);

    for (int i = 0; i < adjCount[node]; i++) {
        int neighbor = adjList[node][i];
        if (!visited[neighbor]) {
            dfsVisit(neighbor);
        }
    }
}

// DFS traversal starting from a given source vertex
void dfs(int source, int numVertices) {
    for (int i = 0; i < numVertices; i++) visited[i] = 0;

    printf("DFS traversal order: ");
    dfsVisit(source);
    printf("\n");
}

// Add an undirected edge between u and v
void addEdge(int u, int v) {
    adjList[u][adjCount[u]++] = v;
    adjList[v][adjCount[v]++] = u;
}

int main() {
    int numVertices = 6;  // S=0, A=1, B=2, C=3, D=4, E=5

    addEdge(0, 1); // S-A
    addEdge(0, 2); // S-B
    addEdge(1, 3); // A-C
    addEdge(1, 4); // A-D
    addEdge(2, 5); // B-E

    dfs(0, numVertices);

    return 0;
}

Sample Input and Output

Input: Graph with edges S-A, S-B, A-C, A-D, B-E, starting DFS from S (vertex 0)

Output: DFS traversal order: 0 1 3 4 2 5

(In this indexed example, node C (index 3) is visited right after A because it comes first in the adjacency list order used in the code.)

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version