Depth First Search (DFS) Explained — Graphs, Recursion & Real-World Patterns

import java.util.*;

public class GraphDFS {

    // Adjacency list — the most common way to represent a sparse graph
    // Each key is a node, each value is a list of its direct neighbours
    private Map<Integer, List<Integer>> adjacencyList;

    public GraphDFS() {
        this.adjacencyList = new HashMap<>();
    }

    // Add a bidirectional (undirected) edge between two nodes
    public void addEdge(int nodeA, int nodeB) {
        // Ensure both nodes have an entry even if they have no other edges yet
        adjacencyList.computeIfAbsent(nodeA, k -> new ArrayList<>()).add(nodeB);
        adjacencyList.computeIfAbsent(nodeB, k -> new ArrayList<>()).add(nodeA);
    }

    // Public entry point — the caller just says 'start here'
    public void depthFirstSearch(int startNode) {
        // We use a Set for O(1) lookup when checking if a node is already visited
        Set<Integer> visitedNodes = new HashSet<>();
        System.out.println("DFS traversal starting from node " + startNode + ":");
        dfsRecursive(startNode, visitedNodes);
        System.out.println(); // clean newline after output
    }

    // Private recursive workhorse — keeps the visited set hidden from the caller
    private void dfsRecursive(int currentNode, Set<Integer> visitedNodes) {
        // Mark this node visited BEFORE processing neighbours
        // Doing it after would cause infinite loops on cycles
        visitedNodes.add(currentNode);
        System.out.print(currentNode + " ");

        // Get all neighbours of the current node
        List<Integer> neighbours = adjacencyList.getOrDefault(currentNode, new ArrayList<>());

        for (int neighbour : neighbours) {
            // Only recurse into a neighbour we haven't visited yet
            // This is the cycle prevention check — absolutely critical
            if (!visitedNodes.contains(neighbour)) {
                dfsRecursive(neighbour, visitedNodes);
                // When this returns, we've fully explored that entire branch
                // and we automatically continue to the next neighbour
            }
        }
    }

    public static void main(String[] args) {
        GraphDFS graph = new GraphDFS();

        // Build a simple undirected graph that looks like this:
        //
        //   1 --- 2 --- 5
        //   |     |
        //   3 --- 4
        //         |
        //         6
        //
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 4);
        graph.addEdge(4, 6);

        graph.depthFirstSearch(1);

        // DFS from node 1 goes: 1 → 2 → 4 → 3 (backtrack) → 6 (backtrack) → 5
        // Notice it dives deep into the 2→4→3 branch before ever visiting 5
    }
}

import java.util.*;

public class IterativeDFS {

    private Map<Integer, List<Integer>> adjacencyList;

    public IterativeDFS() {
        this.adjacencyList = new HashMap<>();
    }

    public void addEdge(int nodeA, int nodeB) {
        adjacencyList.computeIfAbsent(nodeA, k -> new ArrayList<>()).add(nodeB);
        adjacencyList.computeIfAbsent(nodeB, k -> new ArrayList<>()).add(nodeA);
    }

