Lecture XIII · Data Structures & Algorithms
Graphs: search, shortest paths, spanning trees
Everything in this course so far has been about one structure at a time: a list, a tree, a table, a heap. A graph is different in kind. It is not a container you put things in; it is a way of writing down that some things are related to other things, and almost every interesting problem in computing turns out to be a graph problem wearing a costume.
Two lectures ago we built a priority queue and I promised that Dijkstra’s algorithm and Prim’s algorithm were both just “keep pulling the cheapest thing off a heap until there is nothing left”. This lecture makes good on that. By the end we will have written one search function and gotten breadth-first search, Dijkstra, and Prim out of it by changing a single expression.
The vocabulary, quickly
A graph is a set of vertices and a set of edges, where each edge joins two vertices. If the edges have a direction the graph is directed; ours will not be, because a walkway you can only use in one direction is a strange walkway. If the edges carry numbers the graph is weighted, and in this lecture the weight is minutes on foot.
A path is a sequence of vertices each joined to the next by an edge. A cycle is a path that returns to its start. A graph is connected when there is a path between every pair of vertices. The degree of a vertex is how many edges touch it.
One fact worth having in your pocket, because it catches implementation bugs faster than anything else: the degrees of all the vertices sum to , since every edge contributes one to each of its two endpoints. That is the handshake lemma, and if your adjacency structure violates it you have added an edge in one direction only.
The ADT, and two ways to build it
As always, the contract before the implementation. A graph should let us:
- ask for its vertices,
- ask for the neighbours of a vertex,
- ask whether a particular edge exists,
- add vertices and edges.
Now, two implementations. The first is the literal transcription of the definition: keep a set of vertices and a set of edges. It is honest, it is obviously correct, and it is nearly useless, because the operation every algorithm in this lecture performs constantly, “give me the neighbours of ”, requires scanning every edge in the graph.
The second keeps, for each vertex, a dictionary of its neighbours and the weight to each. Now “give me the neighbours of ” is one dictionary lookup followed by iterating a structure that already holds exactly the answer.
The cost difference is the whole reason the adjacency representation is universal:
| Operation | Edge set | Adjacency map |
|---|---|---|
addedge | ||
hasedge(u, v) | ||
nbrs(v) | ||
| Space |
with and . Same space, better time, so there is no trade to
make. The one case for a third representation, an adjacency matrix, is a
dense graph where you want hasedge and are happy to pay space;
road networks and social graphs are nowhere near dense enough for that to pay.
Search: one algorithm, one container, two behaviours
Here is the shape of every graph search ever written:
mark the start as reached
put the start in the frontier
while the frontier is not empty:
take some vertex v out of the frontier
for each neighbour u of v that is not yet reached:
mark u as reached
remember that we reached u from v
put u in the frontier
The word doing all the work is some. Which vertex you take out of the frontier is the entire algorithm. Take the oldest and you get breadth-first search. Take the newest and you get depth-first search. That is not an analogy; it is one character of difference in the code.
BFS explores in rings: everything one hop from the start, then everything two hops away, and so on. Because of that, the first time BFS reaches a vertex it has reached it by a path with the fewest possible edges. DFS charges as deep as it can down one branch before backing up, and offers no such guarantee.
Recursive DFS, and a warning
DFS has a natural recursive form, since “go as deep as you can then back up” is what the call stack does for free:
def dfs(G, v, tree=None):
if tree is None:
tree = {v: None}
for u, w in G.nbrs(v):
if u not in tree:
tree[u] = v
dfs(G, u, tree)
return tree
Elegant, and a genuine trap. As Lecture VI established, Python’s recursion limit is about a thousand frames, and a graph with a long path will blow through it. A road network laid end to end is exactly such a graph. The iterative version with an explicit stack has no such limit, which is why the plate above uses it. This is the same lesson as the call-stack lecture, arriving from a new direction: recursion is a control structure with a memory cost, and the explicit stack is always available when the cost is too high.
Weights change the question
Now the point of the whole lecture. BFS finds the path with the fewest edges. On a weighted graph that is very often the wrong answer, because three short walkways can beat one long one.
Dijkstra’s algorithm fixes this by settling vertices in order of total distance from the start rather than in order of hop count. It keeps a tentative distance for every vertex, starts them all at infinity except the source, and repeats:
- Among the vertices not yet settled, take the one with the smallest tentative distance, and settle it: declare its distance final.
- Relax each of its edges: for each neighbour , if going through beats ‘s current tentative distance, lower it and record as ‘s parent.
The claim that makes it work is that step 1 is safe: when you settle , its tentative distance really is the true shortest distance. Suppose it were not, and some shorter path to existed. That path has to leave the settled set at some point, at some vertex that is not yet settled. But everything on the path up to is non-negative, so the distance to is at most the length of the whole path, which we assumed is less than ‘s tentative distance. Then would have had a smaller tentative distance than , and step 1 would have chosen instead. Contradiction.
Notice exactly where that argument used non-negativity, and notice that it is load-bearing: Dijkstra is wrong on graphs with negative edge weights, not slow, wrong. It will settle a vertex, declare it final, and then later discover a cheaper route it can no longer use. Walking times are never negative, so we are safe here.
Where the heap goes
That linear scan for the cheapest unsettled vertex costs and runs
times, so Dijkstra as written is . Every step of it is a removemin,
and Lecture XII built the structure that does removemin in .
Dropping a heap in gives , and the standard implementation does not
even bother with changepriority. Instead it pushes a new entry every time a
distance improves and ignores entries for vertices already settled when they
surface. That is the lazy heap, and it trades a little memory (the heap can
hold more than items) for not needing the index map that Lecture XII’s
changepriority required.
Spanning trees, and the one-word difference
A spanning tree of a connected graph is a subset of edges that keeps everything connected and contains no cycle. It always has exactly edges. A minimum spanning tree is one whose total weight is as small as possible: the cheapest way to wire the whole campus so every building is reachable, with no redundant cable.
Prim’s algorithm builds one. Start anywhere, and repeatedly add the cheapest edge that joins a vertex already in the tree to a vertex not yet in it.
Now look at that next to Dijkstra and notice how nearly identical they are. Both maintain a set of settled vertices, both repeatedly take the cheapest thing outside it, both relax edges. The only difference is what “cheapest” means:
- Dijkstra scores a neighbour by : how far is from the start.
- Prim scores it by alone: how far is from the tree.
One term dropped. That is the entire difference between a shortest-path tree and a minimum spanning tree, and it is why Lecture XII could promise you both for the price of one heap.
The plate: the campus, and four ways across it
The figure this lecture exists for. The graph below is the UConn Storrs campus, and none of it is invented: the twenty-five landmarks sit at their real OpenStreetMap coordinates, and each of the forty-six edge weights is the true shortest walking distance between two landmarks along the actual footway network, converted to minutes at a stated 1.35 metres per second. When the plate says a walk takes nine minutes, that is a measurement.
The route to try first is Gampel to the Dairy Bar. Run BFS: five hops, and nearly thirty-six minutes on your feet. Now run Dijkstra: seven hops, and just over twenty. BFS wins the count it is optimising and loses you a quarter of an hour, which is the whole lecture in one gesture.
Then run McHugh to Ted’s, where the two return exactly the same route, three hops and 10.1 minutes, and ask why. There is no long detour edge anywhere between those two, so the path with the fewest walkways happens also to be the path with the fewest minutes. The disagreement between BFS and Dijkstra is a property of the map, not of the algorithms: it appears when a graph offers a short-in-hops route that is long in weight, and vanishes when it does not. Over all 600 ordered pairs of landmarks on this campus the two return different routes for 231 of them, so most pairs are worth trying and a good few are not.
Then switch to Prim, which ignores your start and goal entirely and wires the whole campus instead, and watch a different shape of answer come out of nearly the same code.
| algorithm | hops | minutes · vs 15 | settled |
|---|---|---|---|
| BFS · fewest hops | 5 | 22.4 over | 25 |
| DFS · any route at all | 19 | 84.1 over | 25 |
| Dijkstra · fewest minutes | 5 | 18.8 over | 24 |
| Prim · spanning tree | 24 walkways | 82.3 | 25 |
Against a stated 15-minute passing period (an assumption of this figure, not a rule of anyone's registrar): even the fastest route is 18.8 minutes, 3.8 over, so this walk does not fit and no search will make it. Across the map, 218 of the 300 pairs of landmarks fit, 39 of them only if you walk the fastest route rather than the one with the fewest walkways, and the longest of them is the Hilltop Community Center to Kathmandu Kitchen, 31.6 minutes apart over 7 hops even by the fastest route, so no period shorter than that gets every pair on this campus to class.
All four searches, run at build time from Gampel Pavilion to Kathmandu Kitchen. They disagree here. Breadth first takes 5 hops and 22.4 minutes; Dijkstra takes 5 hops and 18.8. Same hop count, 3.6 extra minutes: breadth first is indifferent between routes of equal length, and picks wrong. The two landmarks are 1082 m apart in a straight line, and no walkway on this campus goes in a straight line. With JavaScript enabled the map is clickable, the route is yours to choose, and every algorithm steps one settled building or one relaxed walkway at a time.
settled, darker earlier frontier: seen, not settled the route, or Prim's tree the walkway being examined the small green number by a landmark is its current key: hops for BFS, minutes for Dijkstra, the cheapest single walkway into it for Prim
25 landmarks and 46 walkways, all of them real: coordinates from OpenStreetMap (© OpenStreetMap contributors, ODbL 1.0, pulled 2026-07-27), weights measured as shortest paths along the OSM footway network and converted at 1.35 m/s. Each edge is drawn as a straight chord between two buildings, so the line is a simplification and only the number is the measurement. Total walking on the map: 205.9 minutes over 16710 m.
What it costs
With vertices and edges, on the adjacency representation:
| Algorithm | Time | Answers |
|---|---|---|
| BFS | fewest edges from one source | |
| DFS | reachability, cycles, topological order | |
| Dijkstra, linear scan | cheapest total weight from one source | |
| Dijkstra, binary heap | the same | |
| Prim, binary heap | minimum spanning tree |
Every one of them visits each vertex once and each edge a constant number of times; the factors are the heap, not the graph. Note that BFS and DFS are linear in the size of the graph, which is as good as it can possibly get: you cannot answer a question about a graph without at least looking at it.
The row worth arguing about is the two Dijkstras. beats when the graph is sparse, meaning is closer to than to , and real graphs almost always are: a building does not have a walkway to every other building. On a dense graph the scan version can win. Lecture III’s whole point was that asymptotics are a claim about growth and not about any particular input, and this is the payoff.
Where you meet this again
Almost everywhere, once you learn to see it. Dependency resolution in a package manager is a topological sort, which is DFS. Word ladders and puzzle states are BFS. Network routing is Dijkstra. Clustering by “cut the most expensive edges of the MST” is Prim. Garbage collection is reachability from a root set. The next lecture takes the spanning-tree half of this one and rebuilds it around a different data structure, the disjoint-set forest, which yields Kruskal’s algorithm and one of the most surprising running times in the subject.
Problems
Work these in order. The last two run their own checks; make every row green.
On paper, the handshake. Prove that the sum of all vertex degrees equals in an undirected graph, and use it to prove that the number of vertices of odd degree is always even. Then apply it: someone tells you they have built a graph of 7 vertices in which every vertex has degree 3. Without drawing anything, say why they are wrong.
On paper, the negative edge. Construct the smallest graph you can, with at most four vertices and one negative edge weight, on which Dijkstra returns a wrong answer. Show the settle order, show the wrong distance it reports, and show the true shortest path. Then identify the exact sentence in this lecture’s correctness argument that fails on your example.
On paper, the difference. Take the campus graph from Plate V. Run Dijkstra from
McHughand write down the tree it produces; run Prim fromMcHughand write down that tree. They are different. Now answer the real question: is Prim’s tree ever a shortest-path tree? Give a two-vertex-plus-one condition under which they coincide, or give a graph where they cannot, and say which of the two you found easier and why.Breadth-first paths. Write
bfs_paths(G, start), returning a dictionary from each reachable vertex to the actual shortest path (as a list of vertices) fromstart. Unreachable vertices must be absent from the dictionary entirely, not present with a value ofNone. The checks verify hop counts, verify that every path returned is a genuine walk in the graph, and pin the tie-break that sorted neighbours force.The checks · run against your code
paths = bfs_paths(G, "A") # the start is its own path assert paths["A"] == ["A"] # every vertex is reachable in this graph assert sorted(paths.keys()) == ["A", "B", "C", "D", "E", "F", "G"] # hop counts are the true minimum assert len(paths["B"]) - 1 == 1 assert len(paths["D"]) - 1 == 2 assert len(paths["G"]) - 1 == 3 # every returned path is a real walk in the graph for v, p in paths.items(): assert p[0] == "A" and p[-1] == v for i in range(len(p) - 1): assert p[i + 1] in dict(G.nbrs(p[i])) # with sorted neighbours, D is reached via B and not via C assert paths["D"] == ["A", "B", "D"] # an isolated vertex is simply absent, not mapped to None G2 = Graph([("A", "B", 1)]) G2._nbrs.setdefault("Z", {}) p2 = bfs_paths(G2, "A") assert "Z" not in p2 assert sorted(p2.keys()) == ["A", "B"]python runs in your browser · first run downloads ~240 kbPlate VII Paths, not just distances. Eight checks: the trivial path to the start, full reachability, three exact hop counts, a structural check that walks every returned path edge by edge through the graph, the tie-break at D, and the isolated-vertex case. That last one is the one that catches a `dict` initialised with every vertex up front. Hint one
Keep the frontier as a list used as a queue, with
pop(0)to remove. Store the paths directly: when you reachufromv, setpaths[u] = paths[v] + [u]. That copies a list per vertex, which is wasteful but correct and readable; the parent-pointer version in the lecture is the efficient one.Hint two
The isolated-vertex check is the one that fails if you write
paths = {v: None for v in G.vertices()}at the top. Start the dictionary with only the start vertex in it, and let it grow as you reach things. Membership in the dictionary is your “have I reached this?” mark, so you do not need a separatevisitedset at all.The solution
The queue, with the path carried along instead of reconstructed:
def bfs_paths(G, start): paths = {start: [start]} frontier = [start] while frontier: v = frontier.pop(0) for u, w in G.nbrs(v): if u not in paths: paths[u] = paths[v] + [u] frontier.append(u) return pathsSeven lines, and the subtle one is
if u not in paths, which does double duty as the reached-test and as the thing that makes the dictionary contain exactly the reachable vertices. Mark on enqueue, not on dequeue: if you move the marking down to wherevcomes out of the queue, a vertex with two neighbours already in the frontier will be enqueued twice, and while the answer stays correct the frontier can grow to rather than .Dijkstra, for real. Write
dijkstra(G, start)returning(dist, tree). Settle vertices cheapest-first; a settled vertex is final and must never be relaxed again. Unreachable vertices keep a distance ofINF. The checks are built around a graph where the direct edge is deliberately not the cheapest route, so an implementation that just reads off adjacent weights fails immediately. The last structural check verifies the triangle inequality across every edge, which is the real certificate that a distance labelling is optimal.The checks · run against your code
dist, tree = dijkstra(G, "A") # the direct edge is not always the cheapest route assert dist["C"] == 1 assert dist["B"] == 3 # A -> C -> B costs 3, the direct A -> B costs 4 assert tree["B"] == "C" # and the effect compounds downstream assert dist["D"] == 8 # A -> C -> B -> D assert dist["E"] == 11 # A -> C -> B -> D -> E assert dist["F"] == 13 # the long way round beats the direct C -> F of 15 # start is zero and has no parent assert dist["A"] == 0 assert tree["A"] is None # every distance is consistent with its parent edge for v in dist: if tree[v] is not None: w = dict(G.nbrs(v))[tree[v]] assert abs(dist[v] - (dist[tree[v]] + w)) < 1e-9 # the triangle inequality holds across EVERY edge, which is the real # certificate that these distances are optimal for u in G.vertices(): for v, w in G.nbrs(u): assert dist[v] <= dist[u] + w + 1e-9 # an unreachable vertex keeps distance infinity G2 = Graph([("A", "B", 1)]) G2._nbrs.setdefault("Z", {}) d2, t2 = dijkstra(G2, "A") assert d2["Z"] == INFpython runs in your browser · first run downloads ~240 kbPlate VIII Shortest paths, graded. The graph is rigged: A to B directly costs 4, but A to C to B costs 3, and that saving propagates all the way down to E and F. Beyond the exact distances, two structural checks matter more than the numbers: every distance must equal its parent's distance plus the connecting edge, and no edge anywhere may violate . Any labelling passing both is optimal, whatever route you took to find it. Hint one
Three structures:
diststarting atINFfor everything exceptstart,treestarting as{start: None}, and adoneset. Loop untildoneholds every vertex, or until the cheapest unsettled vertex has distanceINF, which means the rest is unreachable and you must stop rather than loop forever.Hint two
Finding the cheapest unsettled vertex is a plain scan over
distskipping anything indone. When you relax, guard with bothu not in doneand the improvement testdist[v] + w < dist[u]; settree[u] = vin the same branch that lowersdist[u], never outside it, or the tree will disagree with the distances.The solution
Settle, then relax, with the unreachable case handled explicitly:
def dijkstra(G, start): dist = {v: INF for v in G.vertices()} tree = {start: None} dist[start] = 0 done = set() while len(done) < len(dist): v = None for u in dist: if u not in done and (v is None or dist[u] < dist[v]): v = u if dist[v] == INF: break done.add(v) for u, w in G.nbrs(v): if u not in done and dist[v] + w < dist[u]: dist[u] = dist[v] + w tree[u] = v return dist, treeThe
if dist[v] == INF: breakis not an optimisation, it is correctness: without it, a graph with an unreachable component settles a vertex at infinite distance and then relaxesINF + winto its neighbours, which in floating point is stillINFand merely wastes time, but in an integer-weighted implementation would overflow. Note also that the entire body of the loop is oneremoveminfollowed by one pass overnbrs(v), which is exactly the shape that swapping in a heap improves, and exactly the shape that Prim shares.