Graphs: BFS & DFS

Dots and lines model almost everything. Two traversals explore all of them.

intermediate~95 min7 simulations16 problems

▶ guided lesson ⚡ 1-minute summary ↻ 14 recall cards

before this: Recursion · Stacks · Queues · Traversals

Section

01 · why it exists

Why this exists, and the weight it carries

since1736

Graph (vertices + edges) and the adjacency list

Leonhard Euler

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 solvedDeciding whether every connection can be walked exactly once, for any map, without trying every route.

its jobs today

Maps and routing: junctions are vertices, roads are edges (with km or minutes as weights).
Social and professional networks: people are vertices, follows or connections are edges.
Build tools and package managers: modules are vertices, "depends on" is a directed edge.
The JVM's garbage collector: objects are vertices, references are edges, and anything not reachable from the roots is garbage.

the weight it carries

Illustrative: 10 lakh users with 200 connections each → E = 10⁶ × 200 / 2 = 10⁸ edges. An adjacency list stores 2E = 2 × 10⁸ entries. A matrix needs (10⁶)² = 10¹² cells — 5,000× more slots, almost all of them empty.

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.

when · why · how

when: The problem has things plus links between them: cities and roads, people and follows, cells and their neighbours, tasks and dependencies.
why: An adjacency list costs O(V + E) memory and lists a vertex's neighbours in O(degree). A matrix costs O(V²) and only wins for dense graphs or O(1) "is there an edge?" checks.
how: List<List<Integer>> when vertices are 0..n−1 (create a list for every vertex first); Map<K, List<K>> with computeIfAbsent for labels; int[]{v, w} pairs for weights.

since1957–1961

Breadth-first search (BFS)

Edward F. Moore; C. Y. Lee

In April 1957, at a Harvard symposium on switching theory, Edward F. Moore presented "The Shortest Path Through a Maze" (printed in the 1959 proceedings). His method spreads out in waves: every spot 1 step away, then 2, then 3 — so the first time a spot is reached, it is reached by the fewest steps. In 1961 C. Y. Lee published the same wave idea for finding connection paths in wiring layouts. Today that wave is a queue: first in, first out.

the problem it solvedFinding the fewest-steps path through a maze or a grid, and routing connections between points in a wiring layout.

its jobs today

Fewest moves on game maps and grids — the unweighted base of A* pathfinding.
Degrees of separation: LinkedIn-style 1st / 2nd / 3rd connections are BFS levels.
Web crawlers visit pages roughly level by level from seed URLs, with a visited set of URLs.
Spread simulations (rot, fire, infection) and "distance to the nearest X" maps via multi-source BFS.

the weight it carries

Illustrative: a 1000 × 1000 game map has 10⁶ tiles and under 4 × 10⁶ moves between neighbours. BFS touches each tile and each move once — about 5 × 10⁶ steps — to get the fewest moves to every tile. Trying every path with DFS is exponential.

without it

"Fewest steps" questions would need exponential path enumeration, or a heavier weighted algorithm (Dijkstra) paying an extra log factor for nothing.

when · why · how

when: Every move costs the same and you need the fewest moves, or anything "level by level" (minutes, rings, degrees).
why: The queue releases vertices in order of distance, so the first discovery is the shortest — in O(V + E) time and O(V) space.
how: Deque<Integer> queue = new ArrayDeque<>(), offer / poll, and a dist[] filled with -1 that doubles as the visited mark. Mark on enqueue. Snapshot queue.size() to work level by level.

