DFS on graphs

Depth-first search (DFS) explores from a vertex by following edges as deep as possible before backtracking. Implementation is usually recursive (implicit call stack) or iterative with an explicit stack. A visited array prevents revisiting vertices on graphs with cycles. Unlike BFS, DFS does not yield shortest edge-count distances on general graphs—but it is ideal for connectivity, cycle detection, and DAG orderings.

1) Idea

From the current vertex, pick an unvisited neighbor and continue until there is nowhere new to go; then return and try other branches. The order depends on neighbor ordering (e.g. increasing v in a for loop).

Same edges as BFS example:
   1 — 0 — 2       DFS from 0 may go 0→1→3 first, then back to 1, then 0→2→4
       |   |
       3   4

2) Algorithm (recursive)

An iterative DFS pushes vertices onto an explicit stack; order must mirror recursion if you want identical traversal—often neighbors are pushed in reverse order so the smallest neighbor is popped first.

3) DFS vs BFS (reminder)

BFS uses a queue and visits by increasing distance from the source on unweighted graphs. DFS uses a stack (recursion) and goes deep first—preorder discovery order is not the same as BFS layer order.

4) Example in C (same graph as BFS)

Undirected edges 0—1, 0—2, 1—3, 2—4. Adjacency matrix + for (v = 0; v < V; v++) so neighbor 1 is tried before 2 from vertex 0.

#include <stdio.h>
#include <string.h>

#define V 5
int adj[V][V];
int visited[V];

void dfs(int u) {
    visited[u] = 1;
    /* preorder: process u here if needed */
    for (int v = 0; v < V; v++) {
        if (adj[u][v] && !visited[v])
            dfs(v);
    }
}

void dfs_all(void) {
    memset(visited, 0, sizeof visited);
    for (int i = 0; i < V; i++)
        if (!visited[i])
            dfs(i);
}

Recursion depth can be O(V) — on very deep graphs, switch to an explicit stack or raise stack limits with care.

5) Complexity and directed graphs

• Time: O(V + E) with adjacency lists; O(V²) with an adjacency matrix and a full row scan per vertex.
• Space: O(V) for visited plus O(V) worst-case recursion stack (or explicit stack).
• Directed: only recurse along outgoing arcs from u.

See Stack tutorial for LIFO behavior; BFS on graphs for the companion breadth-first lesson.

6) Trace example (same graph as the code)

Undirected edges 0–1, 0–2, 1–3, 2–4. Start dfs(0). Neighbors are scanned in increasing v, so from 0 we recurse to 1 before 2. The table uses recursive call stack (bottom → top); “enter” means we begin dfs(u), “exit” means we return from it.

DFS preorder (discovery order)