Depth-First Search (DFS): Complete Guide with Examples

1. DFS Core Concepts

Depth-First Search (DFS)

Definition

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (either recursive call stack or explicit stack) and is ideal for pathfinding, cycle detection, and backtracking problems.

How It Works

1

Start at source node

Mark current node as visited
Process the node (print, record, etc.)

2

Explore each neighbor

For each adjacent unvisited node
Recursively (or iteratively) explore it
Go as deep as possible before backtracking

3

Backtrack

When no more unvisited neighbors
Return to previous node
Continue with remaining neighbors

Recursive DFS Implementation

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=' ')  # Process node
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

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

print("DFS starting from 'A':")
dfs_recursive(graph, 'A')  # Output: A B D E F C

function dfsRecursive(graph, node, visited = new Set()) {
    visited.add(node);
    console.log(node);  // Process node
    
    for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
    
    return visited;
}

// Example graph
const graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
};

console.log("DFS starting from 'A':");
dfsRecursive(graph, 'A');  // Output: A B D E F C

import java.util.*;

public class DFSRecursive {
    public static void dfs(Map<String, List<String>> graph, 
                           String node, 
                           Set<String> visited) {
        visited.add(node);
        System.out.print(node + " ");
        
        for (String neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited);
            }
        }
    }
    
    public static void main(String[] args) {
        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.print("DFS from 'A': ");
        dfs(graph, "A", new HashSet<>());
    }
}

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

void dfsRecursive(unordered_map<char, vector<char>>& graph, 
                  char node, 
                  unordered_set<char>& visited) {
    visited.insert(node);
    cout << node << " ";
    
    for (char neighbor : graph[node]) {
        if (visited.find(neighbor) == visited.end()) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

int main() {
    unordered_map<char, vector<char>> graph = {
        {'A', {'B', 'C'}},
        {'B', {'D', 'E'}},
        {'C', {'F'}},
        {'D', {}},
        {'E', {'F'}},
        {'F', {}}
    };
    
    unordered_set<char> visited;
    cout << "DFS from 'A': ";
    dfsRecursive(graph, 'A', visited);
    return 0;
}

Iterative DFS Implementation

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            print(node, end=' ')  # Process node
            
            # Add neighbors to stack (reverse for original order)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited

# Example
print("\nIterative DFS from 'A':")
dfs_iterative(graph, 'A')  # Output: A C F B E D

function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        if (!visited.has(node)) {
            visited.add(node);
            console.log(node);  // Process node
            
            // Add neighbors to stack
            for (const neighbor of graph[node].slice().reverse()) {
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
    
    return visited;
}

console.log("Iterative DFS from 'A':");
dfsIterative(graph, 'A');

import java.util.*;

public class DFSIterative {
    public static void dfs(Map<String, List<String>> graph, String start) {
        Set<String> visited = new HashSet<>();
        Stack<String> stack = new Stack<>();
        stack.push(start);
        
        while (!stack.isEmpty()) {
            String node = stack.pop();
            
            if (!visited.contains(node)) {
                visited.add(node);
                System.out.print(node + " ");
                
                // Add neighbors in reverse order
                List<String> neighbors = graph.get(node);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    String neighbor = neighbors.get(i);
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
}

#include <stack>
void dfsIterative(unordered_map<char, vector<char>>& graph, char start) {
    unordered_set<char> visited;
    stack<char> st;
    st.push(start);
    
    while (!st.empty()) {
        char node = st.top();
        st.pop();
        
        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            cout << node << " ";
            
            // Add neighbors in reverse order
            for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
                if (visited.find(*it) == visited.end()) {
                    st.push(*it);
                }
            }
        }
    }
}

Complexity: O(V + E) time for adjacency list, O(V) space
Use When: Pathfinding, cycle detection, topological sort

2. Binary Tree DFS Traversals

Pre-Order Traversal (Root → Left → Right)

Definition

Pre-Order Traversal visits the root node first, then recursively traverses the left subtree, then the right subtree. It's used for copying trees and prefix expression evaluation.

How It Works

1

Visit root

Process current node first

2

Traverse left subtree

Recursively apply pre-order to left child

3

Traverse right subtree

Recursively apply pre-order to right child

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)  # Visit root
        dfs(node.left)           # Traverse left
        dfs(node.right)          # Traverse right
    dfs(root)
    return result

def preorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

# Example: Tree: 1 -> 2,3; 2 -> 4,5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(preorder_recursive(root))  # [1, 2, 4, 5, 3]

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function preorderRecursive(root) {
    const result = [];
    
    function dfs(node) {
        if (!node) return;
        result.push(node.val);
        dfs(node.left);
        dfs(node.right);
    }
    
    dfs(root);
    return result;
}

function preorderIterative(root) {
    if (!root) return [];
    const result = [];
    const stack = [root];
    
    while (stack.length) {
        const node = stack.pop();
        result.push(node.val);
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    
    return result;
}

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class PreorderTraversal {
    public static List<Integer> preorderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
    
    private static void dfs(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);
        dfs(node.left, result);
        dfs(node.right, result);
    }
    
    public static List<Integer> preorderIterative(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }
}

#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> preorderRecursive(TreeNode* root) {
    vector<int> result;
    function<void(TreeNode*)> dfs = [&](TreeNode* node) {
        if (!node) return;
        result.push_back(node->val);
        dfs(node->left);
        dfs(node->right);
    };
    dfs(root);
    return result;
}

vector<int> preorderIterative(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    stack<TreeNode*> st;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    return result;
}

In-Order Traversal (Left → Root → Right)

Definition

In-Order Traversal visits the left subtree first, then the root, then the right subtree. For BSTs, it produces nodes in sorted order.

def inorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)
    dfs(root)
    return result

def inorder_iterative(root):
    result = []
    stack = []
    current = root
    
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    
    return result

print(inorder_recursive(root))  # [4, 2, 5, 1, 3]

function inorderRecursive(root) {
    const result = [];
    
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        result.push(node.val);
        dfs(node.right);
    }
    
    dfs(root);
    return result;
}