since1882 (Trémaux's rule); 1972 (Tarjan)

Depth-first search (DFS)

Charles Pierre Trémaux, via Édouard Lucas; Robert Tarjan

In the early 1880s Édouard Lucas's Récréations mathématiques described Trémaux's rule for escaping any maze: mark each passage you use, and back up when you are stuck. The rule always finds a way out if one exists — but not the shortest one. In 1972 Robert Tarjan showed that this dive-and-backtrack search, run on a computer, solves connectivity problems in time proportional to V + E. That paper made DFS the engine of many linear-time graph algorithms.

the problem it solvedGetting through any maze without walking in circles; later, solving connectivity questions in linear time.

its jobs today

Marking everything reachable: the GC mark phase, "delete this folder and everything inside", flood fill.
Cycle checks: build tools reject circular dependencies with a coloured DFS.
The base of topological sort, strongly connected components and bridge finding (later chapters).

the weight it carries

Illustrative: a build with 2,000 modules and 10,000 dependency edges. One coloured DFS proves there is no cycle in 2,000 + 10,000 = 12,000 steps. Asking "can A reach B?" for every pair separately would be 2,000² = 4 × 10⁶ questions, each a search of its own.

without it

Reachability, cycle and connectivity checks would each need a custom search — and many linear-time graph algorithms would not exist.

when · why · how

when: Visit or mark everything connected, detect cycles, explore all paths — whenever the order doesn't have to be by distance.
why: O(V + E) like BFS, usually less code. Recursion uses O(depth) stack, so very deep inputs need an explicit stack.
how: A recursive method with a boolean[] visited (mark before going deeper), or ArrayDeque with push/pop and the visited check on pop.

since?

Grid as a graph — flood fill

No single inventor: seed-fill programs existed in several 1970s paint systems. Alvy Ray Smith's 1979 SIGGRAPH paper "Tint Fill" documents one used at NYIT and says fill algorithms had already been presented "several times before".

its jobs today

The paint-bucket tool in MS Paint and Photoshop: recolour every connected pixel of one colour.
Counting and measuring regions: islands on a map, blobs in a scanned image, empty areas a game opens up in one click.
Game maps: which tiles can a unit reach at all, before asking how far they are.

the weight it carries

Illustrative: a 4K image is 3840 × 2160 = 8,294,400 pixels. A paint-bucket fill repaints each pixel at most once and checks 4 neighbours each: at most about 3.3 × 10⁷ checks. Done recursively, one big region could need millions of nested calls — so real tools use a queue or stack.

without it

Every "connected region" question on an image or a map would turn into ad-hoc scanning that re-checks the same cells again and again.

when · why · how

when: 2D grids of land/water, pixels, open/blocked cells — count regions, measure them, repaint them, or mark what touches the border.
why: Each cell is a vertex with up to 4 neighbours, so a fill is O(rows × cols). Overwriting the cell ('1' → '0') doubles as the visited mark.
how: A DIRS = {{1,0},{-1,0},{0,1},{0,-1}} array; check bounds, then wall/colour, then visited. Recursion for small grids; ArrayDeque for big ones.

since?

Multi-source BFS

A standard textbook trick — one BFS from an imaginary source wired to every real source. No single inventor.

its jobs today

"Distance to the nearest X" maps: nearest exit, nearest ATM, nearest 0 in a matrix, for every cell at once.
Spread over time: rot, fire, infection or a network broadcast that starts in many places together.
Splitting a map between facilities: every cell learns which source reaches it first.

the weight it carries

Illustrative: a 1000 × 1000 grid with 500 gates. One BFS per gate: 500 × 10⁶ = 5 × 10⁸ cell visits. One multi-source BFS: 10⁶ cell visits — 500× less work.

without it

Nearest-source questions would run one BFS per source (k × the work), and "all at the same time" spreading would be simulated minute by minute.

when · why · how

when: Several starting points spread at the same speed, or each cell needs its distance to the nearest of many targets.
why: All sources share one queue at distance 0, so the queue stays sorted by distance: O(V + E) total instead of O(k · (V + E)).
how: Before the loop, offer every source and mark it; then run the normal BFS, writing dist[next] = dist[cur] + 1 on first discovery.

since1916–1936

Bipartite check (two-colouring)

Dénes Kőnig

Dénes Kőnig, a Hungarian mathematician, studied graphs whose vertices split into two sides with every edge crossing between them. His 1916 paper in Mathematische Annalen proved a matching theorem for these bipartite graphs — an early result in what is now matching theory. His 1936 book Theorie der endlichen und unendlichen Graphen is described as the first textbook on graph theory. The check we code — colour with BFS and look for a clash — rests on the standard fact that a graph is bipartite exactly when it has no odd cycle.

the problem it solvedMatching two groups — workers to jobs, students to slots — where every link joins one side to the other.

its jobs today

Two-slot scheduling: can these exams be split into two sessions so no student has a clash?
Matching and assignment: users ↔ items, drivers ↔ riders, jobs ↔ machines are bipartite graphs.
Spotting odd cycles — a quick structural test before heavier algorithms.

the weight it carries

Illustrative: 10⁴ students and 5 × 10⁴ "can't share a slot" pairs. Two-colouring checks it in V + 2E = 10⁴ + 10⁵ = 1.1 × 10⁵ steps. Trying every split into two groups means 2^(10⁴) options — impossible.

without it

"Can it be split in two?" would be a search over exponentially many splits.

when · why · how

when: "Split into two groups", "no two neighbours share a colour", "possible bipartition".
why: The colouring is forced: once a vertex has a colour, all its neighbours must get the other. One BFS/DFS per component decides it in O(V + E).
how: int[] color with 0 = unpainted and ±1 for the sides; paint a neighbour -color[u]; same colour → false. Start from every unpainted vertex.

since?

Directed cycle detection (three colours)

No single inventor for the white/gray/black DFS convention. The same three colours mark reachable objects in Dijkstra and colleagues' 1978 paper "On-the-fly garbage collection".

its jobs today

Build tools and package managers refuse circular dependencies.
Spreadsheets report a circular reference when a formula depends on itself through other cells.
Deadlock checks: a cycle in a "who waits for whom" graph means nobody can move.

the weight it carries

Illustrative: an Excel sheet with 10⁵ formula cells and 3 × 10⁵ references. One coloured DFS finds or rules out a circular reference in 10⁵ + 3 × 10⁵ = 4 × 10⁵ steps.

without it

A plain visited array reports false cycles on harmless diamonds — so builds would fail for no reason, or real cycles would loop forever.

when · why · how

when: Directed dependencies: prerequisites, imports, formulas — "is it even possible?"
why: Gray marks vertices on the current path; only an edge into gray closes a loop. O(V + E) time, O(V) colours plus recursion depth.
how: int[] color with WHITE = 0, GRAY = 1, BLACK = 2: gray on entry, black on exit, and return true when a neighbour is gray.

since1877–1879

BFS on an implicit graph

Lewis Carroll (Charles Dodgson); later Donald Knuth

Around Christmas 1877, Lewis Carroll invented a word game he first called "Word-Links". Vanity Fair printed his puzzles as "Doublets" in 1879: turn HEAD into TAIL one letter at a time — HEAD, heal, teal, tell, tall, TAIL. Nobody lists the edges: a word's neighbours are the real words one letter away. Donald Knuth's Stanford GraphBase later shipped 5,757 five-letter words that form exactly this kind of graph, to test graph algorithms on.

the problem it solvedFinding the shortest chain between two states when the connections are a rule ("change one letter"), not a list.

its jobs today

Puzzle and game solvers: board positions are vertices, legal moves are edges, BFS gives the fewest moves.
Board games on a grid: dice rolls (Snakes and Ladders) or knight jumps generate the neighbours on the fly.
Search over configurations — lock combinations, gene strings, word chains — without ever building the graph.

the weight it carries

Knuth's 5,757 five-letter words form a graph with 14,135 one-letter-apart edges. Comparing every pair: 5,757 × 5,756 / 2 = 16,568,646 checks. Generating neighbours: 5,757 × 5 × 25 = 719,625 HashSet lookups — about 23× fewer.

without it

You would build the whole graph first (often impossible: the board in Minimum Knight Moves is infinite) or compare every pair of states.

when · why · how

when: A puzzle has states and equal-cost moves between them: "minimum number of mutations / rolls / moves".
why: Same O(V + E) BFS, but V and E are only the states you actually reach; the cost per state is the cost of generating its moves.
how: A HashSet of allowed or unvisited states, an ArrayDeque queue, and a loop that builds each neighbour (change a char, add a roll, add a jump).

02 · plain english

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.

03 · remember

What you must know

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.
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.
BFS = queue. DFS = stack (or recursion, which uses the call stack). Same skeleton, different container — that's the whole difference.
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.
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).
Both traversals are O(V + E): each vertex is processed once and each edge is looked at once (twice if undirected).
A grid is a graph: each cell is a vertex, its 4 (or 8) neighbours are edges. Check bounds first, then walls, then visited.
Loop over every vertex as a possible start to cover disconnected graphs — that same loop counts connected components.
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".
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.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

