← Graphs · guided lesson
Graphs: BFS & DFS
the story
Graph (vertices + edges) and the adjacency list
Every tool here exists because something was too slow or broke without it. Here is what.
The city of Königsberg had seven bridges over its river. Could you walk across every bridge exactly once? Euler answered in a paper for the St Petersburg Academy's 1736 volume (which only appeared in 1741) — for every possible map, not just this one. He threw away distances and shapes and kept only which land touches which bridge, then counted the bridges at each piece of land. (A complete proof of his rule came later, in Carl Hierholzer's paper of 1873.) Keeping only "what connects to what" is exactly what a graph is.
the problem it solved
Deciding whether every connection can be walked exactly once, for any map, without trying every route.
why it matters: without it
Every "what connects to what" question — routes, friend suggestions, build order — would need its own one-off data structure and its own bugs.
sources: The Euler Archive — E53: Solutio problematis ad geometriam situs pertinentis ↗ · Grötschel & Yuan — Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman (Documenta Mathematica, 2012) ↗
also in this chapter: Breadth-first search (BFS) · Depth-first search (DFS) · Grid as a graph — flood fill · Multi-source BFS · Bipartite check (two-colouring) · Directed cycle detection (three colours) · BFS on an implicit graph
the idea
The idea in 30 seconds
A graph is a set of things (vertices) plus the connections between them (edges). A tree is just a graph with no cycles.
BFS explores in rings: everything 1 step away, then 2 steps, then 3. So it finds the fewest-steps path.
DFS dives down one path as far as it can, then backs up. It's perfect for "explore everything connected to this".
picture this
A game map. BFS clears the fog ring by ring around your base: every tile 1 step away, then 2, then 3 — so the first time it reaches a tile, that's the fewest steps. DFS is a player who runs down one corridor to its dead end, then walks back to the last junction and tries the next corridor.
watch it
BFS ring by ring
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
BFS ring by ring
Watch the queue: nodes leave from the front in order of distance, so dist[] fills in rings 0, 1, 2…
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
DFS with an explicit stack
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
DFS with an explicit stack
The newest neighbour is explored first, so DFS dives deep before it goes wide. Nodes 6–7 sit in another component.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 10
Read it once. Say it out loud once. Bas.
Vocabulary: vertex (node), edge, neighbour, degree. Edges can be directed (one-way, like an Instagram follow) or undirected (two-way, like a LinkedIn connection), and weighted (a cost, like km on a map) or unweighted.
key idea 2 of 10
Read it once. Say it out loud once. Bas.
Store graphs as an adjacency list (List<List<Integer>>, or Map<K, List<K>> for non-integer labels). It uses O(V + E) memory; a matrix uses O(V²) and only pays off for dense graphs or O(1) edge checks.
key idea 3 of 10
Read it once. Say it out loud once. Bas.
BFS = queue. DFS = stack (or recursion, which uses the call stack). Same skeleton, different container — that's the whole difference.
key idea 4 of 10
Read it once. Say it out loud once. Bas.
Always keep a `visited` set. Graphs can have cycles; without it you loop forever. In BFS, mark a vertex when you enqueue it, not when you poll it.
key idea 5 of 10
Read it once. Say it out loud once. Bas.
BFS gives shortest paths in unweighted graphs: the first time it reaches a vertex is through the fewest edges. With weights you need Dijkstra (next chapter).
key idea 6 of 10
Read it once. Say it out loud once. Bas.
Both traversals are O(V + E): each vertex is processed once and each edge is looked at once (twice if undirected).
key idea 7 of 10
Read it once. Say it out loud once. Bas.
A grid is a graph: each cell is a vertex, its 4 (or 8) neighbours are edges. Check bounds first, then walls, then visited.
key idea 8 of 10
Read it once. Say it out loud once. Bas.
Loop over every vertex as a possible start to cover disconnected graphs — that same loop counts connected components.
key idea 9 of 10
Read it once. Say it out loud once. Bas.
Many sources? One BFS. Put every source (rotten oranges, gates, zeros) in the queue before you start; levels then mean "distance to the nearest source".
key idea 10 of 10
Read it once. Say it out loud once. Bas.
Implicit graphs: in puzzles the vertices are states (words, genes, board squares, knight positions) and you generate the neighbours on the fly. Same BFS, no adjacency list.
spot the pattern
When you see this, think this
"Minimum number of steps / moves / transformations" with all moves costing the same
BFS from the start; level = answer
"Count islands / provinces / groups / connected regions"
Loop over every cell/vertex; each unvisited one starts a DFS/BFS → count++ (or union-find)
A 2D grid of 0/1, '#'/'.', land/water
Grid as a graph: 4-directional neighbours with a DIRS array
"Spreads every minute", "all at the same time", "distance to the nearest X"
Multi-source BFS: put every source in the queue first
+6 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Marking visited when you poll instead of when you enqueue: the same vertex gets queued many times — wrong counts and O(E) blow-ups.
- Starting only from vertex 0: disconnected parts are silently skipped. Loop over all vertices.
quick check
One question. No pressure.
You need the minimum number of moves to reach a cell in an unweighted grid. Which traversal?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Number of Islands
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why does BFS find the fewest-edges path in an unweighted graph?
Question 1: Why does BFS find the fewest-edges path in an unweighted graph?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.