function inorderIterative(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (stack.length || current) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    
    return result;
}

public static List<Integer> inorderRecursive(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorderDfs(root, result);
    return result;
}

private static void inorderDfs(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorderDfs(node.left, result);
    result.add(node.val);
    inorderDfs(node.right, result);
}

public static List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (!stack.isEmpty() || current != null) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }
    return result;
}

vector<int> inorderIterative(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* current = root;
    
    while (!st.empty() || current) {
        while (current) {
            st.push(current);
            current = current->left;
        }
        current = st.top();
        st.pop();
        result.push_back(current->val);
        current = current->right;
    }
    return result;
}

Post-Order Traversal (Left → Right → Root)

Definition

Post-Order Traversal visits the left subtree, then the right subtree, then the root. It's used for deleting trees and computing expressions.

def postorder_recursive(root):
    result = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        result.append(node.val)
    dfs(root)
    return result

def postorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return result[::-1]  # Reverse for post-order

print(postorder_recursive(root))  # [4, 5, 2, 3, 1]

function postorderRecursive(root) {
    const result = [];
    
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        dfs(node.right);
        result.push(node.val);
    }
    
    dfs(root);
    return result;
}

function postorderIterative(root) {
    if (!root) return [];
    const result = [];
    const stack = [root];
    
    while (stack.length) {
        const node = stack.pop();
        result.push(node.val);
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    
    return result.reverse();
}

public static List<Integer> postorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    
    Collections.reverse(result);
    return result;
}

vector<int> postorderIterative(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    stack<TreeNode*> st;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);
        if (node->left) st.push(node->left);
        if (node->right) st.push(node->right);
    }
    
    reverse(result.begin(), result.end());
    return result;
}

3. Cycle Detection in Graphs

Detect Cycle in Directed Graph

Definition

Cycle Detection identifies if a graph contains cycles. For directed graphs, we track nodes in current recursion stack; for undirected graphs, we track parent nodes to avoid false cycles.

How It Works

1

Track three states

Unvisited: node not yet visited
Visiting: node in current recursion stack
Visited: node fully processed

2

DFS with recursion stack

When encountering a "visiting" node → cycle found
Mark node as visiting before exploring neighbors

