What this module covers: Module P-4's tree traversals assumed a tree — no cycles, exactly one path to any node. A general graph (Module P-6) has neither guarantee, which means traversing one safely requires one new piece of bookkeeping: a record of what's already been visited. This module covers depth-first search, both recursive (Module P-1) and iterative (Module F-6's explicit stack), and two classic applications — counting connected regions in a grid, and deep-copying a graph that might contain cycles.
Why Graphs Need a Visited Set
A tree traversal (Module P-4) never revisits a node, because a tree has no cycles — there's exactly one path from the root to any node, so recursing into children can never loop back on itself. A graph has no such guarantee: two nodes can point to each other, or a longer cycle can exist (A → B → C → A). Traversing a graph without tracking what's already been visited risks an infinite loop, walking the same cycle forever.
typescript
Note the shape: check-and-mark visited, process the node, then recurse into each neighbor — this is exactly Module P-4's preorder pattern (root, then children), just generalized from "two fixed children" to "however many neighbors this node happens to have," and with the visited set added specifically to handle the cycles a tree never had to worry about.
Iterative DFS: The Explicit Stack, Made Visible
Recursive DFS relies on the call stack (Module P-1) to remember which nodes still need their remaining neighbors explored. The iterative version makes that bookkeeping explicit, using Module F-6's stack directly:
typescript
This is the same trade Module P-4 already made explicit for tree traversal: the stack here holds exactly what the recursive call stack was managing implicitly — "which nodes are still waiting to have their neighbors explored." One subtlety worth naming: nodes can be pushed onto the stack more than once (a node might be reachable via two different neighbors before either has been processed) — the if (visited.has(node)) continue check at the top of the loop is what safely discards those duplicate entries when they're eventually popped, rather than reprocessing an already-visited node.
Application: Number of Islands (DFS on a Grid)
A 2D grid of land (1) and water (0) — count the number of distinct islands, where an island is a group of land cells connected horizontally or vertically. A grid is an implicit graph: each cell is a node, and its up/down/left/right neighbors are its edges (Module A-9 covers this grid-as-graph framing in full).
typescript
Every time an unvisited land cell is found during the scan, it must belong to a brand-new island — so the count increments once, and exploreIsland marks every cell reachable from it (in any of the four directions) as visited, ensuring none of them triggers a second, incorrect increment later in the scan. This is precisely Module A-3's connected-components question — "how many separate connected groups exist" — answered here by direct DFS traversal rather than Union-Find's incremental tracking. Both are valid tools for the same underlying question; DFS/BFS suit a one-time count over a static structure, while Union-Find suits a structure that's still being built up edge by edge, needing "are these connected yet" answered incrementally as each edge arrives.
Application: Clone Graph (Deep Copy with Cycles)
Deep-copying a graph is more delicate than deep-copying a tree, precisely because of cycles: naively copying node A, which copies its neighbor B, which copies its neighbor A again, recurses forever without a way to recognize "I'm already in the middle of copying this node."
typescript
The critical detail: visited.set(original, clone) happens before recursing into original's neighbors, not after. If a cycle leads back to original while cloning its neighbors, the recursive call finds original already in visited and returns the in-progress clone directly, rather than trying to clone it all over again — this is what turns a graph that would otherwise cause infinite recursion into one that terminates correctly, visiting each original node exactly once.
Where This Shows Up in Your Stack
Dependency resolution and build-order checking: determining whether a set of npm packages, Terraform resources, or build targets can be resolved without a circular dependency is a DFS-based check — Module A-8's topological sort builds directly on this same traversal, adding cycle detection as an explicit, load-bearing feature rather than just something to avoid getting stuck in.
Maze solving and pathfinding: "is there a path from the entrance to the exit" is answered by a DFS (or BFS, Module A-5) that terminates the moment the target is reached, using the exact visited-set discipline from this module to avoid re-exploring dead ends indefinitely.
Deep-cloning any object graph that might contain circular references (a common real bug: JSON.parse(JSON.stringify(obj)) throws on circular structures, precisely because naive serialization has no visited-tracking) needs exactly cloneGraph's pattern — record the clone before recursing into its children, so a cycle resolves to the already-in-progress clone instead of looping forever.
Summary
Graphs, unlike trees, can contain cycles — traversing one safely requires a visited set (Module F-4) to avoid infinite loops, a piece of bookkeeping tree traversal (Module P-4) never needed.
Recursive DFS follows Module P-4's preorder shape (process, then recurse into each neighbor), generalized from a fixed two children to however many neighbors a node has.
Iterative DFS makes the call stack's implicit bookkeeping explicit using Module F-6's stack — with the added subtlety that nodes can be pushed more than once, requiring a visited-check on pop, not just on push.
Number of Islands answers "how many connected components" via direct DFS traversal — the same question Module A-3's Union-Find answers, via a different mechanism suited to a different situation (static structure vs. incrementally-built one).
Clone Graph's correctness hinges on recording a node's clone before recursing into its neighbors — the specific ordering that turns a graph with cycles from an infinite-recursion trap into a correctly-terminating traversal.
The next module, Graph Traversal: Breadth-First Search (BFS), covers the other general-purpose traversal — visiting nodes layer by layer, using Module F-7's queue instead of a stack, and answering a different class of question DFS can't answer efficiently: shortest path in an unweighted graph.
Knowledge Check
Why does DFS require a visited set when traversing a general graph, when Module P-4's tree traversals never needed one?
In cloneGraph, why must visited.set(original, clone) happen before the loop that recurses into original's neighbors, rather than after?
According to the module, how do numIslands (using DFS) and Module A-3's Union-Find both answer the same underlying question, and when does the module suggest each approach is better suited?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionnumIslands(grid:number[][]):number{const rows = grid.length, cols = grid[0].length;const visited =newSet<string>();let islandCount =0;functionexploreIsland(r:number, c:number):void{const key =`${r},${c}`;if(r <0|| r >= rows || c <0|| c >= cols)return;// out of boundsif(grid[r][c]===0|| visited.has(key))return;// water, or already explored visited.add(key);exploreIsland(r -1, c);// upexploreIsland(r +1, c);// downexploreIsland(r, c -1);// leftexploreIsland(r, c +1);// right}for(let r =0; r < rows; r++){for(let c =0; c < cols; c++){if(grid[r][c]===1&&!visited.has(`${r},${c}`)){ islandCount++;exploreIsland(r, c);// mark this entire connected island as visited in one DFS}}}return islandCount;}
classGraphNode{ val:number; neighbors: GraphNode[]=[];constructor(val:number){this.val = val;}}functioncloneGraph(node: GraphNode |null): GraphNode |null{if(node ===null)returnnull;const visited =newMap<GraphNode, GraphNode>();// original node -> its clone (Module F-4)functiondfs(original: GraphNode): GraphNode {if(visited.has(original))return visited.get(original)!;// already cloned — return the existing clone, don't recurse againconst clone =newGraphNode(original.val); visited.set(original, clone);// record BEFORE recursing into neighbors — this is what breaks the cyclefor(const neighbor of original.neighbors){ clone.neighbors.push(dfs(neighbor));}return clone;}returndfs(node);}