Graph

Half the difficulty in graph problems is noticing that you have one. Very few of them arrive labelled: they arrive as a grid, a list of course prerequisites, a set of email accounts, or a dictionary of words. Once the model is clear the algorithm is almost always standard — and it is usually one you already know from DFS or BFS.

So this article is mostly about the part before the algorithm, plus the three techniques that are specific to graphs rather than to traversal: topological order, union-find, and the shortest-path ladder.

Modelling#

Two questions, always in this order:

1. What is a node? Usually a thing you can be “at”: a cell, a course, an account, a word, a state of a puzzle.
2. What is an edge? A single legal move between two of them, and — critically — what it costs.

Then four properties decide which algorithms are even available:

• Directed or undirected? Prerequisites point one way; friendships point both. In an undirected graph built from an edge list you must add both directions, and forgetting one is the single most common graph bug there is.
• Weighted or unweighted? If every edge costs the same, BFS gives shortest paths for free. If not, you need a heap.
• Cyclic or acyclic? Cycles are why traversals need a visited set, and detecting them is itself a common question.
• Connected? Most problems do not promise it. One traversal reaches one component, so anything asking about the whole graph needs an outer loop over every node.

Three worked examples of the modelling step, which is most of the work:

• Number of Islands. Node = a land cell. Edge = “orthogonally adjacent, also land”. No graph is ever built; the neighbours are computed from the coordinates. The question — how many components — is then routine.
• Course Schedule. Node = a course. Edge = “must be taken before”. The question “can I finish everything” is exactly “is this directed graph acyclic”.
• Accounts Merge. Node = an email. Edge = “appeared in the same account”. Two accounts belong to the same person when their emails are connected, so the question is again components — of a graph that the input never mentions.

If you can state the node and the edge in one sentence each, the rest of the problem is usually a template you have already written.

Building the graph#

Most inputs arrive as an edge list and every algorithm wants an adjacency list, so these five lines are worth being able to write without thinking:

adj = map from node to empty list

for (u, v) in edges:
    adj[u].append(v)
    adj[v].append(u)      // undirected only — omit for a directed graph

The adjacency list is the default and is what all the snippets here use: O(V + E) memory, and iterating a node’s neighbours costs only as many steps as it has. An adjacency matrix — a V×V grid of booleans or weights — is worth it only when the graph is dense or when you need to answer “is there an edge between exactly these two” in O(1); it costs O(V²) memory regardless of how few edges there are. An edge list stays useful when the algorithm sorts edges rather than walking them, which is what Kruskal does.

And the fourth representation is no representation at all. Grids and state-space puzzles have implicit edges: you generate the neighbours on demand and never store anything. That is usually a feature, not a compromise.

Traversal#

Covered properly in their own articles — DFS for reachability, connectivity, and anything aggregating over a subtree, BFS when the answer is a distance — so only the graph-specific reminders here:

• Keep a visited set and mark on arrival (DFS) or on enqueue (BFS). Without it a single cycle loops forever.
• Loop over all nodes to start fresh traversals, or you only ever see one component. Counting the number of times that outer loop actually starts something is how you count components.
• Both cost O(V + E).

Clone Graph is a good test of whether the traversal is really understood: it is a plain walk, but you have to keep a map from original node to copy and consult it before recursing. That map is the visited set — it just happens to carry the copy as its value.

Topological order#

For a directed acyclic graph, a topological order is any sequence in which every edge points forward: everything comes after its prerequisites. There are two standard ways to get one, and both are worth recognising.

Kahn’s algorithm is BFS with a twist. Count each node’s incoming edges, seed a queue with everything at zero, and each time you release a node, decrement its successors — any that hit zero are now free to go. It is written out line by line in the topological sort snippet.

The cycle test falls out of it for nothing: if the order comes out shorter than the node count, the leftovers are in a cycle, because nothing in a cycle ever reaches an in-degree of zero. Course Schedule is that check and nothing else.

DFS post-order gets there differently: run a depth-first search, and push each node onto a list as its call finishes. A node finishes only after everything it points at has finished, so reversing that list gives a valid topological order. Detecting a cycle this way needs three states rather than two — unvisited, in progress, and finished — because an edge back into a node that is still in progress is a cycle, while an edge into a finished node is merely a diamond, and a plain visited set cannot tell them apart.

