Depth-First Search (DFS)

Generated on 2025-07-10 01:55:57 Algorithm Cheatsheet for Technical Interviews

---

Depth-First Search (DFS) - Cheatsheet

1. Quick Overview

• What is it? An algorithm for traversing or searching tree or graph data structures. It explores as far as possible along each branch before backtracking. Think of it like exploring a maze – you go down one path until you hit a dead end, then go back and try another.
• When to use it?
  • Graph traversal and connectivity checking
  • Pathfinding (e.g., finding a path between two nodes)
  • Topological sorting
  • Cycle detection
  • Solving puzzles with a single solution path (e.g., mazes, Sudoku)
  • Tree traversal (pre-order, in-order, post-order)

2. Time & Space Complexity

Metric	Complexity	Explanation
Time	O(V + E)	V = number of vertices (nodes), E = number of edges. We visit each vertex and each edge at most once. In the worst case (dense graph), E could be close to V2, so it might be expressed as O(V2) then, but O(V+E) is more accurate.
Space	O(V)	In the worst case (e.g., a skewed tree or a graph where every node is connected), the recursion depth (call stack) can be proportional to the number of vertices. This is the space used by the implicit call stack. Can be reduced to O(D) if you know the maximum Depth of the graph where D is the maximum depth. Using an explicit stack can also sometimes help manage memory better.

3. Implementation (Recursive & Iterative)

Python

# Recursive DFS (Graph represented as an adjacency list)
def dfs_recursive(graph, start, visited=None):
    """
    Performs Depth-First Search recursively.

    Args:
        graph: A dictionary representing the graph as an adjacency list.
               Keys are nodes, values are lists of neighbors.
        start: The starting node for the search.
        visited: A set to keep track of visited nodes (optional, defaults to None).

    Returns:
        A set of visited nodes.
    """
    if visited is None:
        visited = set()

    visited.add(start)
    print(f"Visiting node: {start}")  # Optional: For tracing the traversal

    for neighbor in graph.get(start, []):  # Handle cases where a node has no neighbors
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited

