Depth-First Search

Graphs O(V + E) O(V)

Dives as deep as possible along each branch before backtracking — implemented with recursion or a stack.

order0

Start node

1/44

Enter dfs(0) — mark 0 visited.

InvariantEvery node on the stack is an ancestor of the current one; the path from the source is exactly that stack.

currentfrontiervisitedtree edge

dfs.c

#define V 6
 
void dfs(int graph[V][V], int u, int visited[V]) {
    visited[u] = 1;
    printf("%d ", u);
    for (int v = 0; v < V; v++) {
        if (graph[u][v] && !visited[v])
            dfs(graph, v, visited);
    }
}

How Depth-First Search works

Follow one branch as deep as it goes before backtracking to the last fork. The recursion stack itself remembers the way back.

When to use it

Cycle detection, topological sorting, connected components, maze/backtracking problems.