DFS Depth First Search Algorithm

DFS in DAA is best learned by connecting the rule to an interview-style problem. Start with the smallest algorithm step, observe the output, and then add one realistic constraint so the concept becomes practical.

The key habit for this lesson is to watch input graph, array, or recurrence as it changes. That makes the topic easier to debug, easier to explain in interviews, and easier to use in real code without memorizing isolated syntax.

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.

Concept	Meaning in DFS
Visited array / set	Ensures each vertex is processed once
Call stack	Stores the path in recursive DFS
Explicit stack	Used in iterative DFS
Backtracking	Return to a previous vertex after exploring a branch
Discovery time / finish time	Useful in advanced DFS applications

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

Start from a source vertex.
Mark the current vertex as visited.
Process the vertex.
Recursively visit each unvisited neighbor.
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

Approach	How it Works	When to Use
Recursive DFS	Uses the system call stack automatically	Cleaner code, easier to understand
Iterative DFS	Uses an explicit stack data structure	Better control, avoids stack overflow on deep graphs

DFS Traversal and Cycle Detection

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.

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

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

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.

Graph Type	How DFS Detects a Cycle
Undirected graph	If we reach a visited neighbor that is not the parent, a cycle exists
Directed graph	If we reach a vertex currently in the recursion stack, a back edge exists and a cycle is present

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.

Topological Sort using DFS

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:

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

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

Edge Classification in DFS

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

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

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.

Preorder and Postorder View

DFS naturally gives two useful orders:

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

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

Complexity Analysis

Measure	Value	Reason
Time complexity	O(V + E)	Every vertex and edge is processed at most once
Space complexity	O(V)	Visited array plus recursion stack or explicit stack
Risk in recursion	Stack overflow	Can happen on very deep graphs

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

Feature	BFS	DFS
Main structure	Queue	Stack / recursion
Traversal style	Layered	Deep exploration
Shortest path in unweighted graph	Yes	No
Common strength	Distance and minimum hops	Structure analysis and backtracking

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.

Applied guide for DFS

Use DFS when the program needs a clear answer to a specific problem, not because the keyword looks familiar. In a real DAA task, first name the input, then name the transformation, then name the output. This small discipline shows whether the topic is being used correctly or only copied from an example.

A reliable practice flow is: create the smallest working algorithm step, add one normal case, add one edge case such as disconnected graphs and back edges, and then confirm the result with trace table and complexity count. If the result surprises you, reduce the code until the behavior is visible again.

The most common trap here is marking nodes too late and revisiting cycles. Avoid it by writing one sentence before the code that explains why DFS is the right choice. After the code runs, verify the lesson by doing this: record discovery order and visited set.

Identify the exact problem solved by DFS.
Trace input graph, array, or recurrence before and after the main operation.
Keep one intentionally broken version and explain the fix.
Connect the example to an interview-style problem so the idea feels concrete.

Key Takeaways

I can explain where DFS fits inside an interview-style problem.
I can point to the exact input graph, array, or recurrence affected by this topic.
I tested a normal case and an edge case involving disconnected graphs and back edges.
I verified the result with trace table and complexity count instead of assuming it worked.
I can describe the main mistake: marking nodes too late and revisiting cycles.

Common Mistakes to Avoid

WRONG Marking nodes too late and revisiting cycles.

RIGHT Write the expected behavior first, then make the example prove it.

A one-line expectation turns the code from copied syntax into a testable idea.

WRONG Practicing only the perfect input.

RIGHT Also test disconnected graphs and back edges before considering the lesson complete.

The edge case is where most interview follow-up questions begin.

WRONG Looking only at the final output.

RIGHT Trace input graph, array, or recurrence through each important step.

Tracing makes debugging faster because you can see the first incorrect state.

Practice Tasks

Build one small algorithm step that demonstrates DFS in an interview-style problem.
Change the example to include disconnected graphs and back edges and record the difference.
Break the example by deliberately marking nodes too late and revisiting cycles, then write the corrected version.
Explain the finished example in five bullet points: input, operation, output, failure case, and verification.

Frequently Asked Questions

When should I use DFS?

Use it when the problem matches the behavior shown in the example and when the result can be verified through trace table and complexity count.

How do I avoid mistakes in DFS?

Start with a tiny case, then test disconnected graphs and back edges. The main warning sign is marking nodes too late and revisiting cycles.

How can I revise DFS quickly?

Trace input graph, array, or recurrence, predict the result, run the example, and compare your prediction with the actual output.

Previous Next

DFS Depth First Search Algorithm