3

Mark as visited after exploration

Remove from recursion stack when done
Continue with other nodes

def has_cycle_directed(graph):
    visited = set()      # Fully processed
    rec_stack = set()    # Currently in recursion stack
    
    def dfs(node):
        if node in rec_stack:
            return True  # Cycle detected
        if node in visited:
            return False
        
        visited.add(node)
        rec_stack.add(node)
        
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        
        rec_stack.remove(node)
        return False
    
    for node in graph:
        if dfs(node):
            return True
    return False

def has_cycle_undirected(graph):
    visited = set()
    
    def dfs(node, parent):
        visited.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False
    
    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

# Example with cycle
graph_with_cycle = {
    0: [1],
    1: [2],
    2: [0]  # Creates cycle 0-1-2-0
}
print(has_cycle_directed(graph_with_cycle))  # True

function hasCycleDirected(graph) {
    const visited = new Set();
    const recStack = new Set();
    
    function dfs(node) {
        if (recStack.has(node)) return true;
        if (visited.has(node)) return false;
        
        visited.add(node);
        recStack.add(node);
        
        for (const neighbor of graph[node]) {
            if (dfs(neighbor)) return true;
        }
        
        recStack.delete(node);
        return false;
    }
    
    for (const node in graph) {
        if (dfs(node)) return true;
    }
    return false;
}

function hasCycleUndirected(graph) {
    const visited = new Set();
    
    function dfs(node, parent) {
        visited.add(node);
        
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                if (dfs(neighbor, node)) return true;
            } else if (neighbor !== parent) {
                return true;
            }
        }
        return false;
    }
    
    for (const node in graph) {
        if (!visited.has(node)) {
            if (dfs(node, null)) return true;
        }
    }
    return false;
}

import java.util.*;

public class CycleDetection {
    public static boolean hasCycleDirected(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();
        
        for (int node : graph.keySet()) {
            if (dfsDirected(node, graph, visited, recStack)) {
                return true;
            }
        }
        return false;
    }
    
    private static boolean dfsDirected(int node, Map<Integer, List<Integer>> graph,
                                        Set<Integer> visited, Set<Integer> recStack) {
        if (recStack.contains(node)) return true;
        if (visited.contains(node)) return false;
        
        visited.add(node);
        recStack.add(node);
        
        for (int neighbor : graph.get(node)) {
            if (dfsDirected(neighbor, graph, visited, recStack)) {
                return true;
            }
        }
        
        recStack.remove(node);
        return false;
    }
}

#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

bool hasCycleDirected(unordered_map<int, vector<int>>& graph) {
    unordered_set<int> visited;
    unordered_set<int> recStack;
    
    function<bool(int)> dfs = [&](int node) -> bool {
        if (recStack.count(node)) return true;
        if (visited.count(node)) return false;
        
        visited.insert(node);
        recStack.insert(node);
        
        for (int neighbor : graph[node]) {
            if (dfs(neighbor)) return true;
        }
        
        recStack.erase(node);
        return false;
    };
    
    for (auto& [node, _] : graph) {
        if (dfs(node)) return true;
    }
    return false;
}

Complexity: O(V + E) time, O(V) space
Use When: Deadlock detection, dependency validation

4. Topological Sort (DFS-based)

Topological Ordering of DAG

Definition

Topological Sort orders vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u→v, u appears before v. It's used for task scheduling and dependency resolution.

How It Works

1

Perform DFS on each unvisited node

Traverse graph using DFS

2

Push node to stack after processing

Post-order: add to stack when leaving node
Ensures dependencies come first

3

Pop stack for topological order

Stack gives reverse topological order
Pop to get correct ordering

def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        
        stack.append(node)  # Post-order
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return stack[::-1]  # Reverse for topological order

# Example: Course prerequisites
courses = {
    'C1': [],           # No prerequisites
    'C2': ['C1'],       # Needs C1 first
    'C3': ['C1'],       # Needs C1 first
    'C4': ['C2', 'C3']  # Needs C2 and C3
}

order = topological_sort(courses)
print(order)  # Possible order: ['C1', 'C2', 'C3', 'C4']