# Iterative DFS (Graph represented as an adjacency list)
def dfs_iterative(graph, start):
    """
    Performs Depth-First Search iteratively using a stack.

    Args:
        graph: A dictionary representing the graph as an adjacency list.
               Keys are nodes, values are lists of neighbors.
        start: The starting node for the search.

    Returns:
        A set of visited nodes.
    """
    visited = set()
    stack = [start]  # Use a list as a stack

    while stack:
        vertex = stack.pop()  # LIFO: Last In, First Out

        if vertex not in visited:
            visited.add(vertex)
            print(f"Visiting node: {vertex}")  # Optional: For tracing the traversal

            # Important: Add neighbors in reverse order to maintain DFS order
            for neighbor in reversed(graph.get(vertex, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

    return visited

# Example graph (adjacency list)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("Recursive DFS:")
dfs_recursive(graph, 'A')

print("\nIterative DFS:")
dfs_iterative(graph, 'A')

Java

import java.util.*;

public class DFS {

    // Recursive DFS (Graph represented as an adjacency list)
    public static Set<String> dfsRecursive(Map<String, List<String>> graph, String start, Set<String> visited) {
        if (visited == null) {
            visited = new HashSet<>();
        }

        visited.add(start);
        System.out.println("Visiting node: " + start); // Optional: For tracing the traversal

        List<String> neighbors = graph.getOrDefault(start, new ArrayList<>());
        for (String neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(graph, neighbor, visited);
            }
        }

        return visited;
    }


    // Iterative DFS (Graph represented as an adjacency list)
    public static Set<String> dfsIterative(Map<String, List<String>> graph, String start) {
        Set<String> visited = new HashSet<>();
        Stack<String> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            String vertex = stack.pop();

            if (!visited.contains(vertex)) {
                visited.add(vertex);
                System.out.println("Visiting node: " + vertex); // Optional: For tracing the traversal

                // Important:  Iterate in reverse order to mimic the recursive DFS
                List<String> neighbors = graph.getOrDefault(vertex, new ArrayList<>());
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    String neighbor = neighbors.get(i);
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }

        return visited;
    }


    public static void main(String[] args) {
        // Example graph (adjacency list)
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("D", "E"));
        graph.put("C", Arrays.asList("F"));
        graph.put("D", new ArrayList<>());
        graph.put("E", Arrays.asList("F"));
        graph.put("F", new ArrayList<>());

        System.out.println("Recursive DFS:");
        dfsRecursive(graph, "A", null);

        System.out.println("\nIterative DFS:");
        dfsIterative(graph, "A");
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm> // for std::reverse

using namespace std;

// Recursive DFS (Graph represented as an adjacency list)
void dfsRecursive(const unordered_map<char, vector<char>>& graph, char start, unordered_set<char>& visited) {
    visited.insert(start);
    cout << "Visiting node: " << start << endl; // Optional: For tracing the traversal

    for (char neighbor : graph.at(start)) {
        if (visited.find(neighbor) == visited.end()) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}


// Iterative DFS (Graph represented as an adjacency list)
unordered_set<char> dfsIterative(const unordered_map<char, vector<char>>& graph, char start) {
    unordered_set<char> visited;
    stack<char> stack;
    stack.push(start);

    while (!stack.empty()) {
        char vertex = stack.top();
        stack.pop();

        if (visited.find(vertex) == visited.end()) {
            visited.insert(vertex);
            cout << "Visiting node: " << vertex << endl; // Optional: For tracing the traversal

            // Important: Reverse the order of neighbors before pushing onto the stack
            //             to mimic the recursive DFS order.
            vector<char> neighbors = graph.at(vertex);
            reverse(neighbors.begin(), neighbors.end());

            for (char neighbor : neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    stack.push(neighbor);
                }
            }
        }
    }

    return visited;
}


int main() {
    // Example graph (adjacency list)
    unordered_map<char, vector<char>> graph = {
        {'A', {'B', 'C'}},
        {'B', {'D', 'E'}},
        {'C', {'F'}},
        {'D', {}},
        {'E', {'F'}},
        {'F', {}}
    };

    cout << "Recursive DFS:" << endl;
    unordered_set<char> visitedRecursive;
    dfsRecursive(graph, 'A', visitedRecursive);

    cout << "\nIterative DFS:" << endl;
    unordered_set<char> visitedIterative = dfsIterative(graph, 'A');

    return 0;
}

4. Common Patterns

• Pre-order Traversal (Trees): Process the current node before visiting its children.
• In-order Traversal (Trees): Process the left child, then the current node, then the right child. (Useful for sorted binary trees).
• Post-order Traversal (Trees): Process the children before processing the current node. (Useful for deleting a tree or evaluating expressions).
• Pathfinding: Keeping track of the path taken to reach a node.
• Cycle Detection: Detecting cycles in a graph using the “visiting” state to mark nodes currently on the recursion stack.

5. Pro Tips

• Marking Nodes: Always mark nodes as visited to prevent infinite loops in graphs with cycles.
• Recursion Depth: In languages with limited stack size, iterative DFS might be preferred for very deep graphs or trees. Consider increasing stack size if using recursion (but iterative is generally better).
• Adjacency List vs. Adjacency Matrix: Use an adjacency list for sparse graphs (few edges) to save space. Use an adjacency matrix for dense graphs (many edges) for faster neighbor lookups.
• Order of Neighbors: The order in which you visit neighbors matters. It can affect the order of the DFS traversal and the solution found (e.g., in pathfinding). Consider sorting neighbors if needed.
• Backtracking: When implementing search algorithms with DFS, backtracking is crucial. After exploring a path, you must “undo” your changes (e.g., unmark nodes as visited) so that other paths can be explored correctly.

6. Practice Problems

• LeetCode 200. Number of Islands: Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. Use DFS to explore connected components of ‘1’s.
• LeetCode 130. Surrounded Regions: Given a 2D board containing ‘X’ and ‘O’, capture all regions surrounded by ‘X’. Use DFS to find ‘O’s connected to the boundary and mark the rest.
• LeetCode 695. Max Area of Island: Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

7. Templates

These are basic, reusable templates. Adapt them for specific problem requirements.

C++

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

// DFS Template (Recursive) - Adjacency List Representation
void dfs(const vector<vector<int>>& graph, int node, unordered_set<int>& visited) {
    if (visited.count(node)) return; // Base case: Already visited

    visited.insert(node);
    cout << "Visiting node: " << node << endl; // Process node

    for (int neighbor : graph[node]) {
        dfs(graph, neighbor, visited); // Recursive call
    }
}

// DFS Template (Iterative) - Adjacency List Representation
void dfs_iterative(const vector<vector<int>>& graph, int start_node) {
    unordered_set<int> visited;
    stack<int> s;
    s.push(start_node);

    while(!s.empty()){
        int node = s.top();
        s.pop();

        if(visited.count(node)) continue;

        visited.insert(node);
        cout << "Visiting node: " << node << endl;

        for(int i = graph[node].size() -1; i >= 0; i--){
            int neighbor = graph[node][i];
            if(!visited.count(neighbor)){
                s.push(neighbor);
            }
        }

    }
}

int main() {
    // Example graph (adjacency list) - replace with your graph
    vector<vector<int>> graph = {
        {1, 2},   // Neighbors of node 0
        {0, 3, 4}, // Neighbors of node 1
        {0, 5},   // Neighbors of node 2
        {1},       // Neighbors of node 3
        {1},       // Neighbors of node 4
        {2}        // Neighbors of node 5
    };

    unordered_set<int> visited;
    cout << "Recursive DFS:" << endl;
    dfs(graph, 0, visited); // Start DFS from node 0

    cout << "Iterative DFS:" << endl;
    dfs_iterative(graph, 0);
    return 0;
}

Python

# DFS Template (Recursive) - Adjacency List Representation
def dfs(graph, node, visited):
    if node in visited:
        return

    visited.add(node)
    print(f"Visiting node: {node}")  # Process node

    for neighbor in graph.get(node, []):
        dfs(graph, neighbor, visited)

# DFS Template (Iterative) - Adjacency List Representation
def dfs_iterative(graph, start_node):
    visited = set()
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node in visited:
            continue

        visited.add(node)
        print(f"Visiting node: {node}")

        for neighbor in reversed(graph.get(node, [])):  # Reverse for correct DFS order
            if neighbor not in visited:
                stack.append(neighbor)


# Example graph (adjacency list) - replace with your graph
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2]
}

