Pattern 1: DFS and BFS with visited
The two traversals you already saw in Matrix and Tree now appear in their most general form. The only novelty compared to trees: since graphs have cycles, the visited set stops being optional — it is what prevents running forever.
Try it first: Number of Connected Components
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
There are n nodes (numbered from 0 to n-1) and a list of edges (undirected edges). Return the number of connected components (groups of nodes linked to each other).
Example: n = 5, edges = [[0,1],[1,2],[3,4]] → 2 (the group {0,1,2} and the group {3,4}).
Tried it? The core idea: every time you find a node not yet visited, it starts a new group — and a search (DFS/BFS) from it marks the entire group. The theory below formalizes this.
The theory: traversing while marking visited
DFS (depth): go as deep as possible along a path, backing up when stuck. Recursive and short:
dfs(node):
mark node as visited
for each neighbor of node:
if not visited: dfs(neighbor)
BFS (breadth): explore in layers, with a queue:
queue = [origin]; mark origin
while the queue is not empty:
node = dequeue
for each neighbor of node:
if not visited: mark and enqueue
Both visit all reachable nodes from the origin, in O(V + E). The difference is the order (depth vs layers) — and the choice follows the same criterion as in Matrix: BFS for the shortest path; DFS for "reach / cover / exists". Compare the orders on the same graph:
Counting connected components
A graph can have several disconnected "pieces". To count them: traverse all nodes; each node still not visited starts a new component (+1), and a search from it marks the whole piece. It is the same reasoning as "counting islands" (Matrix!), now on a general graph. O(V + E) time.
Example: Clone Graph (DFS with a map)
"Copy an entire graph (nodes and edges), creating new objects." The
challenge: when following the edges, you run into nodes already copied (because
of cycles) — and you cannot copy them again. The solution: a map
original → copy, and registering the copy before recursing into the
neighbors (otherwise, a cycle causes infinite recursion):
The map serves two purposes at once: memory of what was already cloned (avoids duplicating) and visited detector (avoids the infinite cycle). Changing the original afterwards proves that the copy is truly independent.
🧠 Review quiz
0/41. Why is the visited set MANDATORY in graphs, but was not in trees?
2. To count connected components, what is the strategy?
3. In Clone Graph, why register the copy in the map BEFORE recursing into the neighbors?
4. DFS and BFS on a graph visit the same nodes. How to choose between them?
Summary
- DFS (depth, recursion) and BFS (layers, queue) traverse what is reachable in O(V+E), always with visited.
- Connected components: each not-visited node starts a search = +1 component.
- Clone Graph: map
original → copyregisters before recursing (cuts cycles and avoids duplicating).
Next lesson: ordering tasks with dependencies — topological sort.