Minimum Height Trees uses a relative of Kahn’s on an undirected graph: repeatedly strip every leaf, layer by layer, and whatever survives at the centre — one node or two — is the answer. The peeling is the same mechanism, with degree 1 as the release condition instead of degree 0.

Union-find#

Traversal answers connectivity questions when you have the whole graph up front. Union-find — a disjoint set union, or DSU — answers them as edges arrive, which traversal cannot do without starting over.

The structure is one array. parent[i] points at another element, and a set is identified by its root, the element that points at itself. Two elements are in the same set when they walk up to the same root.

Watch the two writes the structure ever makes. A union repoints one root at another — exactly one cell changes, and a whole set has been merged. A find repoints everything it walked past straight at the root, so the next query is a single hop. Notice too what happens on the last step: both elements already share a root, which is a cycle, detected without any traversal at all.

parent[i] = i for all i          // everyone starts alone
size[i]   = 1

function find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])     // path compression, on the way back
    return parent[x]

function union(a, b):
    ra = find(a); rb = find(b)
    if ra == rb:  return false           // already together: a cycle

    if size[ra] < size[rb]:  swap ra, rb
    parent[rb] = ra                      // union by size: small hangs off large
    size[ra] += size[rb]
    return true

The two optimisations do different jobs and you want both. Union by size stops the tree growing tall in the first place; path compression flattens whatever height it did reach, the first time anyone asks. Together, operations cost an amortised inverse-Ackermann factor — under 5 for any input that fits in a computer, so “effectively constant” is a fair thing to say out loud. Either optimisation alone is much worse; neither is O(n) per operation. The union-find snippet builds the whole thing in Go.

Reach for it when:

• Edges arrive one at a time and connectivity is queried in between.
• You are grouping things by a “belongs with” relation — Accounts Merge is the canonical case, and the merge is one union per pair of emails in an account.
• You need to know whether an edge closes a cycle, which is the return false above and the heart of Kruskal’s MST.

It does have a real limitation: it tracks whether things are connected, never how. If the answer is a path or a distance, use a traversal.

Shortest paths#

One decision, four answers, and it is worth having them in order:

• Every edge costs the same → BFS, O(V + E).
• Non-negative weights, one source → Dijkstra, O(E log V).
• Negative weights allowed, one source → Bellman-Ford, O(V·E).
• Every pair of nodes, small graph → Floyd-Warshall, O(V³).

Dijkstra is BFS with the queue replaced by a min-heap, so the next node examined is the nearest rather than the oldest — which is why it breaks on negative edges, where a node’s distance can improve after it has already been settled. Bellman-Ford handles those by relaxing every edge V−1 times, and a V-th pass that still improves something proves a negative cycle.

None of these appear in Grind 75, but recognising which one a problem needs is a fair interview question in its own right, and the mistake to avoid is reaching for Dijkstra on an unweighted graph — BFS is simpler and strictly faster.

What goes wrong#

Nearly every graph bug is one of these, and none of them are algorithmic:

• Only one direction added for an undirected edge. The traversal quietly explores half the graph.
• Nodes numbered from 1, arrays sized n. Size them n + 1 or subtract one consistently.
• The graph is disconnected, and the solution starts a single traversal from node 0.
• Duplicate edges or self-loops in the input. A visited set absorbs both; an in-degree count does not, so Kahn’s algorithm can stall on a duplicate.
• Isolated nodes. A node with no edges appears nowhere in the edge list, so an adjacency list built only from edges will not contain it at all.

The cheap insurance is to state the graph’s four properties before writing anything, and to build the adjacency list over the node count rather than over the edges.

Recognising it#

You are looking at a graph problem when:

• The input describes relationships between pairs — edges, prerequisites, friendships, shared attributes — even if the word “graph” never appears.
• The input is a grid and the question is about regions, reachability, or spreading.
• The question is about components, cycles, ordering under constraints, or connectivity.
• You are moving between states by legal moves, and want to know if a state is reachable or how far away it is.

Then pick by what is being asked: reachable → DFS, how far → BFS, valid order → topological sort, are these together → union-find, cheapest under weights → Dijkstra.

Summary#

Name the node and name the edge; almost everything else is a template. Settle four properties — directed, weighted, cyclic, connected — because each one rules algorithms in or out. Then the choice is small: traversal for reachability and distance, topological order for constraints and directed-cycle detection, union-find for connectivity that arrives incrementally, and the heap-based variants when edges stop costing the same. The algorithms are the easy half.