Graph representation choices — every question, written out
Adjacency list versus matrix versus edge list, judged by the operation you perform most.
Why is the adjacency list the default representation for most real graphs?
Trade-off & selection
Real graphs are sparse, and it costs O(V + E) while making neighbour iteration cost degree
Road networks, social graphs and dependency graphs all have E close to V rather than V², so paying per edge instead of per pair is an enormous saving. The operation traversals perform most is "enumerate my neighbours", and a list answers it in exactly the neighbour count. Use a list unless a specific operation argues otherwise, and be able to say which operation that would be.
What does an adjacency matrix cost in storage, and what does that cost depend on?
Complexity derivation
O(V²) cells, regardless of how many edges the graph actually contains
A matrix reserves one cell for every ordered pair of nodes, so the bill is fixed by V alone and an empty graph costs exactly as much as a complete one. That is why the structure is unusable for sparse graphs at scale and entirely reasonable for dense ones, where the cells would be occupied anyway. Storage is the price paid for the O(1) edge test.
A BFS asks for the neighbours of one node. What does that cost under each representation?
Complexity derivation
degree(X) for a list, V for a matrix row, E for a full scan of an edge list
Neighbour iteration is the operation every traversal is built from, so this row of the table decides the whole bound. Summed over all nodes, the list cost is 2E for an undirected graph, which is where O(V + E) comes from; the matrix cost is V per node and therefore V² overall. In Prism’s BFS run, exploring A produces exactly three edge inspections because A has three neighbours.
See it run — Three inspectEdge steps for A, then it is done — the walk is priced by degree, not by node count.
Your algorithm asks "is there an edge from a to b?" millions of times. Which representation wins?
Comparison
The matrix, because `m[a][b]` is one array read while a list scans a bucket
Edge existence is the one operation the matrix is built for: the two node ids are the coordinates, so the answer is an address computation. A list must scan the smaller endpoint’s bucket, which costs its degree, and an edge list must scan everything. If V is small enough that V² cells are affordable, this workload is the case for paying it.
BFS is O(V + E). What happens to that bound if the graph is handed to you as a matrix?
Complexity derivation
It becomes O(V²), because each dequeued node scans a full row of V cells
The O(V + E) bound is a property of the adjacency list, not of BFS — the algorithm only ever inherits the cost of "give me the neighbours". Each of the V dequeues reads a whole row, so the total becomes V², which on a sparse graph is catastrophically worse than V + E. This is why the representation is worth stating out loud whenever you quote a graph bound.
At what point does a matrix stop being wasteful and start being the right choice?
Trade-off & selection
When E approaches V², so the cells are occupied anyway, or when V is small enough that V² is cheap
The comparison is V² cells against V + E cells, so a matrix pays for itself only when E is within a constant factor of V². The second half of the answer matters just as much in practice: with V in the low thousands, V² is a few million cells and the O(1) edge test can be worth buying outright. The sentence that shows you own the trade is "matrix when dense or when V is small and edge tests dominate; list otherwise".
Kruskal’s algorithm wants an edge list rather than an adjacency list. What about its shape demands that?
Invariant identification
It processes all edges in global weight order and never asks for one node’s neighbours
The access pattern is "give me all edges, cheapest first", which is exactly what an array of triples supports and exactly what an adjacency list makes awkward. Union-find then supplies the connectivity test, so neighbour enumeration never appears anywhere in the algorithm. Bellman–Ford has the same shape for the same reason: relax every edge, V−1 times, in any order.
See it run — The run opens on twelve edges in weight order — the edge list is the input format, not a conversion.
A BFS over an undirected graph reaches only part of it, yet the traversal code is textbook. Where is the bug?
Code diagnosis
The builder pushed each edge into one bucket only, so half the graph is one-way
An undirected edge is stored twice, once in each endpoint’s bucket, and forgetting the second insertion is the most common graph-construction bug there is. The traversal is then perfectly correct over a directed graph that is not the one you meant to build. The tell is that reachability is asymmetric: starting from the other end reaches nodes the first run missed.
Counting islands in a grid is a graph traversal. Which representation should you build for it?
Trade-off & selection
None — neighbours are computed from row and column offsets, an implicit graph with no storage
A grid, a word ladder, and a puzzle state space are all graphs whose neighbours are generated rather than stored, which is the cheapest representation available. The traversal is ordinary BFS or DFS, with `for (dr, dc) of [[1,0],[-1,0],[0,1],[0,-1]]` standing in for the bucket walk. Recognising the implicit case is worth more than the pricing table, because interview graphs rarely announce themselves as graphs.
One million nodes and five million edges. Put actual numbers on the two representations.
Complexity derivation
A list stores about ten million endpoints; a matrix wants 10¹² cells, over a hundred gigabytes as bits
An undirected adjacency list holds each edge twice, so about ten million endpoint entries plus a million buckets — tens of megabytes, entirely ordinary. The matrix reserves V² cells whatever E is, which here is 10¹² cells, or well over a hundred gigabytes even packed one bit per cell. Doing this arithmetic out loud is how you show that "sparse graphs want lists" is a conclusion rather than a slogan.
Which kind of algorithm makes an adjacency matrix the natural fit rather than a concession?
Comparison
All-pairs shortest paths — Floyd–Warshall is a triple loop that reads and writes the grid directly
Floyd–Warshall’s state is itself a V×V table of distances, so the matrix is the answer as well as the input and its O(V³) cost already assumes dense access. Algorithms whose output is per-pair have no reason to avoid per-pair storage. When the output is per-node or per-edge, the matrix is paying for cells the algorithm will never read.
Data arrives as a CSV of relationships and your traversal needs an adjacency list. What does the conversion cost?
Complexity derivation
O(V + E): one pass over the edges, appending each endpoint into the right bucket
Building the list is a single linear pass, so "read an edge list, build an adjacency list" is essentially free next to any traversal that follows. That is why the edge list is the usual wire format and the adjacency list the usual working format, and why converting is a non-decision. The one thing to get right in that pass is inserting undirected edges into both buckets.
Inside an adjacency list, should each node’s bucket be an array or a hash set?
Trade-off & selection
An array, unless edge-existence tests are frequent enough to outweigh iteration speed
The operation the bucket serves most is sequential iteration, and a contiguous array beats a hash set on that decisively because of cache behaviour. A set only pays off when the workload really is edge-existence-heavy, which is the same workload that argues for a matrix. This is the level at which "adjacency list" stops being one thing and becomes an implementation choice.
Prism sorts each adjacency bucket when it builds a graph. What property does that buy?
Invariant identification
A deterministic traversal order, so the same input always produces the same trace
Two runs over the same graph must produce the same visit sequence for a step-through visualisation, a snapshot test, or a debugging session to mean anything. Bucket order is the only source of ambiguity in an otherwise deterministic traversal, so fixing it fixes the whole run. Determinism is a representation property, decided when the graph is built rather than when it is walked.
Union-find answers "are these two nodes connected?" without any graph representation. How?
Comparison
It stores a parent pointer per node, so connectivity is a root comparison rather than a search
The question "same component?" never needs neighbour enumeration, so the structure that answers it needs no neighbours. Each node points at a parent, `find` walks to the root, and `union` links two roots — with path compression and union by rank making both nearly constant. It is the clearest case in the syllabus of the representation being chosen by the query rather than by the data.
Dijkstra settles node B and then inspects four edges before moving on. What number is that four?
Trace prediction
B’s degree — the size of its adjacency bucket, one inspection per incident edge
Every graph algorithm on this site inherits its bound from the same operation, and this is that operation happening once. Summed over all settled nodes the inspections total E, which is why Dijkstra is O((V + E) log V) with a binary heap rather than something quadratic. One of B’s four inspections is rejected immediately because it leads back to already-settled A.
See it run — The fourth and last inspectEdge for B — count them back to step 18 and you have counted its degree.
Your graph has two flights between the same pair of cities at different prices. What does that rule out?
Edge case reasoning
A single-valued matrix cell, which can hold one weight and silently loses the other
A matrix indexes by node pair, so parallel edges collide in one cell and you have to decide up front to keep the minimum — which is fine for shortest paths and wrong for anything that needs the individual flights. Lists and edge lists both keep every edge as a separate entry, so nothing is lost. Self-loops are the same question in miniature: `m[a][a]` has exactly one cell to say something about.
Explain to someone non-technical why the same graph can be stored in three different ways. Say it out loud before revealing.
Explain it plainly
Imagine you want to record who is friends with whom in a town of a thousand people. One way is to give everybody a card listing their own friends. That is compact — you only write down friendships that exist — and it is perfect for questions like "who can I reach from Anna in three hops?", because you just read her card, then read their cards. But if I ask "are Anna and Bob friends?", you have to read all the way down Anna’s card looking for Bob. So a second way is a giant thousand-by-thousand grid with a tick in every square where two people are friends. Now "are Anna and Bob friends?" is instant — look at one square. The price is that you have drawn a million squares to record a few thousand friendships, and to list Anna’s friends you must scan her whole row of a thousand squares. The third way is just a long list of pairs: "Anna and Bob", "Bob and Carol", and so on. Useless for looking anybody up, but ideal if what you want is to sort every friendship by how long it has lasted and work through them in order. Nothing about the town changed in any of that. All that changed is which question you expect to be asked most often, and you store the data in the shape that makes that question cheap.
The listener should end up with the idea that storage is chosen by the question you ask most often, not by what the data "is". A strong answer gives one concrete question per structure and admits that each choice makes something else slower.