BFS ring by ring

Watch the queue: nodes leave from the front in order of distance, so dist[] fills in rings 0, 1, 2…

loading simulation…

javajava.util.*

1class Bfs {2    /** Fewest edges from source to every vertex; -1 means unreachable. */3    static int[] distances(List<List<Integer>> adj, int source) {4        int[] dist = new int[adj.size()];5        Arrays.fill(dist, -1);6        Deque<Integer> queue = new ArrayDeque<>();7        dist[source] = 0;8        queue.offer(source);9        while (!queue.isEmpty()) {10            int u = queue.poll();11            for (int v : adj.get(u)) {12                if (dist[v] == -1) {13                    dist[v] = dist[u] + 1;14                    queue.offer(v);15                }16            }17        }18        return dist;19    }20}

sim

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.

loading simulation…

javajava.util.*

1class DfsIterative {2    static List<Integer> order(List<List<Integer>> adj, int source) {3        List<Integer> out = new ArrayList<>();4        boolean[] visited = new boolean[adj.size()];5        Deque<Integer> stack = new ArrayDeque<>();6        stack.push(source);7        while (!stack.isEmpty()) {8            int u = stack.pop();9            if (visited[u]) continue;10            visited[u] = true;11            out.add(u);12            List<Integer> nbrs = adj.get(u);13            for (int i = nbrs.size() - 1; i >= 0; i--) // push in reverse → same order as recursion14                if (!visited[nbrs.get(i)]) stack.push(nbrs.get(i));15        }16        return out;17    }18}

sim

Grid flood fill — Number of Islands

Each new piece of land starts a DFS that sinks the whole island, so it's counted exactly once.

loading simulation…

javajava.util.*

1class Solution {2    public int numIslands(char[][] grid) {3        int islands = 0;4        for (int r = 0; r < grid.length; r++)5            for (int c = 0; c < grid[0].length; c++)6                if (grid[r][c] == '1') {7                    islands++;8                    sink(grid, r, c);9                }10        return islands;11    }12 13    /** Turns the whole island containing (r, c) into water so it is never counted again. */14    private void sink(char[][] grid, int r, int c) {15        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1') return;16        grid[r][c] = '0';17        sink(grid, r + 1, c);18        sink(grid, r - 1, c);19        sink(grid, r, c + 1);20        sink(grid, r, c - 1);21    }22}

sim

Multi-source BFS — Rotting Oranges

All rotten oranges start in the queue together. One BFS level = one minute.

loading simulation…

javajava.util.*

1class Solution {2    public int orangesRotting(int[][] grid) {3        int rows = grid.length, cols = grid[0].length, fresh = 0;4        Deque<int[]> queue = new ArrayDeque<>();5        for (int r = 0; r < rows; r++)6            for (int c = 0; c < cols; c++) {7                if (grid[r][c] == 2) queue.offer(new int[] {r, c});8                else if (grid[r][c] == 1) fresh++;9            }10        int minutes = 0;11        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};12        while (!queue.isEmpty() && fresh > 0) {13            minutes++;14            for (int size = queue.size(); size > 0; size--) { // exactly one BFS level = one minute15                int[] cell = queue.poll();16                for (int[] d : dirs) {17                    int nr = cell[0] + d[0], nc = cell[1] + d[1];18                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || grid[nr][nc] != 1) continue;19                    grid[nr][nc] = 2;20                    fresh--;21                    queue.offer(new int[] {nr, nc});22                }23            }24        }25        return fresh == 0 ? minutes : -1;26    }27}

sim

Two-colouring — is the graph bipartite?

Neighbours get opposite colours. The square passes; the triangle (an odd cycle) can't be coloured.

loading simulation…

javajava.util.*

1class Solution {2    public boolean isBipartite(int[][] graph) {3        int n = graph.length;4        int[] color = new int[n];5        for (int start = 0; start < n; start++) { // the graph may be disconnected6            if (color[start] != 0) continue;7            color[start] = 1;8            Deque<Integer> queue = new ArrayDeque<>();9            queue.offer(start);10            while (!queue.isEmpty()) {11                int u = queue.poll();12                for (int v : graph[u]) {13                    if (color[v] == 0) {14                        color[v] = -color[u];15                        queue.offer(v);16                    } else if (color[v] == color[u]) return false;17                }18            }19        }20        return true;21    }22}

sim

Directed cycle detection with three colours

Gray = on the current path. An edge into a gray node loops back to an ancestor: a cycle.

loading simulation…

javajava.util.*

1class DirectedCycle {2    static final int WHITE = 0, GRAY = 1, BLACK = 2; // unseen · on the current path · finished3 4    static boolean hasCycle(int n, int[][] edges) {5        List<List<Integer>> adj = new ArrayList<>();6        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());7        for (int[] e : edges) adj.get(e[0]).add(e[1]);8        int[] color = new int[n];9        for (int s = 0; s < n; s++)10            if (color[s] == WHITE && dfs(adj, s, color)) return true;11        return false;12    }13 14    private static boolean dfs(List<List<Integer>> adj, int u, int[] color) {15        color[u] = GRAY;16        for (int v : adj.get(u)) {17            if (color[v] == GRAY) return true;18            if (color[v] == WHITE && dfs(adj, v, color)) return true;19        }20        color[u] = BLACK;21        return false;22    }23}

sim

Implicit graph — BFS over words

Nobody gives you edges: each word's neighbours are made by changing one letter and checking a HashSet. Columns are BFS levels.

loading simulation…

javajava.util.*

1class Solution {2    /** Don't build the graph: generate neighbours by trying all 26 letters at each position. */3    public int ladderLength(String beginWord, String endWord, List<String> wordList) {4        Set<String> unvisited = new HashSet<>(wordList);5        if (!unvisited.contains(endWord)) return 0;6        Deque<String> queue = new ArrayDeque<>(List.of(beginWord));7        unvisited.remove(beginWord);8        for (int length = 1; !queue.isEmpty(); length++) {9            for (int size = queue.size(); size > 0; size--) { // one level = one more word10                char[] w = queue.poll().toCharArray();11                for (int i = 0; i < w.length; i++) {12                    char original = w[i];13                    for (char ch = 'a'; ch <= 'z'; ch++) {14                        if (ch == original) continue;15                        w[i] = ch;16                        String next = new String(w);17                        if (!unvisited.contains(next)) continue;18                        if (next.equals(endWord)) return length + 1;19                        unvisited.remove(next); // removing = marking visited20                        queue.offer(next);21                    }22                    w[i] = original; // undo before trying the next position23                }24            }25        }26        return 0;27    }28}

05 · cost

Time & space, explained

Graph representations (V vertices, E edges)
	Adjacency list	Adjacency matrix	Edge list	why
Memory	O(V + E)	O(V²)	O(E)	A list stores only the edges that exist; a matrix reserves a slot for every possible pair.
Is there an edge u–v?	O(deg u)	O(1)	O(E)	The matrix is a direct lookup `m[u][v]`; a list must scan u's neighbours.
Visit all neighbours of u	O(deg u)	O(V)	O(E)	A matrix row has V slots even if u has only 2 neighbours.
Add an edge	O(1) amortized	O(1)	O(1) amortized	`ArrayList.add` is amortized O(1); a matrix write is a single assignment.
Full BFS / DFS	O(V + E)	O(V²)	O(V · E)	Traversal visits every vertex's neighbours once — cost depends on how fast neighbours can be listed.

Traversals and what they cost
	Time	Extra space	why
BFS (queue)	O(V + E)	O(V)	Each vertex is enqueued once; each adjacency list is scanned once. visited/dist + queue hold ≤ V items.
DFS (recursive)	O(V + E)	O(V)	Same work as BFS. The call stack can be V deep on a long path graph.
DFS (explicit stack)	O(V + E)	O(V + E)	A vertex can be pushed once per incoming edge before it's visited, so the stack can hold up to E entries.
Connected components	O(V + E)	O(V)	One outer loop over V; every inner traversal touches each vertex/edge only once in total.
Grid BFS / DFS (R × C)	O(R · C)	O(R · C)	V = R·C cells and E ≤ 4·R·C, so O(V + E) = O(R·C). Visited marks or recursion can cover the whole grid.
Cycle check / bipartite check	O(V + E)	O(V)	They are a single DFS/BFS with a colour array instead of a boolean array.
Multi-source BFS (k sources)	O(V + E)	O(V)	All k sources start in one queue and every vertex still enters it once. k separate BFS runs would cost O(k · (V + E)).
Implicit-graph BFS (N words of length L)	O(N · L² · 26)	O(N · L)	Each word is expanded once: L positions × 26 letters, and each candidate costs O(L) to build and hash.

06 · java

Raw vs Collections Framework

Building a graph: arrays & matrix vs Map of lists

javamatrix + List<List<Integer>>java.util.*

1class RawGraph {2    /** Undirected graph as an n×n matrix: m[u][v] == 1 means "u and v are connected". */3    static int[][] matrix(int n, int[][] edges) {4        int[][] m = new int[n][n];5        for (int[] e : edges) {6            m[e[0]][e[1]] = 1;7            m[e[1]][e[0]] = 1; // undirected: store both directions8        }9        return m;10    }11 12    /** The same graph as an adjacency list: one list of neighbours per vertex. */13    static List<List<Integer>> list(int n, int[][] edges) {14        List<List<Integer>> adj = new ArrayList<>();15        for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); // every vertex, even isolated ones16        for (int[] e : edges) {17            adj.get(e[0]).add(e[1]);18            adj.get(e[1]).add(e[0]);19        }20        return adj;21    }22}

javaMap + computeIfAbsent, weighted pairsjava.util.*

1class MapGraph {2    /** Vertices are labels (names, big ids), edges are directed: use a Map of lists. */3    static Map<String, List<String>> directed(String[][] edges) {4        Map<String, List<String>> adj = new HashMap<>();5        for (String[] e : edges) {6            adj.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);7            adj.computeIfAbsent(e[1], k -> new ArrayList<>()); // sinks still get an entry8        }9        return adj;10    }11 12    /** Weighted edges: store {neighbour, weight} pairs. */13    static List<List<int[]>> weighted(int n, int[][] edges) {14        List<List<int[]>> adj = new ArrayList<>();15        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());16        for (int[] e : edges) adj.get(e[0]).add(new int[] {e[1], e[2]});17        return adj;18    }19}

Vertices are 0..n−1 (most LeetCode problems)? Use List<List<Integer>> — fast and simple.
Vertices are strings or huge ids? Use Map<K, List<K>> with computeIfAbsent(k, x -> new ArrayList<>()).
Undirected edge = add it twice (u→v and v→u). Forgetting one direction is the #1 graph bug.
Weighted edges: store int[]{neighbour, weight} pairs — you'll need this for Dijkstra next chapter.
Create a list for every vertex first, or isolated vertices crash with IndexOutOfBoundsException.

BFS with ArrayDeque

javaBFS distancesjava.util.*

1class Bfs {2    /** Fewest edges from source to every vertex; -1 means unreachable. */3    static int[] distances(List<List<Integer>> adj, int source) {4        int[] dist = new int[adj.size()];5        Arrays.fill(dist, -1);6        Deque<Integer> queue = new ArrayDeque<>();7        dist[source] = 0;8        queue.offer(source);9        while (!queue.isEmpty()) {10            int u = queue.poll();11            for (int v : adj.get(u)) {12                if (dist[v] == -1) {13                    dist[v] = dist[u] + 1;14                    queue.offer(v);15                }16            }17        }18        return dist;19    }20}

ArrayDeque is the right queue: offer adds at the rear, poll removes from the front, both O(1). Avoid LinkedList (slower) and never use Stack.
dist[v] == -1 doubles as the visited check, and gives you the answer for free.
BFS never revisits: the first time a vertex is discovered is via a shortest path.

DFS: recursion vs an explicit stack

javarecursivejava.util.*

1class DfsRecursive {2    static List<Integer> order(List<List<Integer>> adj, int source) {3        List<Integer> out = new ArrayList<>();4        dfs(adj, source, new boolean[adj.size()], out);5        return out;6    }7 8    private static void dfs(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> out) {9        visited[u] = true; // mark BEFORE going deeper, or a cycle loops forever10        out.add(u);11        for (int v : adj.get(u))12            if (!visited[v]) dfs(adj, v, visited, out);13    }14}

javaArrayDeque as a stackjava.util.*

1class DfsIterative {2    static List<Integer> order(List<List<Integer>> adj, int source) {3        List<Integer> out = new ArrayList<>();4        boolean[] visited = new boolean[adj.size()];5        Deque<Integer> stack = new ArrayDeque<>();6        stack.push(source);7        while (!stack.isEmpty()) {8            int u = stack.pop();9            if (visited[u]) continue;10            visited[u] = true;11            out.add(u);12            List<Integer> nbrs = adj.get(u);13            for (int i = nbrs.size() - 1; i >= 0; i--) // push in reverse → same order as recursion14                if (!visited[nbrs.get(i)]) stack.push(nbrs.get(i));15        }16        return out;17    }18}

Recursive DFS is shortest to write. Default Java thread stacks handle depths of roughly 10⁴ frames — risky on a 300×300 all-land grid (9·10⁴ deep).
Iterative DFS uses push/pop on an ArrayDeque and never overflows. Push neighbours in reverse to match the recursive order.
In iterative DFS, check visited when you pop — a vertex may have been pushed twice by different neighbours.

Connected components & grids as graphs

javacount componentsjava.util.*

1class Components {2    /** Number of connected pieces in an undirected graph with vertices 0..n-1. */3    static int count(int n, int[][] edges) {4        List<List<Integer>> adj = new ArrayList<>();5        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());6        for (int[] e : edges) {7            adj.get(e[0]).add(e[1]);8            adj.get(e[1]).add(e[0]);9        }10        boolean[] visited = new boolean[n];11        int components = 0;12        for (int s = 0; s < n; s++) {13            if (visited[s]) continue;14            components++; // s was not reached before → it starts a new component15            Deque<Integer> queue = new ArrayDeque<>();16            queue.offer(s);17            visited[s] = true; // mark when ENQUEUED, not when polled18            while (!queue.isEmpty()) {19                int u = queue.poll();20                for (int v : adj.get(u))21                    if (!visited[v]) {22                        visited[v] = true;23                        queue.offer(v);24                    }25            }26        }27        return components;28    }29}

javagrid BFS with a DIRS arrayjava.util.*

1class GridBfs {2    static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // down, up, right, left3 4    /** Fewest 4-directional steps from (0,0) to the bottom-right through 0-cells; -1 if blocked. */5    static int steps(int[][] grid) {6        int rows = grid.length, cols = grid[0].length;7        if (grid[0][0] != 0) return -1;8        int[][] dist = new int[rows][cols];9        for (int[] row : dist) Arrays.fill(row, -1);10        Deque<int[]> queue = new ArrayDeque<>();11        queue.offer(new int[] {0, 0});12        dist[0][0] = 0;13        while (!queue.isEmpty()) {14            int[] cell = queue.poll();15            int r = cell[0], c = cell[1];16            for (int[] d : DIRS) {17                int nr = r + d[0], nc = c + d[1];18                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue; // off the board19                if (grid[nr][nc] != 0 || dist[nr][nc] != -1) continue;    // wall or seen20                dist[nr][nc] = dist[r][c] + 1;21                queue.offer(new int[] {nr, nc});22            }23        }24        return dist[rows - 1][cols - 1];25    }26}

The outer for (s = 0; s < n; s++) loop is what makes your code correct for disconnected graphs.
Grids: keep a DIRS = {{1,0},{-1,0},{0,1},{0,-1}} array. Check bounds first, then walls, then visited.
Encode a cell as one int with r * cols + c when you need it as a map key or a union-find id.

Cycle detection: undirected vs directed

javaundirected: skip the parentjava.util.*

1class UndirectedCycle {2    static boolean hasCycle(int n, int[][] edges) {3        List<List<Integer>> adj = new ArrayList<>();4        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());5        for (int[] e : edges) {6            adj.get(e[0]).add(e[1]);7            adj.get(e[1]).add(e[0]);8        }9        boolean[] visited = new boolean[n];10        for (int s = 0; s < n; s++) // every component, not just the one containing 011            if (!visited[s] && dfs(adj, s, -1, visited)) return true;12        return false;13    }14 15    private static boolean dfs(List<List<Integer>> adj, int u, int parent, boolean[] visited) {16        visited[u] = true;17        for (int v : adj.get(u)) {18            if (v == parent) continue;   // the edge we arrived on is not a cycle19            if (visited[v]) return true; // reached an old vertex another way → cycle20            if (dfs(adj, v, u, visited)) return true;21        }22        return false;23    }24}

javadirected: white / gray / blackjava.util.*

1class DirectedCycle {2    static final int WHITE = 0, GRAY = 1, BLACK = 2; // unseen · on the current path · finished3 4    static boolean hasCycle(int n, int[][] edges) {5        List<List<Integer>> adj = new ArrayList<>();6        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());7        for (int[] e : edges) adj.get(e[0]).add(e[1]);8        int[] color = new int[n];9        for (int s = 0; s < n; s++)10            if (color[s] == WHITE && dfs(adj, s, color)) return true;11        return false;12    }13 14    private static boolean dfs(List<List<Integer>> adj, int u, int[] color) {15        color[u] = GRAY;16        for (int v : adj.get(u)) {17            if (color[v] == GRAY) return true;18            if (color[v] == WHITE && dfs(adj, v, color)) return true;19        }20        color[u] = BLACK;21        return false;22    }23}

Undirected: seeing a visited vertex that isn't the one you came from means a cycle.
Directed: only an edge to a gray vertex (still on the current path) is a cycle. A black vertex was finished earlier — a diamond like 0→1→3, 0→2→3 is not a cycle.
The parent trick assumes no parallel edges. With duplicate edges, skip the parent edge id, not the parent vertex.

Java API you will actually use
call	does	cost
`new ArrayDeque<>()`	Queue (offer/poll) or stack (push/pop) — the default for BFS and iterative DFS	O(1) per op (amortized)
`queue.offer(x) / queue.poll()`	Add at the rear / remove from the front (null if empty)	O(1)
`stack.push(x) / stack.pop()`	Add / remove at the head — LIFO	O(1)
`adj.get(u).add(v)`	Add an edge u→v to an adjacency list	O(1) amortized
`map.computeIfAbsent(k, x -> new ArrayList<>())`	Get k's list, creating it the first time	O(1) average
`Arrays.fill(dist, -1)`	Mark every vertex "unvisited"	O(V)
`new boolean[n] / new boolean[rows][cols]`	Visited flags, all false by default	O(V)
`set.add(x)`	Adds and returns false if already present — a visited check in one call	O(1) average

Fewest steps / edges in an unweighted graph or grid

→ BFS with a queue

Explores by distance, so the first arrival is the shortest.

Explore / count / mark everything connected

→ DFS (recursive) or BFS

Both are O(V + E). DFS is less code; pick BFS if depth could overflow the stack.

Very deep graphs or big grids (≥ 10⁴ cells in a line)

→ BFS or iterative DFS

No recursion → no StackOverflowError.

Edges arrive over time; just need "same group?"

→ Union-Find (see its own chapter)

Near O(1) per union/find without rebuilding a graph.

Many sources spreading at once

→ Multi-source BFS (seed the queue with all sources)

One BFS instead of one per source: O(V + E) total.

Edges have weights

→ Dijkstra / 0-1 BFS (Shortest Paths chapter)

Plain BFS counts edges, not cost.

07 · recognise

Spot the pattern

"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

"Split into two groups", "no two neighbours share a colour"

Bipartite check with 2-colouring

Region that is "surrounded", "can reach the border", "flows to the ocean"

Reverse it: start from the border/ocean and mark what's reachable

"Deep copy" a graph with cycles

HashMap original → clone + DFS/BFS

Dependencies / prerequisites — "is it possible?"

Directed cycle detection (colours) or topological sort (its own chapter)

"Fewest moves" in a puzzle: change one letter / gene, roll a die, move a knight

BFS on an implicit graph — states are vertices, legal moves are edges

"Largest / size of" a connected region

Flood fill that returns a count (1 + the neighbours' counts), keep the max

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

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.
Indexing grid[nr][nc] before checking 0 ≤ nr < rows and 0 ≤ nc < cols → ArrayIndexOutOfBoundsException.
Using DFS to find the shortest path in an unweighted graph. DFS finds a path, not the shortest one.
Adding an undirected edge only once (u→v but not v→u).
Directed cycle check with a plain visited array: it reports a cycle on a harmless diamond. You need three states.
Comparing Integer objects with == (e.g. adj.get(u).get(i) == target) — works below 128, breaks above. Use int variables or .equals.
Deep recursion on big grids → StackOverflowError. Switch to BFS or an explicit stack.

tricks

Say the template out loud: "queue, visited, while queue not empty: poll, for each neighbour, if not visited: mark, offer."
For level-by-level BFS (minutes, word-ladder steps), snapshot int size = queue.size() and process exactly that many.
Ask early: directed or undirected? Weighted? Connected? Can I modify the input? Max size (recursion depth)?
Modifying the grid in place ('1' → '0') is a neat visited trick — mention that it destroys the input and offer a boolean[][] instead.
Chalo, dry-run karte hain: draw 4–6 nodes on paper and run the queue by hand before you code. It catches most off-by-one and visited-mark bugs.
Many "hard" problems are BFS on an implicit graph — the vertices are states (words, lock combinations, board positions) and you generate neighbours on the fly.

09 · why & how

Questions you might be too shy to ask

What's the difference between a graph and a tree?

A tree is a connected graph with no cycles (exactly V − 1 edges). That's why tree traversals that walk down from the root through child pointers don't need a visited set — there's only one way to reach each node. General graphs can loop back, so they do. (A tree given as an undirected edge list still needs one check: don't walk back to the parent you came from.)

Adjacency list or matrix?

Default to a list: O(V + E) memory and fast neighbour iteration. Use a matrix when the graph is dense (E close to V²), when the input already is one (LC 547), or when you need O(1) "is there an edge?" checks.

The vertices are numbered 1 to n, not 0 to n − 1. What do I do?

Easiest: make every array one bigger — new boolean[n + 1], and n + 1 lists in adj — and simply never use index 0. Or subtract 1 from every label while reading the edges, and add 1 back if you print vertices. Pick one way and use it everywhere. Mixing the two is a classic off-by-one bug.

What does O(V + E) mean — why not O(V · E)?

Each vertex is processed once (V), and when it's processed we scan only its own neighbours. Added up over all vertices, those scans touch every edge once (twice if undirected): E. Work is V + E, not V times E.

How do I choose between BFS and DFS?

Need the shortest path or anything "by levels"? BFS. Just need to visit everything connected, detect cycles, or explore all paths? DFS is usually less code. When both work (counting islands), pick the one you write fastest without bugs.

Why does BFS find the shortest path?

The queue is always sorted by distance: everything at distance d leaves before anything at distance d+1 arrives at the front. So when a vertex is discovered for the first time, it's through the fewest edges possible — any shorter route would have discovered it earlier.

Why mark visited when I enqueue, not when I poll?

Between enqueue and poll, other vertices can see the same neighbour and enqueue it again. Marking at enqueue time guarantees each vertex enters the queue once, which is what makes BFS O(V + E).

Iterative DFS checks visited on pop, but BFS marks on push. Why the difference?

For "visit everything reachable" (count islands, components), marking on push works for a stack too, and is O(V + E). But then the visiting order is no longer the true DFS order a recursive call would give. When you want that exact order, mark on pop, as this chapter's DfsIterative does. For cycle colours or finish times, recursion is the simplest choice. BFS has no such issue: queue order already is distance order, so mark on push.

BFS gave me the shortest length. How do I get the actual path?

Remember who discovered each vertex: when you first enqueue v from u, store parent[v] = u. After BFS, start at the target and follow parent back to the source, then reverse the list. Example: parent says 4 ← 2 ← 0, so the path is 0 → 2 → 4. Extra cost is only O(V).

Will recursive DFS crash on big inputs?

It can. Each call uses a stack frame, and with default JVM settings the stack often holds only around 10⁴ of them — the exact number depends on the JVM, its settings and the frame size. A 300×300 grid of land could need 90 000 frames. In an interview, mention it and offer BFS or an explicit stack as the safe version.

How is a grid a graph if nobody gave me edges?

The edges are implied: cell (r, c) connects to (r±1, c) and (r, c±1) when they're inside the grid and passable. You generate those neighbours on the fly with a direction array instead of storing them.

With 8 directions, a diagonal step is longer. Does BFS still give the shortest path?

Yes, because the problem counts moves, not straight-line distance. A diagonal move costs 1, the same as a straight one. So every edge still has the same cost, and BFS is correct — just use an 8-entry DIRS array. If moves had different costs, you'd need Dijkstra (next chapter).

How can one BFS handle many starting points at once?

Put all of them in the queue at distance 0 before the loop. It's the same as one BFS from an invisible super-source wired to every real source, so the first time BFS reaches a cell, that's its distance to the nearest source.

The puzzle never mentions a graph. How do I know it's BFS?

Ask: is there a state (a word, a board square, a knight position) and a move that turns one state into another, all moves costing the same? Then states are vertices, moves are edges, and "fewest moves" is BFS. Generate the neighbours inside the loop instead of building the graph.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#200
Number of Islandsmust-do
MediumByteDance / TikTokWalmartSamsungUberAmazon+1
#733
Flood Fill
EasyAmazonMicrosoftGoogle
#695
Max Area of Islandmust-do
MediumIntuitMetaAmazonGoogleBloomberg+1
#133
Clone Graphmust-do
MediumMetaGoogleAmazonBloombergMicrosoft
#994
Rotting Orangesmust-do
MediumFlipkartAmazonSamsungWalmartInfosys+1
#542
01 Matrixmust-do
MediumFlipkartAmazonGoogleMicrosoftMeta
#286
Walls and GatesLeetCode Premium
MediumMetaGoogleAmazonMicrosoft
#417
Pacific Atlantic Water Flow
MediumAmazonGoogle
#130
Surrounded Regions
MediumGoogleBloombergUberByteDance / TikTok
#785
Is Graph Bipartite?must-do
MediumSamsungMetaGoogle
#1091
Shortest Path in Binary Matrixmust-do
MediumMetaAmazonGoogleMicrosoft
#1730
Shortest Path to Get FoodLeetCode Premium
MediumBloomberg
#909
Snakes and Ladders
MediumAmazonGoogleMicrosoftBloombergMeta
#1197
Minimum Knight MovesLeetCode Premium
MediumLinkedInMetaGoogleMicrosoftAmazon
#433
Minimum Genetic Mutation
MediumAmazonGoogleBloombergMicrosoft
#127
Word Laddermust-do
HardLinkedInAmazonByteDance / TikTokAppleMeta+1

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#547
Number of Provinces
Mediumin Union-Find & MST
Connected components on an adjacency matrix: count how many times you must start a new DFS/BFS.
#207
Course Schedule
Mediumin Topo Sort
Directed cycle detection in action: can every course be finished? Three-colour DFS or Kahn's algorithm.
#79
Word Search
Mediumin Backtracking
Grid DFS again, but cells are un-marked on the way back, because each path may reuse them.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
A graph = vertices + edges. Store it as an adjacency list List<List<Integer>>: O(V + E) memory. Grids and puzzles are graphs too.
use it when
Fewest steps with equal-cost moves → BFS. Count or mark everything connected → DFS or BFS. Many sources spreading at once → multi-source BFS.
template
BFS: offer(s); seen[s] = true; while the queue isn't empty: u = poll(); for each neighbour v not seen → mark it, offer(v).
cost
BFS and DFS: O(V + E) time, O(V) extra space. A grid is O(rows × cols). Bipartite and cycle checks cost the same.
trap
Mark visited when you enqueue, not when you poll — or the same vertex is queued many times.
trap
Recursive DFS on a big grid can go rows × cols deep → StackOverflowError. Use BFS or an ArrayDeque stack.
trap
Check bounds before grid[nr][nc], and loop over every vertex as a start, or disconnected parts are silently skipped.
trap
Directed cycle check needs 3 colours: only an edge into a gray (on-path) vertex is a cycle. A diamond is not.
pro tip
Seed the queue with every source (rotten oranges, gates, zeros): one BFS instead of one per source.
pro tip
"Fewest moves" puzzles (words, genes, dice boards, knights) are BFS on an implicit graph: states = vertices, moves = edges.

12 · recall

Flip, remember, repeat

card 1 / 14

recall

Why does BFS find the fewest-edges path in an unweighted graph?

tap or Space to flip ↻

Question 1: Why does BFS find the fewest-edges path in an unweighted graph?

13 · check yourself

Quick quiz

You need the minimum number of moves to reach a cell in an unweighted grid. Which traversal?
Graph: edges 0–1, 0–2, 1–3. BFS from 0 (neighbours in that order). In what order are vertices polled?
What is the time complexity of BFS on an adjacency list?
Why mark a vertex visited when it is enqueued rather than when it is polled?
Directed edges 0→1, 0→2, 1→3, 2→3. A DFS with a plain visited array reaches 3 twice. Is there a cycle?
Rotting Oranges has 3 rotten oranges. What's the best approach?
Which graph is NOT bipartite?
01 Matrix: you need every cell's distance to its nearest 0. Where does the BFS start?
Snakes and Ladders asks for the fewest dice rolls. In the BFS, what is a vertex?

0/0 correct · 9 left

14 · learn more