Graph - Depth First Search (DFS)

DFS starts at a given source node and explores as far as possible along each branch before backtracking. A visited set is maintained to avoid revisiting nodes, which would cause infinite loops in cyclic graphs.

Consider the below undirected graph:

Starting DFS from node 1, the traversal proceeds as follows:

• Visit node 1, mark it visited. Explore its first unvisited neighbour.
• Continue going deeper, visiting each node and exploring its unvisited neighbours, until reaching a dead-end.
• Backtrack to the most recent node that still has unvisited neighbours.
• Repeat until all reachable nodes have been visited.

The recursive approach is the most natural way to implement DFS. We pass a Set of visited nodes and for each unvisited neighbour of the current node, we recursively call DFS.

Algorithm steps:

1. Mark the current node as visited.
2. Process the current node (e.g. add to result list or print).
3. For each neighbour of the current node, if it has not been visited yet, recursively call DFS on it.

import java.util.*;

public class GraphDFS {

    // Adjacency list: node -> list of neighbouring nodes
    private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

    public void addEdge(int from, int to) {
        adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        adjacencyList.computeIfAbsent(to,   k -> new ArrayList<>()).add(from); // undirected
    }

    /** Public entry point for recursive DFS */
    public void dfsRecursive(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start, visited);
    }

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

        List<Integer> neighbours = adjacencyList.getOrDefault(node, Collections.emptyList());
        for (int neighbour : neighbours) {
            if (!visited.contains(neighbour)) {
                dfsHelper(neighbour, visited);
            }
        }
    }
}

Example usage:

GraphDFS graph = new GraphDFS();
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(4, 5);

graph.dfsRecursive(1);
// Possible output: 1 2 4 3 5

The iterative approach uses an explicit Deque as a stack to simulate the recursive call stack. This avoids potential StackOverflowError for very deep or large graphs.

Algorithm steps:

1. Push the start node onto the stack and mark it as visited.
2. While the stack is not empty, pop a node from the top.
3. Process the popped node.
4. Push all unvisited neighbours of the popped node onto the stack, marking each as visited.
5. Repeat until the stack is empty.

public void dfsIterative(int start) {
    Set<Integer> visited = new HashSet<>();
    Deque<Integer> stack = new ArrayDeque<>();

    stack.push(start);
    visited.add(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        System.out.print(node + " "); // process the node

        List<Integer> neighbours = adjacencyList.getOrDefault(node, Collections.emptyList());
        for (int neighbour : neighbours) {
            if (!visited.contains(neighbour)) {
                visited.add(neighbour);
                stack.push(neighbour);
            }
        }
    }
}

• Time complexity: O(V + E): where V is the number of vertices and E is the number of edges. Each vertex and each edge is visited at most once.
• Space complexity: O(V). The visited set and the call stack (or explicit stack) can hold at most V nodes in the worst case (a linear chain graph).

• Cycle detection: detect whether a cycle exists in a directed or undirected graph.
• Topological sorting: order nodes in a Directed Acyclic Graph (DAG) based on dependencies.
• Finding connected components: identify all disconnected subgraphs.
• Solving maze and puzzle problems: explore all possible paths and backtrack on dead-ends.
• Strongly Connected Components (SCC): used in Kosaraju's and Tarjan's algorithms.
• Path finding: determine if a path exists between two nodes.