DFS — Depth-First Search Algorithm Guide

What is Depth-First Search?

Depth-First Search (DFS) is a graph traversal algorithm that explores a path as far as possible before backtracking. Instead of moving level by level, DFS keeps going deeper into the graph until it cannot continue, then returns to the most recent vertex that still has an unexplored neighbor.

• Traversal idea: go deep first, then backtrack.
• Main data structure: recursion stack or explicit stack.
• Complexity: O(V + E) time and O(V) space.
• Typical uses: cycle detection, topological sorting, components, bridges, articulation points.

Where DFS Fits in Graph Problems

DFS is not just a traversal method. It is a general graph exploration framework that becomes the foundation for many advanced algorithms. Once we know how to visit vertices deeply and backtrack correctly, we can build cycle detection, topological sorting, strongly connected components, articulation points, bridges, and several backtracking techniques on top of it.

Core Intuition

Imagine exploring a maze. At every junction, you choose one path and keep walking until you hit a dead end. Then you backtrack to the previous junction and try another path. That is exactly how DFS behaves on a graph.

When DFS is a Good Choice

• When we need to explore complete branches before trying alternatives.
• When solving structural graph problems rather than shortest path problems.
• When backtracking is natural, such as mazes, puzzles, and recursive search spaces.
• When we need entry/exit order information for each vertex.

DFS Algorithm Steps

1. Start from a source vertex.
2. Mark the current vertex as visited.
3. Process the vertex.
4. Recursively visit each unvisited neighbor.
5. When no unvisited neighbor remains, backtrack.

Worked Example

Suppose the graph has edges: 0-1, 0-2, 1-3, 1-4, 2-5. If DFS starts at 0 and processes neighbors from left to right, one valid traversal is:

0 -> 1 -> 3, backtrack to 1, then 4, backtrack to 0, then 2 -> 5.

So one possible DFS order is: 0, 1, 3, 4, 2, 5. DFS order is not unique; it depends on the order of neighbors.

DFS Tree Idea

As DFS runs, it builds a DFS tree (or DFS forest if the graph is disconnected). Every recursive call that discovers a new vertex becomes a tree edge. This tree records how vertices were first reached during traversal.

Recursive DFS vs Iterative DFS

import java.util.*;

public class DFS {

    static int V;
    static List<List<Integer>> adj;

    static void buildGraph(int v) {
        V = v;
        adj = new ArrayList<>();
        for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
    }

    static void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);  // undirected graph
    }

    // Recursive DFS - O(V + E)
    static void dfsRecursive(int node, boolean[] visited) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfsRecursive(neighbor, visited);
            }
        }
    }

    // Iterative DFS using stack
    static void dfsIterative(int src) {
        boolean[] visited = new boolean[V];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(src);

        System.out.print("Iterative DFS: ");
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (visited[node]) continue;

            visited[node] = true;
            System.out.print(node + " ");

            for (int i = adj.get(node).size() - 1; i >= 0; i--) {
                int neighbor = adj.get(node).get(i);
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                }
            }
        }
        System.out.println();
    }

    // Cycle detection in an undirected graph
    static boolean hasCycle(int node, int parent, boolean[] visited) {
        visited[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                if (hasCycle(neighbor, node, visited)) return true;
            } else if (neighbor != parent) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        buildGraph(6);
        addEdge(0, 1); addEdge(0, 2);
        addEdge(1, 3); addEdge(1, 4);
        addEdge(2, 5);

        boolean[] visited = new boolean[V];
        System.out.print("Recursive DFS: ");
        dfsRecursive(0, visited);
        System.out.println();

        dfsIterative(0);

        buildGraph(4);
        addEdge(0, 1); addEdge(1, 2);
        addEdge(2, 3); addEdge(3, 1);
        boolean[] vis2 = new boolean[V];
        System.out.println("Graph has cycle: " + hasCycle(0, -1, vis2));
    }
}

DFS on Disconnected Graphs

If the graph is disconnected, starting DFS from a single source will only visit one connected component. To traverse the entire graph, we run DFS from every still-unvisited vertex.

1. Loop through all vertices.
2. If a vertex is unvisited, start a new DFS from it.
3. Each new DFS call explores one connected component.