function topologicalSort(graph) {
    const visited = new Set();
    const stack = [];
    
    function dfs(node) {
        visited.add(node);
        
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                dfs(neighbor);
            }
        }
        
        stack.push(node);  // Post-order
    }
    
    for (const node in graph) {
        if (!visited.has(node)) {
            dfs(node);
        }
    }
    
    return stack.reverse();  // Topological order
}

// Example: Build system dependencies
const dependencies = {
    'libc': [],
    'libssl': ['libc'],
    'curl': ['libssl'],
    'python': ['libc', 'libssl']
};

console.log(topologicalSort(dependencies));
// Possible: ['libc', 'libssl', 'python', 'curl']

import java.util.*;

public class TopologicalSort {
    public static List<String> sort(Map<String, List<String>> graph) {
        Set<String> visited = new HashSet<>();
        List<String> order = new ArrayList<>();
        
        for (String node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfs(node, graph, visited, order);
            }
        }
        
        Collections.reverse(order);
        return order;
    }
    
    private static void dfs(String node, Map<String, List<String>> graph,
                            Set<String> visited, List<String> order) {
        visited.add(node);
        
        for (String neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, graph, visited, order);
            }
        }
        
        order.add(node);  // Post-order
    }
}

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

vector<string> topologicalSort(unordered_map<string, vector<string>>& graph) {
    unordered_set<string> visited;
    vector<string> order;
    
    function<void(const string&)> dfs = [&](const string& node) {
        visited.insert(node);
        
        for (const string& neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                dfs(neighbor);
            }
        }
        
        order.push_back(node);  // Post-order
    };
    
    for (auto& [node, _] : graph) {
        if (visited.find(node) == visited.end()) {
            dfs(node);
        }
    }
    
    reverse(order.begin(), order.end());
    return order;
}

Complexity: O(V + E) time, O(V) space
Use When: Task scheduling, dependency resolution

5. Backtracking with DFS

General Backtracking Template

Definition

Backtracking is an algorithmic technique for solving problems recursively by building candidates incrementally and abandoning (backtracking) partial candidates when they can't lead to a valid solution.

How It Works

1

Make a choice

Select a candidate from available options
Add to current solution path

2

Recursive exploration

Continue building solution recursively
Check if current state is promising

3

Undo choice (backtrack)

Remove choice from current path
Try next candidate

All Subsets (Power Set)

def subsets(nums):
    result = []
    
    def backtrack(start, current):
        result.append(current[:])  # Add copy of current path
        
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()  # Backtrack
    
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

function subsets(nums) {
    const result = [];
    
    function backtrack(start, current) {
        result.push([...current]);
        
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();  // Backtrack
        }
    }
    
    backtrack(0, []);
    return result;
}

public static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private static void backtrack(int[] nums, int start, 
                              List<Integer> current,
                              List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        backtrack(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    
    function<void(int)> backtrack = [&](int start) {
        result.push_back(current);
        
        for (int i = start; i < nums.size(); i++) {
            current.push_back(nums[i]);
            backtrack(i + 1);
            current.pop_back();
        }
    };
    
    backtrack(0);
    return result;
}

All Permutations

def permutations(nums):
    result = []
    used = [False] * len(nums)
    
    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                current.append(nums[i])
                backtrack(current)
                current.pop()  # Backtrack
                used[i] = False
    
    backtrack([])
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

function permutations(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);
    
    function backtrack(current) {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                current.push(nums[i]);
                backtrack(current);
                current.pop();
                used[i] = false;
            }
        }
    }
    
    backtrack([]);
    return result;
}

public static List<List<Integer>> permutations(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, new ArrayList<>(), result);
    return result;
}

private static void backtrack(int[] nums, boolean[] used,
                              List<Integer> current,
                              List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (!used[i]) {
            used[i] = true;
            current.add(nums[i]);
            backtrack(nums, used, current, result);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}

vector<vector<int>> permutations(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    vector<bool> used(nums.size(), false);
    
    function<void()> backtrack = [&]() {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                current.push_back(nums[i]);
                backtrack();
                current.pop_back();
                used[i] = false;
            }
        }
    };
    
    backtrack();
    return result;
}

