---

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."

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.

---

Complexity

DFS visits every node once and, for each node, walks its list of neighbors — so time complexity is O(V + E) (V vertices, E edges) on an adjacency list, since the total work across all neighbor-lists sums to the edge count. On an adjacency matrix, checking for neighbors means scanning an entire row of size V for every node, regardless of how many real edges exist, so the same traversal costs O(V²) instead — the representation from Module P-6 you pick has a direct, measurable effect on this algorithm's runtime.

---

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.

---