Graph DFS

Concept

Depth-First Search (DFS) on a Graph works exactly like DFS on a Tree. You plunge down a path as far as possible, and when you hit a dead end, you backtrack.

However, there is one massive, critical difference between Tree DFS and Graph DFS: Cycles.
In a Tree, you can only travel downwards. You will eventually hit a Leaf node and naturally stop.
In a Graph, because edges can connect anywhere, you can easily walk from A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ A $\rightarrow$ B $\rightarrow$ C… triggering an infinite loop and a Stack Overflow error.

The Golden Rule of Graph DFS: You MUST use a Hash Set to track the nodes you have already visited.

Implementation

Let’s assume we have already built our adjList (a Hash Map where the key is the Node, and the value is an array of neighbor Nodes).

// Time Complexity: O(V + E) (We visit every Vertex once, and check every Edge once)
// Space Complexity: O(V) (The Visited Set and the Recursion Call Stack)

function graphDFS(startNode: number, adjList: Map<number, number[]>) {
    // The Holy Grail of Graph Traversal: The Visited Set
    const visited = new Set<number>();

    function dfs(node: number) {
        // 1. Have we been here before? If yes, abort!
        if (visited.has(node)) return;

        // 2. Mark this node as officially visited
        visited.add(node);
        
        console.log(`Processing Node ${node}`);

        // 3. Get all the neighbors
        const neighbors = adjList.get(node) || [];

        // 4. Recursively plunge down into each neighbor
        for (let neighbor of neighbors) {
            dfs(neighbor);
        }
    }

    // Kick off the recursion
    dfs(startNode);
}

The Disconnected Graph Problem

If you run the code above starting at Node 0, it will successfully explore every node connected to Node 0.
But what if the Graph has “Islands” (Disconnected Components)?

[0 - 1 - 2]       [3 - 4]

If you start at 0, the DFS will find 1 and 2, and then stop. Nodes 3 and 4 will never be visited!

To guarantee you visit absolutely every node in a potentially disconnected graph, you must wrap your DFS in an outer for loop that checks every single node.

function exploreEntireGraph(numNodes: number, adjList: Map<number, number[]>) {
    const visited = new Set<number>();

    // Outer loop checks every possible node
    for (let i = 0; i < numNodes; i++) {
        // If it hasn't been visited yet, it must be a brand new Island!
        if (!visited.has(i)) {
            console.log(`Starting a new DFS expedition on Island ${i}...`);
            dfs(i, visited, adjList); // Run the standard DFS
        }
    }
}

Detecting Cycles

Problem: Given a Directed Graph, determine if there is a cycle.

You might think you can just use the standard visited set. If you hit a visited node, there’s a cycle!
Wrong. In a Directed Graph, paths can merge without forming a cycle.
A -> B -> C and A -> D -> C.
Node C will be visited twice, but there is no cycle! You just arrived at C from two different legal paths.

To properly detect a cycle in a Directed Graph, you must track the Current Active Path using a second Hash Set (or by mapping the nodes to 3 states: 0 = Unvisited, 1 = Visiting, 2 = Fully Processed).

If you bump into a node that is currently marked as Visiting (meaning it is actively sitting in the Call Stack above you), you have definitively proven a back-edge Cycle. If you bump into a node that is Fully Processed, it’s just a harmless cross-edge merge.

Interview Questions

Q: Can DFS find the Shortest Path in an unweighted graph?
A: No. DFS plunges randomly down the very first neighbor it sees. It might take a convoluted 100-edge winding path to reach a node that was sitting right next to the start node. To find the shortest path by edge count, you MUST use BFS.