Graphs cheat sheet

The 22 Graphs interview answers in 30 seconds each, plus quick facts. Printable, free.

One page per topic: print it or save it as PDF from your browser's print menu. Practise these questions

Rules of thumb

Fewest steps in an unweighted graph or grid: BFS. Weighted with non-negative costs: Dijkstra.
Count or label connected pieces: DFS, BFS or union-find; all are O(V + E).
Tasks with 'must come before' rules: topological order with in-degrees (Kahn); leftover nodes mean a cycle.
Many starting points at once (spreading, nearest exit): put them all in the queue at distance 0.
Mark a node visited when you push it, not when you pop it, or BFS can queue it many times.

Count the separate patches of land on a map

Scan every cell. When you meet land you have not visited, count a new patch and flood it: walk all land reachable from it with a stack or queue, marking cells as seen. Each cell is visited a constant number of times, so it is O(R·C) time and O(R·C) space for the seen set.

Can every task finish, given its prerequisites?

Count, for each task, how many rules still block it (its in-degree). Start with the unblocked tasks; each time one finishes, unblock the tasks that waited on it. If every task finishes, the rules allow an order. If some never become unblocked, they sit on a cycle or wait on one. O(V + E) time and space.

Minutes until every item on a shelf spoils

Put every spoiled item in a queue at once (multi-source BFS). Process the queue one layer per minute, spoiling fresh neighbours and queueing them. Stop when nothing fresh remains; if fresh items are left when the queue empties, return -1. O(R·C) time and space.

How many separate groups does a network have?

Union-find: start with every computer in its own group, and for each link join the two groups if they differ, subtracting one from the count. With path compression and union by size, each operation is nearly O(1), so the whole thing is O(n + E·α(n)) time, with O(n) space for the two arrays.

Fewest hops between two stations

Breadth-first search from the start explores stations in order of hop count, so the first time it reaches the goal is via the fewest hops. Keep a distance per station and mark stations as you queue them. O(V + E) time and space.

Fastest delivery time to every depot

Dijkstra's algorithm: keep a min-heap of (time, depot). Pop the closest unsettled depot and try every road out of it; if that gives a faster time to a neighbour, record it and push it. Stale heap entries are skipped when popped. O((V + E) log V) time, O(V + E) space.

The earliest valid task order

Kahn's algorithm with a min-heap instead of a queue: among the tasks that are currently unblocked, always take the smallest number. That choice is safe because taking any other ready task first would make the order larger at this position. O((V + E) log V) time and O(V + E) space.

Seat guests at two tables with no feud at either

Colour the graph with two colours using BFS: give a starting guest table 0, their rivals table 1, and so on. If a feud ever links two guests with the same table, it is impossible. Repeat from every guest not yet seated, since the graph may have several parts. O(V + E) time and space.

Which cable closes a loop?

Lay the cables in list order with union-find. The first cable whose two ends are already connected closes the loop. Every other cable on that loop came earlier in the list (they had to, to connect its ends), so this one is also the last loop cable in the list. O(n·α(n)) time and O(n) space.

Area of the biggest patch of land

Same flood as counting patches, but count the cells each flood reaches and keep the largest. Each cell is visited once: O(R·C) time and space.

Repaint the connected region of a picture

This is flood fill. Remember the starting colour; if it already equals the new colour, return a copy unchanged. Otherwise walk from the start with a stack, repainting each matching pixel and pushing its neighbours. Each pixel is repainted once: O(R·C) time and space (the copy).

Fewest one-letter changes between two code words

Treat each word as a node and connect words that differ in one letter. BFS from the start gives the shortest chain. To find neighbours quickly, try every position and every letter: 26·L candidates per word of length L, each checked against a set. With N words that is O(N·26·L²) once string building is counted, and the set and queue take O(N·L) space.

Does a dependency graph contain a loop?

Depth-first search with three states: not visited, in progress (on the current path), done. Reaching an in-progress package means the path loops back. Use an explicit stack so long dependency chains do not hit the recursion limit. O(V + E) time and space.

Cheapest way to cable every office together

Kruskal's algorithm: sort cables by cost and take each one that joins two offices not yet connected (union-find tells you). Stop after n - 1 cables. The result is a minimum spanning tree. O(E log E) for the sort, and O(V + E) space for the sorted cables and the union-find array.

Cells whose rain reaches both coasts

Reverse the flow. Start a BFS from every cell on the west edges and climb to neighbours of equal or greater height; that marks every cell that drains west. Do the same from the east edges. The answer is the cells in both sets. O(R·C) time and space.

Fill in the water that does not touch the edge

Flip the question: find the water that does touch the edge. Search from every edge water cell and mark what it reaches. Everything else that is water must be enclosed, so turn it into land. O(R·C) time and space.

Adjacency list, adjacency matrix or edge list?

An adjacency list (a list or dict of neighbour lists) uses O(V + E) memory and lists a node's neighbours in time proportional to its degree, so it suits most sparse graphs. An adjacency matrix uses O(V²) memory but answers 'is there an edge?' in O(1). An edge list is just the input pairs, ideal for Kruskal or union-find.

BFS or DFS: which one to use

Both visit every reachable node in O(V + E). BFS explores in layers with a queue, so it finds the fewest edges to any node and suits 'shortest' and 'nearest' questions. DFS goes deep with a stack (or recursion), which suits connectivity, cycle detection, topological order and backtracking. Memory differs: BFS holds a whole layer, DFS holds one path.

Mark visited when you push or when you pop?

Mark on push for BFS. If you mark on pop, a node can be added to the queue once per neighbour before it is ever popped, so the queue can grow to O(E) entries and do repeated work. Marking on push guarantees each node enters the queue once. Dijkstra is the exception: it settles nodes on pop and skips stale entries instead.

Why Dijkstra fails with negative weights

Dijkstra settles the closest unsettled node and never revisits it, assuming no later route can be cheaper. A negative edge breaks that: a longer-looking route can drop below a settled distance after the fact. Bellman-Ford relaxes every edge V - 1 times in O(V·E), handles negative weights and detects negative cycles.

Union-find: how it works and when to reach for it

Union-find tracks which items are in the same group. Each item points to a parent; the root names the group. find follows parents to the root, and union points one root at the other. Path compression flattens the paths it walks, and union by size hangs the smaller tree under the larger one. Together they make each operation nearly O(1).

Grids are graphs: neighbours, bounds and costs

Each cell is a node and its neighbours are the cells up, down, left and right (sometimes diagonals too). You never build an adjacency list; you compute neighbours from coordinates and check bounds. With R rows and C columns there are R·C nodes and at most 4·R·C edges, so BFS and DFS are O(R·C).

Quick facts

Adjacency list size: An adjacency list stores V lists holding E entries in total (2E for undirected graphs): O(V + E) memory, against O(V²) for a matrix.
heapq is a min-heap: heapq.heappush and heappop keep the smallest item at index 0; push (distance, node) tuples for Dijkstra.
Kotlin PriorityQueue: java.util.PriorityQueue with compareBy { it.first } gives a min-heap of pairs for Dijkstra in Kotlin.
Dijkstra cost: Dijkstra with a binary heap runs in O((V + E) log V) and requires non-negative edge weights.
Union-find cost: With path compression and union by size, a sequence of m union-find operations costs O(m α(n)), where α grows so slowly it is below 5 for any practical n.