Step 3 of 6

50% Complete

Depth-First Search (DFS)

Learn the DFS graph traversal algorithm

What is Depth-First Search?

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (LIFO) to keep track of vertices to visit next. DFS is fundamental for many graph algorithms.

DFS can be implemented iteratively using a stack or recursively using the call stack.

How DFS Works

DFS Algorithm Steps

Start at a source vertex
Mark it as visited
Visit each unvisited neighbor recursively
Continue until all reachable vertices are visited
Backtrack if a vertex has no unvisited neighbors

DFS Traversal - Visual Example

// Graph: 0 - 1 - 3
//         |   |
//         2   4
 
// DFS from vertex 0:
// Step 1: Visit 0 (visited: {0})
// Step 2: Visit neighbor 1 (visited: {0, 1})
// Step 3: Visit neighbor 3 (visited: {0, 1, 3})
// Step 4: No unvisited neighbors of 3, backtrack to 1
// Step 5: Visit neighbor 4 (visited: {0, 1, 3, 4})
// Step 6: No unvisited neighbors, backtrack to 1
// Step 7: No unvisited neighbors, backtrack to 0
// Step 8: Visit neighbor 2 (visited: {0, 1, 3, 4, 2})
 
// DFS Order: 0 → 1 → 3 → 4 → 2
// Pre-order: 0, 1, 3, 4, 2 (visit when entering)

Recursive DFS Implementation

DFS - Recursive Approach

public class DFSRecursive {
    private List<Integer>[] adj;
    private boolean[] visited;
    private List<Integer> traversalOrder;
    
    public DFSRecursive(int V) {
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
    
    // Main DFS method
    public List<Integer> dfs(int start) {
        visited = new boolean[adj.length];
        traversalOrder = new ArrayList<>();
        dfsHelper(start);
        return traversalOrder;
    }
    
    // Helper method (recursive)
    private void dfsHelper(int v) {
        // Mark as visited
        visited[v] = true;
        traversalOrder.add(v);
        
        // Visit all unvisited neighbors
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                dfsHelper(neighbor);
            }
        }
        // Backtracking happens automatically via recursion
    }
    
    public static void main(String[] args) {
        DFSRecursive g = new DFSRecursive(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        
        List<Integer> result = g.dfs(0);
        System.out.println("DFS traversal: " + result);
        // Output: [0, 1, 3, 4, 2] or [0, 1, 4, 3, 2] (order may vary)
    }
}

Iterative DFS Implementation

DFS - Iterative Approach (Using Stack)

public class DFSIterative {
    private List<Integer>[] adj;
    private int V;
    
    public DFSIterative(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
    
    // Iterative DFS using stack
    public List<Integer> dfs(int start) {
        List<Integer> traversalOrder = new ArrayList<>();
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();
        
        // Push start vertex
        stack.push(start);
        
        while (!stack.isEmpty()) {
            // Pop vertex
            int v = stack.pop();
            
            if (!visited[v]) {
                visited[v] = true;
                traversalOrder.add(v);
                
                // Push unvisited neighbors
                // Add in reverse order for left-to-right traversal
                for (int i = adj[v].size() - 1; i >= 0; i--) {
                    int neighbor = adj[v].get(i);
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
        
        return traversalOrder;
    }
    
    public static void main(String[] args) {
        DFSIterative g = new DFSIterative(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        
        List<Integer> result = g.dfs(0);
        System.out.println("DFS traversal: " + result);
    }
}

DFS Applications

Detecting Cycles

Use DFS to detect if a graph contains cycles

Topological Sorting

Sort DAG vertices using DFS finish times

Connected Components

Find all connected components in a graph

Path Finding

Find path between two vertices

Strongly Connected Components

Find SCCs in directed graphs

DFS Complexity Analysis

Time Complexity

O(V + E)

Visit each vertex once, each edge twice

Space Complexity

O(V)

For visited array and recursion/stack

Cycle Detection with DFS

Detecting Cycles in Undirected Graph

public class CycleDetection {
    private List<Integer>[] adj;
    private boolean[] visited;
    
    public CycleDetection(int V) {
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }
    
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
    
    // Check if cycle exists in graph
    public boolean hasCycle() {
        visited = new boolean[adj.length];
        
        // Check each connected component
        for (int i = 0; i < adj.length; i++) {
            if (!visited[i]) {
                if (dfsHasCycle(i, -1)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // DFS to detect cycle
    // parent is the vertex we came from
    private boolean dfsHasCycle(int v, int parent) {
        visited[v] = true;
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                if (dfsHasCycle(neighbor, v)) {
                    return true;
                }
            } else if (neighbor != parent) {
                // Found back edge (cycle)
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        CycleDetection g = new CycleDetection(4);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 0);  // Creates cycle
        
        System.out.println("Has cycle: " + g.hasCycle());  // true
    }
}

DFS Characteristics

Recursive vs Iterative

Recursive: Natural, concise, uses call stack

Iterative: More control, explicit stack, avoids stack overflow

Order Variants

Pre-order: Process vertex before recursing (visit)

Post-order: Process vertex after recursing (finish)

In-order: Process between recursive calls

Key Takeaways

DFS explores graph deeply before backtracking
Time complexity O(V + E) makes it efficient
Can be implemented recursively or iteratively
Useful for cycle detection, topological sorting, connectivity
Backtracking is inherent with recursive implementation
Space complexity depends on graph structure
Foundation for many advanced graph algorithms