Synthesis: which pattern to use?
Four graph patterns covered. This section is the peak of the DFS/BFS reasoning that has been coming since Matrix and Tree — here it appears on the most general structure. Time to train the reflex of choosing the tool.
The section's decision tree
1. Do I need to TRAVERSE / reach / count connected groups?
├── reach / cover / "is there a path?" → DFS or BFS (with visited)
├── SHORTEST path / fewest steps → BFS
└── several sources ("time to reach everything") → MULTI-SOURCE BFS
2. Are there DEPENDENCIES / order ("X before Y") in a directed graph?
→ TOPOLOGICAL SORT (Kahn) — also detects a cycle
3. Do I need to group / "are they connected?" / detect a cycle (undirected),
especially with edges arriving gradually?
→ UNION-FIND
4. Is it a GRID? → treat it as a graph (neighbors = edges) and use the same DFS/BFS
And the section's reflexes: always use visited (graphs have cycles); build the adjacency list from the edges; and name the Big-O as O(V + E).
The section's complete map
| Pattern | Key question | Time |
|---|---|---|
| DFS / BFS | "reach / count components / clone" | O(V + E) |
| BFS (shortest) | "fewest number of steps" | O(V + E) |
| Topological sort | "order with dependencies / is there a cycle?" | O(V + E) |
| Union-Find | "connected? / cycle / dynamic connections" | ~O(V + E·α) |
| Multi-source BFS | "time to reach everything (grid)" | O(V + E) |
The idea that ties it all together: a graph is nodes + edges, and almost everything is a traversal with visited. DFS (depth), BFS (layers), topological (by dependencies), Union-Find (by groups) — four ways to organize that traversal. Tree, grid and linked list were rehearsals for this.
Section quiz
Statements you have not seen in the lessons. Identify the pattern and why. 6+ correct: ready for the exam.
🧠 Section quiz: Graphs
0/71. 'Is there a path between nodes A and B in an undirected graph?' Which pattern?
2. 'What is the smallest number of transformations from one word into another, changing one letter at a time (each step valid in the dictionary)?' Which pattern?
3. 'There are n tasks with dependencies; is there a valid order of execution?' Which pattern?
4. 'Cities are connected by roads, one at a time; after each road, how many groups of connected cities are there?' Which pattern?
5. 'Distance from each free cell to the nearest wall/door in a grid.' Which pattern?
6. 'Longest sequence of consecutive numbers in an array (e.g.: [100,4,200,1,3,2] → 4, since 1,2,3,4).' How does group thinking help?
7. What is the parent idea that ties the whole section together — and connects it with Matrix and Tree?
Ready for the exam?
The Graph section's final exam has three brand-new problems — easy, medium and hard — with hidden cases. The hard one (Word Ladder) is a BFS in an implicit graph of words: the confirmation that you see graphs even where they are not drawn out. The four lessons cover everything you need.
Good luck! Go back to the section page and click "Final exam".