    public void depthFirstSearchIterative(int startNode) {
        Set<Integer> visitedNodes = new HashSet<>();

        // Deque used as a stack — ArrayDeque is faster than Stack in Java
        // Always prefer ArrayDeque over java.util.Stack which is synchronized
        Deque<Integer> explorationStack = new ArrayDeque<>();

        explorationStack.push(startNode); // Push the starting node

        System.out.println("Iterative DFS from node " + startNode + ":");

        while (!explorationStack.isEmpty()) {
            // Pop the top node — this is the one we explore next
            int currentNode = explorationStack.pop();

            // A node might be pushed multiple times before it's popped
            // (two different neighbours could both push the same unvisited node)
            // So we check visited HERE, at pop time, not at push time
            if (visitedNodes.contains(currentNode)) {
                continue; // Already handled — skip it
            }

            visitedNodes.add(currentNode);
            System.out.print(currentNode + " ");

            List<Integer> neighbours = adjacencyList.getOrDefault(currentNode, new ArrayList<>());

            // Push all unvisited neighbours onto the stack
            // They'll be explored in reverse order due to LIFO — that's fine for DFS
            for (int neighbour : neighbours) {
                if (!visitedNodes.contains(neighbour)) {
                    explorationStack.push(neighbour);
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        IterativeDFS graph = new IterativeDFS();

        // Same graph as before:
        //   1 --- 2 --- 5
        //   |     |
        //   3 --- 4
        //         |
        //         6
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 4);
        graph.addEdge(4, 6);

        graph.depthFirstSearchIterative(1);

        // Order may differ from recursive DFS due to stack push order
        // but it's still a valid depth-first traversal
    }
}

import java.util.*;

public class DirectedCycleDetector {

    private Map<String, List<String>> dependencyGraph;

    public DirectedCycleDetector() {
        this.dependencyGraph = new HashMap<>();
    }

    // Add a directed edge: moduleA depends ON moduleB
    // Arrow goes: moduleA → moduleB
    public void addDependency(String moduleA, String moduleB) {
        dependencyGraph.computeIfAbsent(moduleA, k -> new ArrayList<>()).add(moduleB);
        dependencyGraph.computeIfAbsent(moduleB, k -> new ArrayList<>()); // ensure it exists
    }

    // Returns true if a cycle exists anywhere in the graph
    public boolean hasCycle() {
        // Three-state tracking: unvisited nodes won't be in either set
        Set<String> fullyExplored = new HashSet<>();  // DFS completely done for this node
        Set<String> currentPath = new HashSet<>();    // Currently on the active DFS stack

        // We need to start DFS from EVERY node because the graph might not be connected
        for (String module : dependencyGraph.keySet()) {
            if (!fullyExplored.contains(module)) {
                if (dfsHasCycle(module, currentPath, fullyExplored)) {
                    return true; // Found a cycle — stop early
                }
            }
        }
        return false;
    }

    private boolean dfsHasCycle(String currentModule,
                                 Set<String> currentPath,
                                 Set<String> fullyExplored) {

        // Add to current path — we're actively exploring from this node
        currentPath.add(currentModule);

        List<String> dependencies = dependencyGraph.getOrDefault(currentModule, new ArrayList<>());

        for (String dependency : dependencies) {
            if (currentPath.contains(dependency)) {
                // We've reached a node that's already on our current path — CYCLE!
                System.out.println("Cycle detected: " + currentModule + " → " + dependency
                        + " (which is an ancestor on the current path)");
                return true;
            }

            if (!fullyExplored.contains(dependency)) {
                // Not fully explored yet — recurse deeper
                if (dfsHasCycle(dependency, currentPath, fullyExplored)) {
                    return true;
                }
            }
            // If it's in fullyExplored, we've already proven no cycle through that node — skip it
        }

        // Done with this node — remove from current path, mark fully explored
        // This backtrack step is critical: this node is no longer on the active path
        currentPath.remove(currentModule);
        fullyExplored.add(currentModule);

        return false;
    }

    public static void main(String[] args) {
        DirectedCycleDetector buildSystem = new DirectedCycleDetector();

        // Scenario 1: Clean dependency tree (no cycle)
        // auth-service → database-driver → connection-pool
        buildSystem.addDependency("auth-service", "database-driver");
        buildSystem.addDependency("database-driver", "connection-pool");
        buildSystem.addDependency("api-gateway", "auth-service");

        System.out.println("=== Clean Build System ===");
        System.out.println("Has circular dependency: " + buildSystem.hasCycle());

        // Scenario 2: Circular dependency introduced
        DirectedCycleDetector brokenBuildSystem = new DirectedCycleDetector();
        brokenBuildSystem.addDependency("module-a", "module-b");
        brokenBuildSystem.addDependency("module-b", "module-c");
        brokenBuildSystem.addDependency("module-c", "module-a"); // This creates the cycle!

        System.out.println("\n=== Broken Build System ===");
        System.out.println("Has circular dependency: " + brokenBuildSystem.hasCycle());
    }
}