What is DFS (Depth First Search)?

• Strategy – follow one path as far as it goes before backtracking to explore the next branch.
• Implementation – naturally expressed with recursion (call stack) or iteratively with an explicit stack.
• Visited set – required in graphs to prevent infinite loops on cycles; unnecessary in trees.
• Applications – cycle detection, topological sort, connected components, path finding.
• Complexity – O(V + E) time, O(V) space for the visited set plus O(h) or O(V) for the stack.

What is Depth-First Search?

Depth-first search (DFS) is a graph and tree traversal algorithm that follows one path as far as it can go before backtracking to explore the next unexplored branch. It commits to a direction immediately, always choosing depth over breadth.

DFS is most naturally expressed with recursion, where the call stack remembers where to backtrack to. It can also be implemented iteratively with an explicit stack.

How does recursive DFS work?

The recursive form marks the current node as visited, processes it, then recurses into each unvisited neighbour. When a recursive call returns, control naturally resumes at the previous node, which is the backtracking step.

package com.bank.service;

import java.util.*;

public class FraudTrailTracer {

    private Map<String, List<String>> transferGraph;
    private Set<String> visited;

    public FraudTrailTracer(Map<String, List<String>> transferGraph) {
        this.transferGraph = transferGraph;
        this.visited = new HashSet<>();
    }

    public void traceRecursive(String account) {
        if (visited.contains(account)) return;
        visited.add(account);
        System.out.println("Investigating account: " + account);

        for (String next : transferGraph.getOrDefault(account, Collections.emptyList())) {
            traceRecursive(next);
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("Rajesh", Arrays.asList("Priya", "Amit"));
        graph.put("Priya", Arrays.asList("Deepak"));
        graph.put("Amit", Arrays.asList("Sonal"));
        graph.put("Deepak", Collections.emptyList());
        graph.put("Sonal", Collections.emptyList());

        FraudTrailTracer tracer = new FraudTrailTracer(graph);
        tracer.traceRecursive("Rajesh");
    }
}

Investigating account: Rajesh
Investigating account: Priya
Investigating account: Deepak
Investigating account: Amit
Investigating account: Sonal

How does iterative DFS work?

The iterative version replaces the call stack with an explicit stack. Push the source, then repeatedly pop a node, process it if unvisited, and push its neighbours.

public void traceIterative(String startAccount) {
    Stack<String> stack = new Stack<>();
    stack.push(startAccount);

    while (!stack.isEmpty()) {
        String account = stack.pop();
        if (visited.contains(account)) continue;
        visited.add(account);
        System.out.println("Investigating account: " + account);

        List<String> neighbours = transferGraph.getOrDefault(account, Collections.emptyList());
        for (int i = neighbours.size() - 1; i >= 0; i--) {
            stack.push(neighbours.get(i));
        }
    }
}
// Note: pushing in reverse order preserves left-to-right processing

How is DFS different from BFS?

| Aspect | DFS | BFS |
|---|---|---|
| Data structure | Stack (or recursion) | Queue |
| Exploration | Goes deep first | Goes wide first |
| Shortest path | No guarantee | Guarantees shortest (unweighted) |
| Memory | O(depth) | O(width of widest level) |
| Cycle detection | Back-edge on recursion stack | Not directly |
| Topological sort | Yes, via finish order | Yes, via Kahn's algorithm |
| Use case | Path existence, cycles, components | Shortest path, level order |

// BFS uses a queue instead of a stack
Queue<String> queue = new LinkedList<>();
queue.offer(startAccount);
while (!queue.isEmpty()) {
    String account = queue.poll();
    if (visited.contains(account)) continue;
    visited.add(account);
    for (String next : transferGraph.getOrDefault(account, Collections.emptyList())) {
        queue.offer(next);
    }
}

What is DFS used for?

DFS has several important applications beyond simple traversal.

• Cycle detection – a back edge to a node on the current recursion stack indicates a cycle.
• Topological sort – record nodes in reverse finish order for dependency ordering.
• Connected components – run DFS from each unvisited node; each run discovers one component.
• Path finding – DFS naturally finds any path between two nodes (not necessarily shortest).
• Strongly connected components – Tarjan's and Kosaraju's algorithms use DFS.

// Cycle detection: back edge to node on recursion stack
public boolean hasCycle(String account, Set<String> onStack) {
    visited.add(account);
    onStack.add(account);
    for (String next : transferGraph.getOrDefault(account, Collections.emptyList())) {
        if (onStack.contains(next)) return true; // cycle: money loops back
        if (!visited.contains(next) && hasCycle(next, onStack)) return true;
    }
    onStack.remove(account);
    return false;
}

What are the edge cases?

• Disconnected graph – DFS from one node does not visit all nodes; run DFS from every unvisited node.
• Self-loop – a node with an edge to itself; the visited check prevents infinite recursion.
• Empty graph – no nodes to visit; handle gracefully.
• Very deep graph – recursive DFS overflows the call stack; use iterative version.

// Disconnected graph: must start DFS from each unvisited node
for (String account : transferGraph.keySet()) {
    if (!visited.contains(account)) {
        traceRecursive(account);
    }
}

What are common mistakes?

The most common mistake is forgetting the visited set in a graph, causing infinite loops on cycles.

// WRONG: no visited check in a graph with cycles
public void dfsBuggy(String account) {
    System.out.println(account);
    for (String next : transferGraph.getOrDefault(account, Collections.emptyList())) {
        dfsBuggy(next); // infinite loop if cycle exists
    }
}

// CORRECT: check visited before recursing
public void dfsCorrect(String account) {
    if (visited.contains(account)) return;
    visited.add(account);
    for (String next : transferGraph.getOrDefault(account, Collections.emptyList())) {
        dfsCorrect(next);
    }
}

What is the time and space complexity?

DFS visits every vertex once and examines every edge once, giving O(V + E) time. Space is O(V) for the visited set plus O(h) for the recursion stack (or O(V) in the worst case of a degenerate graph). For a banking transaction graph with millions of accounts, the iterative version is preferred to avoid stack overflow.

What should a senior engineer know?

A senior engineer should know the distinction between tree edges, back edges, forward edges, and cross edges in a DFS forest. Back edges indicate cycles, and the DFS finish time ordering produces a topological sort. They should also understand that DFS memory is proportional to depth, making it lighter than BFS for wide graphs but heavier for deep narrow ones.