This idea is also why we speak of a DFS forest instead of a single DFS tree in disconnected graphs.

Why DFS is Useful

• Cycle detection: detect whether a graph contains a cycle.
• Connected components: all vertices reached from one DFS call belong to the same component.
• Topological sort: use finish times on a DAG.
• Strongly connected components: foundation of Kosaraju and Tarjan algorithms.
• Backtracking problems: mazes, puzzles, permutations, combinations.
• Bridge and articulation point detection: important in network reliability.

Cycle Detection: Undirected vs Directed Graphs

This distinction is important. The parent trick works for undirected graphs, but directed graphs require tracking whether a node is currently active in the recursive call chain.

Topological Sort using DFS

For a Directed Acyclic Graph (DAG), DFS can produce a topological ordering. The key idea is to push a vertex onto a stack after all of its outgoing neighbors have been processed. This ensures every dependency appears before the task that depends on it.

import java.util.*;

public class TopologicalSort {

    static int V;
    static List<List<Integer>> adj;

    static void buildGraph(int v) {
        V = v;
        adj = new ArrayList<>();
        for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
    }

    static void addEdge(int u, int v) {
        adj.get(u).add(v);  // directed edge u -> v
    }

    static void dfs(int node, boolean[] visited, Deque<Integer> order) {
        visited[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) dfs(neighbor, visited, order);
        }

        order.push(node);
    }

    static void topologicalSort() {
        boolean[] visited = new boolean[V];
        Deque<Integer> order = new ArrayDeque<>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) dfs(i, visited, order);
        }

        System.out.print("Topological order: ");
        while (!order.isEmpty()) System.out.print(order.pop() + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        buildGraph(6);
        addEdge(5, 2); addEdge(5, 0);
        addEdge(4, 0); addEdge(4, 1);
        addEdge(2, 3); addEdge(3, 1);

        topologicalSort();  // one valid answer: 5 4 2 3 1 0
    }
}

Discovery Time and Finish Time

In advanced DFS-based algorithms, we often record two timestamps for each vertex:

• Discovery time: when the vertex is first visited.
• Finish time: when all of its descendants are fully processed.

These timestamps help in topological sorting, strongly connected components, edge classification, and articulation-point/bridge algorithms.

Edge Classification in DFS

In directed graphs, DFS edges are often classified into types:

• Tree edge: leads to a newly discovered vertex.
• Back edge: points to an ancestor in the DFS tree and indicates a cycle.
• Forward edge: points to a descendant already discovered.
• Cross edge: connects different DFS branches.

This classification is useful mostly in theoretical analysis and in advanced graph algorithms.

Preorder and Postorder View

DFS naturally gives two useful orders:

• Preorder: process a node when you first enter it.
• Postorder: process a node after all children are done.

Topological sorting with DFS relies on the postorder idea: push a vertex after exploring all of its outgoing neighbors.

Complexity Analysis

DFS vs BFS

DFS and BFS are both graph traversal algorithms, but they serve different purposes. DFS is usually preferred when we care about structure, recursion, backtracking, and dependency order. BFS is preferred when we care about levels and shortest paths in unweighted graphs.

BFS vs DFS

Common Mistakes

• Forgetting the visited array, which can cause infinite loops on cyclic graphs.
• Assuming DFS gives the shortest path; it usually does not.
• Ignoring recursion depth on large graphs.
• Using undirected cycle detection logic directly on directed graphs; the checks are different.
• Expecting DFS traversal order to be unique; it depends on adjacency order.

Common Questions

• Can DFS be implemented without recursion? Yes, by using an explicit stack.
• Does DFS work on trees? Yes. Tree traversals are special cases of DFS.
• Can DFS detect cycles? Yes, but the method differs for directed and undirected graphs.
• Is DFS always memory efficient? Often yes, but recursive DFS can overflow on very deep graphs.

Key Takeaways

• DFS explores one branch fully before returning.
• It can be implemented recursively or iteratively.
• It is one of the most important tools for structural graph problems.
• Its time complexity is O(V + E).
• Its traversal order supports topological sort, cycle detection, and many advanced graph algorithms.