Complexity: O(n! × n) for permutations, O(2^n) for subsets
Use When: Combinatorial problems, constraint satisfaction

6. Connected Components (Number of Islands)

Finding Connected Components in Grid

Definition

Number of Islands problem counts connected components in a 2D grid. DFS explores all four directions (up, down, left, right) to mark connected land cells.

How It Works

1

Scan grid for unvisited land

Find cell with value '1' not yet visited
Increment island count

2

DFS to mark entire island

Explore all four directions
Mark visited cells (set to '0' or use visited set)

3

Repeat until grid is scanned

Continue scanning for more land
Each DFS marks one complete island

def num_islands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    visited = set()
    
    def dfs(r, c):
        # Check boundaries and conditions
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            grid[r][c] == '0' or (r, c) in visited):
            return
        
        visited.add((r, c))
        # Explore all 4 directions
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        for dr, dc in directions:
            dfs(r + dr, c + dc)
    
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                dfs(r, c)
                count += 1
    
    return count

# Example grid
grid = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']
]
print(num_islands(grid))  # 3

function numIslands(grid) {
    if (!grid.length) return 0;
    
    const rows = grid.length;
    const cols = grid[0].length;
    const visited = new Set();
    
    function dfs(r, c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols ||
            grid[r][c] === '0' || visited.has(`${r},${c}`)) {
            return;
        }
        
        visited.add(`${r},${c}`);
        
        // Explore all 4 directions
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }
    
    let count = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1' && !visited.has(`${r},${c}`)) {
                dfs(r, c);
                count++;
            }
        }
    }
    
    return count;
}

public class NumberOfIslands {
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int count = 0;
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    dfs(grid, r, c, visited);
                    count++;
                }
            }
        }
        return count;
    }
    
    private static void dfs(char[][] grid, int r, int c, boolean[][] visited) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length ||
            grid[r][c] == '0' || visited[r][c]) {
            return;
        }
        
        visited[r][c] = true;
        dfs(grid, r + 1, c, visited);
        dfs(grid, r - 1, c, visited);
        dfs(grid, r, c + 1, visited);
        dfs(grid, r, c - 1, visited);
    }
}

#include <vector>
using namespace std;

void dfs(vector<vector<char>>& grid, int r, int c) {
    if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() ||
        grid[r][c] == '0') {
        return;
    }
    
    grid[r][c] = '0';  // Mark as visited by setting to '0'
    
    dfs(grid, r + 1, c);
    dfs(grid, r - 1, c);
    dfs(grid, r, c + 1);
    dfs(grid, r, c - 1);
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    
    int count = 0;
    for (int r = 0; r < grid.size(); r++) {
        for (int c = 0; c < grid[0].size(); c++) {
            if (grid[r][c] == '1') {
                dfs(grid, r, c);
                count++;
            }
        }
    }
    return count;
}

Complexity: O(rows × cols) time and space
Use When: Grid connectivity, image segmentation

Problem Type	DFS Approach	Complexity
Connected Components/Islands	DFS on each unvisited node	O(V + E)
Cycle Detection (Directed)	Track recursion stack	O(V + E)
Cycle Detection (Undirected)	Track parent node	O(V + E)
Topological Sort	Post-order DFS, reverse	O(V + E)
Path Existence	DFS from start to target	O(V + E)
Tree Traversals	Pre/In/Post-order	O(N)
Backtracking	Try, recurse, undo	O(b^d)

7. Real-World Applications

Web Crawler

DFS-based crawling: Explore links recursively

class WebCrawler:
    def __init__(self):
        self.visited = set()
    
    def crawl(self, url, max_depth=3):
        if url in self.visited or max_depth == 0:
            return []
        
        self.visited.add(url)
        pages = [url]
        
        for link in self.get_links(url):
            pages.extend(self.crawl(link, max_depth - 1))
        
        return pages
    
    def get_links(self, url):
        # Simulate getting links from page
        return []

class WebCrawler {
    constructor() {
        this.visited = new Set();
    }
    
