Coding Exercise: Graph DFS Using Recursion

Traverse graph depth-first: visit node → recurse unvisited neighbors.

Detect cycles, connected components, paths.

Problem Statement

Input: Graph (adjacency list), start node

Output: DFS traversal order

Visit each node exactly once.

Graph Representation

              
C++

          Adjacency list structure
        
vector<vector<int>> adj;
vector<bool> visited;

// Example graph 0→1,0→2,1→2,2→3
adj = {{1,2}, {2}, {3}, {}};

Recursive DFS Solution

              
            
C++

          Complete graph DFS implementation
        
#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

int main() {
    int n = 4;  // nodes 0-3
    vector<vector<int>> adj(n);
    // 0→1,0→2,1→2,2→3
    adj[0] = {1, 2};
    adj[1] = {2};
    adj[2] = {3};
    
    vector<bool> visited(n, false);
    cout << "DFS from 0: ";
    dfs(0, adj, visited);
    cout << endl;
    return 0;
}

DFS Traversal Path

              
TEXT

          Graph traversal order
        
Graph: 0→1→2→3
       ↘
DFS(0): 0 → DFS(1) → DFS(2) → DFS(3)
Output: 0 1 2 3 ✓

Backtracks: 3→2→1→0

Test Cases

              
TEXT

          Expected outputs
        
Line: 0→1 → 0 1
Cycle: 0→1→0 → 0 1
Disconnected → Multiple DFS calls

Complexity

Time: O(V+E)

Space: O(V) - recursion + visited

Practice Variations

1. DFS iterative (stack)

2. Cycle detection in directed graph

3. Topological sort (DAG)

Conclusion

Mastered graph recursion! DFS = tree recursion on steroids.

Next: BFS or shortest path algorithms.