visited = set()
print("Recursive DFS:")
dfs(graph, 0, visited)  # Start DFS from node 0

print("Iterative DFS:")
dfs_iterative(graph, 0)

Java

import java.util.*;

public class DFSTemplate {

    // DFS Template (Recursive) - Adjacency List Representation
    public static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
        if (visited.contains(node)) return;

        visited.add(node);
        System.out.println("Visiting node: " + node); // Process node

        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            dfs(graph, neighbor, visited);
        }
    }

    // DFS Template (Iterative) - Adjacency List Representation
    public static void dfsIterative(Map<Integer, List<Integer>> graph, int startNode) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(startNode);

        while (!stack.isEmpty()) {
            int node = stack.pop();

            if (visited.contains(node)) {
                continue;
            }

            visited.add(node);
            System.out.println("Visiting node: " + node);

            List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }



    public static void main(String[] args) {
        // Example graph (adjacency list) - replace with your graph
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 3, 4));
        graph.put(2, Arrays.asList(0, 5));
        graph.put(3, Arrays.asList(1));
        graph.put(4, Arrays.asList(1));
        graph.put(5, Arrays.asList(2));

        Set<Integer> visited = new HashSet<>();
        System.out.println("Recursive DFS:");
        dfs(graph, 0, visited); // Start DFS from node 0

        System.out.println("Iterative DFS:");
        dfsIterative(graph, 0);
    }
}