Graphs & Networks
Graph DFS
🕯️
Picture this
A lone explorer descends into the catacombs, following each tunnel to its dead end by candlelight before turning back.
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
connected componentsislandsflood fillcycle in graphreachableregions
Ask yourself
- Explore a maze/grid/graph fully?
- Count components / islands / flood fill?
- Mark visited; recurse to neighbours.
Canonical template
function dfs(node: string): void {
visited.add(node);
for (const next of adj.get(node) ?? []) {
if (!visited.has(next)) dfs(next);
}
}
Common pitfalls
Forgetting visited → infinite recursion.
Stack overflow on deep graphs (use iterative).