Depth-First Search (DFS) is one of the most widely used graph traversal algorithms. It explores as far as possible along a branch before backtracking, making it a fundamental concept in computer science, especially for graph-based problems like pathfinding, solving puzzles, and connected components in a graph.

DFS can be applied to both graphs and binary trees. The main idea behind DFS is to explore a node, then recursively explore each of its unvisited neighbors (or children) until you backtrack.

In this blog, we’ll explore the concept of DFS, its different implementations, and its applications with examples in Java.

📚 What is Depth-First Search (DFS)?

DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (or any arbitrary node in the case of a graph) and explores as far as possible along each branch before backtracking. This makes DFS suitable for exploring deep paths in the structure.

DFS can be implemented in two ways:

  1. Recursive DFS
  2. Iterative DFS (using a stack)

DFS Algorithm Steps

  1. Start at the root node (or any arbitrary node).
  2. Mark the node as visited.
  3. Explore each adjacent node (or child in the case of trees) recursively or iteratively.
  4. Backtrack if necessary (i.e., when there are no more adjacent unvisited nodes).

🛠️ Types of DFS

DFS can be applied in several contexts, especially in graph-related problems:

  • DFS in trees: Explores a tree structure, which is a specific case of a graph.
  • DFS in graphs: Can be used for searching all vertices, discovering connected components, or solving pathfinding problems.
  • DFS for solving puzzles: DFS is often used in backtracking problems, such as solving mazes, Sudoku, or N-Queens.

🧑‍💻 DFS in Java

1. DFS Recursive Implementation (for Trees and Graphs)

In the recursive approach, we start at a node, mark it as visited, and recursively visit its neighbors (or children in case of trees).

DFS for Graphs (Recursive) 

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    public void addEdge(int u, int v) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(u).add(v);
        adjList.get(v).add(u); // For an undirected graph
    }

    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsRecursive(start, visited);
    }

    private void dfsRecursive(int node, Set<Integer> visited) {
        // Visit the node
        System.out.print(node + " ");
        visited.add(node);

        // Recur for all the adjacent vertices
        for (int neighbor : adjList.get(node)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited);
            }
        }
    }
}

public class DFSExample {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);

        System.out.println("DFS starting from node 0:");
        graph.dfs(0);  // Starting DFS from node 0
    }
}

Explanation:

  • We create an adjacency list to represent the graph.
  • dfsRecursive function is called recursively to visit each unvisited node.
  • A set visited keeps track of the nodes that have been visited to avoid revisiting nodes.

Output: 

DFS starting from node 0:
0 1 3 4 2

2. DFS Iterative Implementation (Using Stack)

In the iterative approach, we can simulate the recursive function using an explicit stack. This can be useful in situations where recursion might lead to stack overflow for large trees/graphs (for instance, in very deep recursive trees or graphs).

DFS for Graphs (Iterative) 

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph() {
        adjList = new HashMap<>();
    }

    public void addEdge(int u, int v) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(u).add(v);
        adjList.get(v).add(u); // For an undirected graph
    }

    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited.contains(node)) {
                System.out.print(node + " ");
                visited.add(node);

                // Push adjacent nodes to stack (to visit them later)
                for (int neighbor : adjList.get(node)) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
}

public class DFSExample {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);

        System.out.println("DFS starting from node 0 (Iterative):");
        graph.dfs(0);  // Starting DFS from node 0
    }
}

Explanation:

  • In this approach, we use an explicit stack to simulate the recursive calls.
  • We pop nodes from the stack and explore their neighbors, pushing unvisited neighbors back into the stack.
  • The process continues until all reachable nodes are visited.

Output: 

DFS starting from node 0 (Iterative):
0 2 1 4 3

🧠 Time and Space Complexity

Time Complexity:

  • DFS takes O(V + E) time, where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because we visit each node and edge once.
  • For trees, it’s O(n) where n is the number of nodes, as each node is visited once.

Space Complexity:

  • DFS (Recursive): The space complexity is O(h), where h is the height of the tree or the maximum depth of recursion in the graph (it’s the space used by the recursion stack).
  • DFS (Iterative): The space complexity is O(V) due to the stack holding the nodes.

🎯 Applications of DFS

  1. Pathfinding: DFS can be used to find paths between nodes in a graph. It is particularly useful in situations where you want to explore all possible paths.
  2. Connected Components: DFS can be used to find all the connected components in an undirected graph.
  3. Topological Sorting: DFS is an essential part of topological sorting of directed acyclic graphs (DAGs).
  4. Cycle Detection: DFS can be used to detect cycles in directed and undirected graphs.
  5. Backtracking: DFS is commonly used in solving puzzles like N-Queens, Sudoku, and Maze Solving.
  6. Graph Traversal: DFS is used to traverse graphs to gather information about nodes and edges.

🎓 Interview Tips

  • Graph Representation: Be comfortable with different ways to represent graphs, such as using an adjacency list or adjacency matrix.
  • Edge Cases: Handle edge cases like empty graphs, graphs with a single node, or disconnected graphs.
  • Recursive vs Iterative: Understand the trade-offs between using recursion and using an explicit stack for DFS. Know when one approach is better than the other.
  • Backtracking: DFS is often a key component in backtracking problems. Practice common problems like N-Queens or Sudoku Solver.
  • Cycle Detection: Be prepared to implement DFS for cycle detection in both directed and undirected graphs.

📝 Conclusion

Depth-First Search (DFS) is a powerful and versatile algorithm for traversing graphs and trees. Whether you're solving puzzles, exploring graphs, or finding paths between nodes, DFS is a key tool in your algorithmic toolbox. The recursive and iterative implementations each have their advantages, depending on the problem at hand. Mastering DFS is essential for any software developer working with graph-related problems.