Chapter 68

Home

Depth First Search (DFS)

DFS explores a graph by going as deep as possible before backtracking. It uses a stack (explicit or the call stack via recursion). DFS is the foundation for connectivity, cycle detection, topological sort, and SCC.

Recursive DFS

C++ — recursive DFS

vector visited(V, false);

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
}

// Count components:
int components = 0;
for (int i = 0; i < V; i++)
    if (!visited[i]) { dfs(i); components++; }

Rust — recursive DFS

fn dfs(u: usize, adj: &[Vec], visited: &mut Vec) {
    visited[u] = true;
    for &v in &adj[u] {
        if !visited[v] { dfs(v, adj, visited); }
    }
}

🚨 Stack overflow risk

Recursive DFS on a deep graph (e.g., a chain of 10⁶ nodes) will overflow the call stack. Use iterative DFS with an explicit stack<int> for very deep graphs.

Iterative DFS

C++ — iterative DFS

stack st;
st.push(start);
while (!st.empty()) {
    int u = st.top(); st.pop();
    if (visited[u]) continue;
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v]) st.push(v);
}

Key Takeaways

Practice