    crawl(url, maxDepth = 3) {
        if (this.visited.has(url) || maxDepth === 0) return [];
        
        this.visited.add(url);
        let pages = [url];
        
        for (const link of this.getLinks(url)) {
            pages.push(...this.crawl(link, maxDepth - 1));
        }
        
        return pages;
    }
}

class WebCrawler {
    private Set<String> visited = new HashSet<>();
    
    public List<String> crawl(String url, int maxDepth) {
        if (visited.contains(url) || maxDepth == 0) return new ArrayList<>();
        
        visited.add(url);
        List<String> pages = new ArrayList<>();
        pages.add(url);
        
        for (String link : getLinks(url)) {
            pages.addAll(crawl(link, maxDepth - 1));
        }
        
        return pages;
    }
}

class WebCrawler {
private:
    unordered_set<string> visited;
    
public:
    vector<string> crawl(string url, int maxDepth = 3) {
        if (visited.count(url) || maxDepth == 0) return {};
        
        visited.insert(url);
        vector<string> pages = {url};
        
        for (string link : getLinks(url)) {
            vector<string> subPages = crawl(link, maxDepth - 1);
            pages.insert(pages.end(), subPages.begin(), subPages.end());
        }
        
        return pages;
    }
};

Maze Solving

Path finding: DFS to find exit

def solve_maze(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    path = []
    
    def dfs(r, c):
        if (r, c) == end:
            path.append((r, c))
            return True
        
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            maze[r][c] == 1):  # 1 = wall
            return False
        
        maze[r][c] = 1  # Mark as visited
        path.append((r, c))
        
        # Try all 4 directions
        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            if dfs(r + dr, c + dc):
                return True
        
        path.pop()  # Backtrack
        return False
    
    dfs(start[0], start[1])
    return path

function solveMaze(maze, start, end) {
    const rows = maze.length, cols = maze[0].length;
    const path = [];
    
    function dfs(r, c) {
        if (r === end[0] && c === end[1]) {
            path.push([r, c]);
            return true;
        }
        
        if (r < 0 || r >= rows || c < 0 || c >= cols || maze[r][c] === 1) {
            return false;
        }
        
        maze[r][c] = 1;  // Mark visited
        path.push([r, c]);
        
        // Try all directions
        const dirs = [[1,0], [-1,0], [0,1], [0,-1]];
        for (const [dr, dc] of dirs) {
            if (dfs(r + dr, c + dc)) return true;
        }
        
        path.pop();  // Backtrack
        return false;
    }
    
    dfs(start[0], start[1]);
    return path;
}

public class MazeSolver {
    public static List<int[]> solveMaze(int[][] maze, int[] start, int[] end) {
        List<int[]> path = new ArrayList<>();
        dfs(maze, start[0], start[1], end, path);
        return path;
    }
    
    private static boolean dfs(int[][] maze, int r, int c, int[] end, List<int[]> path) {
        if (r == end[0] && c == end[1]) {
            path.add(new int[]{r, c});
            return true;
        }
        
        if (r < 0 || r >= maze.length || c < 0 || c >= maze[0].length || maze[r][c] == 1) {
            return false;
        }
        
        maze[r][c] = 1;
        path.add(new int[]{r, c});
        
        int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        for (int[] dir : dirs) {
            if (dfs(maze, r + dir[0], c + dir[1], end, path)) return true;
        }
        
        path.remove(path.size() - 1);
        return false;
    }
}

bool dfs(vector<vector<int>>& maze, int r, int c, 
         pair<int,int> end, vector<pair<int,int>>& path) {
    if (make_pair(r, c) == end) {
        path.push_back({r, c});
        return true;
    }
    
    if (r < 0 || r >= maze.size() || c < 0 || c >= maze[0].size() || maze[r][c] == 1) {
        return false;
    }
    
    maze[r][c] = 1;
    path.push_back({r, c});
    
    int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    for (auto& dir : dirs) {
        if (dfs(maze, r + dir[0], c + dir[1], end, path)) return true;
    }
    
    path.pop_back();
    return false;
}

Report Content

Depth-First Search (DFS): Complete Guide

DFS Usage in Tech (2023)

1. DFS Core Concepts