Data Structures · Chapter 9

Graphs and Graph AlgorithmsData Structures · Chapter 9

A subway map, a social network and the web are the same picture: dots and lines. This chapter stores such a graph, walks through it, finds the cheapest route between two points and the cheapest way to connect all of them. It is also where the structures of the whole course meet: a queue gives breadth-first search, a stack or recursion gives depth-first search, a heap gives Dijkstra's shortest paths, and union-find gives Kruskal's minimum spanning tree.

Start → Video 1 · Graph representations Chapter outline ↓

Instructors: Boxi Yu · Yintong Huo · Python and Java versions (switch at the top) · Every program here has been run, and every output shown is the real output. · All chapters

Walk through the example graph

Seven towns A–G joined by eleven weighted roads. Choose breadth-first search, depth-first search or Dijkstra and press Step: the vertex being explored, the frontier (a queue, a stack or a priority queue) and the discovered distances change together, and a counter shows how many adjacency entries have been read.

Why this matters

about 100–120 minutes (4 videos of 11–12 minutes plus the exercises).

Graphs are the general shape of "things and their connections"

Routes, friendships, links, dependencies between tasks, circuits: the same few questions come up every time. What is connected to what? What is the fewest steps, or the cheapest route? What is the cheapest way to connect everything?

Every earlier chapter is a part here

The adjacency list is a dictionary or map of lists (chapters 2 and 7), BFS uses a queue and DFS a stack or recursion (chapters 3 and 4), Dijkstra needs a priority queue (chapter 8) and Kruskal needs union-find, a small forest of trees (chapter 5). Choosing the right one for each job is what makes the algorithms fast.

The cost depends on how the graph is stored

For a sparse graph an adjacency list needs about V + E space and a search costs V + E steps; a matrix needs V² cells even when nearly all are empty. Most real graphs are sparse, so this decision decides whether a program is usable on a million vertices.

5 parts

Four videos with their notes, then the summary and practice. Read them in order.

Graph representations

A graph is vertices plus edges, directed or not, with or without weights. A program can store it as an edge list, an adjacency list or an adjacency matrix. They differ in space and in two costs: is there an edge u–v? and who are the neighbours of v? The adjacency list is the usual choice, because real graphs are mostly sparse.

vertexedgedirectedweightdegreepathcycleconnectededge listadjacency listadjacency matrixsparsedense

Open →02

BFS and DFS

Both searches keep a frontier of vertices that are discovered but not yet explored; the only choice is which one to take next. Take the oldest (a queue) and you get breadth-first search, which explores in rings and reaches every vertex by a route with the fewest edges. Take the newest (a stack, or recursion) and you get depth-first search, which dives as deep as it can and then backs up; its discovery and finish times expose cycles. Both cost O(V + E).

frontierqueuestackBFSDFSlevelparentdiscovery timefinish timecycleO(V + E)

Open →03

Dijkstra's shortest paths

To find the cheapest route, keep a tentative distance for every vertex and always settle the closest unsettled one (a priority queue keyed by distance). Settling a vertex relaxes its edges: does going through it make the route to a neighbour cheaper? With non-negative weights the closest unsettled vertex can never be beaten later, so its distance is final. A heap makes it O((V + E) log V); a negative edge breaks the argument.

weighted shortest pathtentative distancesettlerelaxpriority queuelazy deletionstale entryshortest-path treenegative edgeBellman–Ford

Open →04

Minimum spanning trees and union-find

A minimum spanning tree (MST) connects all the vertices with V − 1 edges, no cycle, and the least total weight. A greedy rule is safe because of the cut property: the cheapest edge between any two groups of vertices belongs to the MST. Kruskal takes edges cheapest-first and skips any that would close a cycle; union-find answers "would it?" almost in constant time. Prim grows one tree from a start vertex, always adding the cheapest edge that leaves the tree.

spanning treeminimum spanning treecut propertyKruskalunion-findunion by sizepath compressionPrimO(E log V)

Open →05

Summary and practice

A one-page map of the chapter, five self-check questions, ten exercises with solutions, and a way to test claims an AI makes about complexity.

self-checkexercises

Open →

How to use these notes

Watch · Predict · Step through · Practise

STEP 1

Watch

Each part starts with its video, 8–10 minutes, in Python or Java.

STEP 2

Predict

Answer the amber Predict box before you open the answer.

STEP 3

Step through

The interactive demos are being added; each one is described where it will appear.

STEP 4

Practise

Finish with the self-check and the exercises, with templates in your language.

Video 1

Graph representations

vertexedgedirectedweightdegreepathcycleconnectededge listadjacency listadjacency matrixsparsedense

Graph representationsVideo in preparation.

§1The words

A graph has vertices (the dots) and edges (the lines between two vertices). An edge is undirected (a friendship that goes both ways) or directed (a link from one page to another, which goes one way), and it can carry a weight: a distance, a price, a travel time. The degree of a vertex is the number of edges that touch it. A path is a walk along edges, a cycle is a path that comes back to where it started, and a graph is connected when there is a path between every two vertices. The graph of the whole chapter has seven vertices A–G and eleven undirected edges with distinct weights (code/example_graph.txt): A-D 3, C-E 4, D-F 5, A-B 6, B-E 7, B-C 8, E-F 9, E-G 10, B-D 11, F-G 12, D-E 13. The degrees are A 2, B 4, C 2, D 4, E 5, F 3, G 2, and they add up to 22 = 2 × 11.

NOTE · The handshake lemma.

Every edge has two ends and adds one to the degree of two different vertices, so in an undirected graph the degrees always add up to twice the number of edges. It is the quickest sanity check for code that builds a graph (Exercise 1 uses the same count).

§2Three ways to store it

An edge list. A plain list of (from, to, weight). Eleven edges, eleven entries: very compact. But "is there an edge A–G?" and "who are the neighbours of E?" both read the whole list.
An adjacency list. For every vertex a list of its neighbours, with the weight of the edge. A has B and D; B has A, C, D and E; an undirected edge appears twice, once in each end's list, so the lists hold 22 entries. The neighbours of v are right there, and looking at them costs the number of neighbours, no more.
An adjacency matrix. A table with a row and a column for every vertex; the cell (u, v) holds the weight or stays empty. "Is there an edge A–G?" is one cell, however large the graph. The price: 7 × 7 = 49 cells for 11 edges, and listing the neighbours of one vertex scans a whole row.

	entries stored (example graph)	is there an edge u–v?	who are the neighbours of v?
edge list	11	every edge	every edge
adjacency list	22	the number of neighbours of u	exactly the neighbours
adjacency matrix	49	1 step	the whole row, V cells

In Python the adjacency list is a dictionary from each vertex to a list of (neighbor, weight) pairs (code/py/graph.py): add_edge(u, v, weight) appends to the list of u and, for an undirected graph, to the list of v as well. neighbors returns the list sorted, so that every traversal in this chapter visits in the same order.

In Java the adjacency list is a Map<V, List<Edge<V>>> (code/java/Graph.java, a TreeMap so that vertices come out sorted) where Edge is a record of the vertex it goes to and the weight; addEdge(u, v, weight) appends to the list of u and, for an undirected graph, to the list of v too, and neighbors returns a sorted copy.

class Graph:    def add_edge(self, u, v, weight=1):        self.add_vertex(u)        self.add_vertex(v)        self._adj[u].append((v, weight))        if not self.directed:            self._adj[v].append((u, weight))   # an undirected edge is stored in both lists

public void addEdge(V u, V v, int weight) {    addVertex(u);    addVertex(v);    adj.get(u).add(new Edge<>(v, weight));    if (!directed) {        adj.get(v).add(new Edge<>(u, weight));   // an undirected edge is stored in both lists    }}

One graph, three tables

Click a vertex pair in the drawing: the edge list, the adjacency list and the adjacency matrix each show how many entries they read to answer "is there an edge?" and "who are the neighbours?", with a running total for each.

PREDICT

A social network has 1,000 people and each follows about 6 others: about 3,000 friendships. How many cells does the adjacency matrix need, how many entries does the adjacency list need, and how many steps does it take to list one person's friends in each?

Show the answer

The matrix needs 1,000,000 cells, almost all empty, and listing the friends of one person scans a row of 1,000 cells. The adjacency list needs 6,000 entries (twice the edges) and listing the friends takes 6 steps. This is the sparse graph of the demo (code/py/representations_demo_output.txt, identical in Java):

representation	entries	has_edge steps	neighbors steps
adjacency list	6,000	6	6
adjacency matrix	1,000,000	1	1,000
edge list	3,000	3,000	3,000

The matrix is not "the safe choice": it answers is there an edge in one step, but it wastes almost everything on a sparse graph.

On the dense graph of the same demo (1,000 vertices where half of all pairs are joined, 249,500 edges) the list holds 499,000 entries and has_edge costs about 499 steps, while the matrix still holds a million cells, now half of them used, so it is no longer wasteful. The rule: for a sparse graph use adjacency lists; for a dense graph, or when you test edges all the time, the matrix can win.

PITFALL · An undirected edge stored once.

If add_edge(u, v) only appends to the list of u, the graph you built is directed by accident: v does not know u, and a search from v never finds the way back. Test with the handshake lemma, and check that has_edge(u, v) and has_edge(v, u) agree.

§3The standard libraries

Python has no graph class in the standard library. A dictionary of lists is the usual answer, and collections.defaultdict(list) removes the "add the vertex first" step (the third-party library networkx wraps the same idea).

Java has no graph class in the standard library either. A Map<V, List<Edge>> is the usual answer, and computeIfAbsent creates a vertex's list on first use (third-party libraries such as JGraphT wrap the same idea).

Video 2

BFS and DFS

frontierqueuestackBFSDFSlevelparentdiscovery timefinish timecycleO(V + E)

BFS and DFSVideo in preparation.

§1The frontier idea

A search sorts the vertices into three kinds: undiscovered, explored (all neighbours looked at) and the frontier, discovered but not yet explored. The loop never changes: take a vertex off the frontier, look at its neighbours, and put every neighbour you have never seen onto the frontier. The only free choice is which vertex to take off. The oldest gives a queue; the newest gives a stack.

§2Breadth-first search

From A: take A off; its neighbours B and D go on the queue. Take B: A and D are known, C and E are new. Take D: F is new. Then C (nothing new), E (G is new), F, G. The order of visits is A B D C E F G, and the levels (number of edges from A) are A 0, B 1, D 1, C 2, E 2, F 2, G 3: the search explores in rings.

Breadth-first search from A

Step through the search: the queue is drawn under the graph, the vertex just taken out is highlighted and each new vertex receives its level and its parent; a counter shows the adjacency entries read (22 at the end).

Each vertex remembers who discovered it, its parent. Follow the parents back from G: E, then B, then A, so the route is A B E G: three edges, and no route has fewer, because BFS reaches a vertex in the first ring that touches it (Exercise 1 proves it).

bfs(graph, start) in code/py/traversal.py returns the order, the levels and the parents; the queue is a collections.deque.

Traversal.bfs(graph, start) in code/java/Traversal.java returns a record with the order, the levels and the parents; the queue is an ArrayDeque.

def bfs(graph, start):    level = {start: 0}    parent = {start: None}    order = []    queue = deque([start])    while queue:        u = queue.popleft()        order.append(u)        for v, _ in graph.neighbors(u):            if v not in level:            # mark when we enqueue, so nobody is queued twice                level[v] = level[u] + 1                parent[v] = u                queue.append(v)    return order, level, parent

public static <V extends Comparable<V>> BfsResult<V> bfs(Graph<V> graph, V start) {    Deque<V> queue = new ArrayDeque<>();    level.put(start, 0);    parent.put(start, null);    queue.add(start);    while (!queue.isEmpty()) {        V u = queue.poll();        order.add(u);        for (Graph.Edge<V> e : graph.neighbors(u)) {            V v = e.to();            if (!level.containsKey(v)) { // mark when we enqueue, so nobody is queued twice                level.put(v, level.get(u) + 1);                parent.put(v, u);                queue.add(v);            }        }    }    return new BfsResult<>(order, level, parent);}

PITFALL · Mark a vertex when you put it on the queue, not when you take it off.

Otherwise a vertex is queued again by every neighbour that reaches it. On a triangle A-B-C, without marking, every pop adds two more vertices: after 20 pops the queue is longer than when it started (21 entries) and A has been visited 7 times; the search never ends. Marking too late in a more careful way (taking a vertex off, skipping it if it was done) ends, but it gives the wrong levels (Exercise 9).

PREDICT

The edges have weights. Is the route A B E G, found by BFS, also the cheapest route from A to G?

Show the answer

No. A B E G costs 6 + 7 + 10 = 23, but A D F G has the same three edges and costs 3 + 5 + 12 = 20. BFS counts edges; it does not look at weights. For the cheapest route we need another algorithm: Dijkstra's, in the next video.

§3Depth-first search

Now take the newest vertex. From A we go to its first neighbour B, then C, then E, then D, then F, then G: always from the vertex just found. G has no unseen neighbour, so we back up, to F, D, E, … all the way to A, checking each for anything skipped. The order of discovery is A B C E D F G. If the search keeps a clock and writes down the time it first reaches a vertex and the time it finishes with it:

A = 1/14, B = 2/13, C = 3/12, E = 4/11, D = 5/10, F = 6/9, G = 7/8 (discovery/finish)

Every vertex's interval sits inside its parent's: the intervals are nested like brackets, and that nesting is what DFS computes.

Depth-first search from A

Step through the dive and the backing up: the call stack is drawn beside the graph, each vertex shows its discovery and finish time as soon as it gets them, and the intervals are drawn as bars under the graph so you can see them nest.

Depth-first search is naturally recursive: to visit a vertex, mark it and visit each unseen neighbour; the call stack is the stack of the search, backing up is returning. The same can be done with an explicit stack: push the neighbours in reverse order and pop the next vertex; it visits in exactly the same order. A cycle shows up as an edge to a vertex we have already seen, other than the one we came from (undirected graph), or as an edge back to a vertex that is still being explored (directed graph; Exercise 5).

NOTE · The cost of a search.

Each vertex is taken off the frontier once and each vertex's list of neighbours is read once: V vertices and 2E entries (22 on the example graph), so O(V + E) for both searches. They differ in the order, not in the effort.

§4The standard libraries

Use collections.deque for the queue: popleft is constant time, while list.pop(0) shifts every element and would make breadth-first search slow. A plain list is a fine stack (append, pop).

Use ArrayDeque for both the queue and the stack; the old Stack class is legacy and LinkedList is slower and heavier.

Video 3

Dijkstra's shortest paths

weighted shortest pathtentative distancesettlerelaxpriority queuelazy deletionstale entryshortest-path treenegative edgeBellman–Ford

Dijkstra's shortest pathsVideo in preparation.

§1The idea

Start from A with distance 0; every other vertex gets a tentative distance of infinity (no route known yet). Repeat one step: among the vertices not yet settled, take the one with the smallest tentative distance and settle it: its distance is final. Then look at each of its edges: if going through this vertex gives a neighbour a cheaper route than it has now, update the neighbour and remember this vertex as its parent. That update is called relaxing the edge: one comparison, d + w < dist[v]. To pick the closest vertex quickly, keep the tentative distances in a priority queue.

§2A run on the example graph

From A (code/py/dijkstra_demo_output.txt, identical in Java):

step	settled	relaxations
1	A (0)	B = 6, D = 3
2	D (3)	E = 16, F = 8
3	B (6)	C = 14, E = 13 (better than 16)
4	F (8)	G = 20
5	E (13), then C (14)	nothing to improve
	the stale entry E (16) is skipped
6	G (20)

The final distances are A 0, D 3, B 6, F 8, E 13, C 14, G 20. Following the parents back from G gives A D F G, cost 20; BFS gave A B E G, cost 23: same number of edges, different cost. The parents of all the vertices form the shortest-path tree, here of weight 41 (the minimum spanning tree of video 4 costs 35: a different question, a different tree).

Dijkstra from A

Step through the run: every vertex shows its tentative distance (infinity at first), the priority queue is drawn as a list sorted by distance, and each relaxation highlights the edge and the old and new distance; the stale entry of E is struck through when it comes to the front. Counters show pushes, pops and stale entries.

PITFALL · A first distance is not final.

Watch for the word tentative: E first gets 16 (through D) and later 13 (through B). A vertex can be relaxed several times before it is settled. Treating the first distance as final is the classic mistake.

§3Lazy deletion

A heap cannot change the priority of an entry that is already inside it. So when E improved from 16 to 13 we pushed a second entry for E and left the old one in the heap. When the old entry (E, 16) comes to the front, E is already settled, so we recognise it as stale and skip it. In our run: 8 pushes, 8 pops, 1 of them stale. On a larger graph (1,000 vertices, 3,000 edges, weights 1–97) there are 1,603 pushes and pops, of which 603 are stale: a few thousand heap operations, not millions.

dijkstra(graph, source) in code/py/shortest_paths.py uses heapq with (distance, vertex) tuples, which compare distance first, vertex second, and a set done of settled vertices.

ShortestPaths.dijkstra(graph, source) in code/java/ShortestPaths.java uses a PriorityQueue of entries compared by distance, then vertex, and a HashSet of settled vertices.

heap = [(0, source)]done = set()while heap:    d, u = heapq.heappop(heap)    if u in done:                  # an older, longer entry for a vertex that is already settled        continue    done.add(u)    for v, w in graph.neighbors(u):        if d + w < dist[v]:        # relax the edge u-v            dist[v] = d + w            parent[v] = u            heapq.heappush(heap, (dist[v], v))

PriorityQueue<Entry<V>> heap = new PriorityQueue<>();heap.add(new Entry<>(0, source));Set<V> done = new HashSet<>();while (!heap.isEmpty()) {    Entry<V> top = heap.poll();    int d = top.dist();    V u = top.node();    if (done.contains(u)) {        // an older, longer entry for a vertex that is already settled        continue;    }    done.add(u);    for (Graph.Edge<V> e : graph.neighbors(u)) {        V v = e.to();        if (d + e.weight() < r.dist.get(v)) {   // relax the edge u-v            r.dist.put(v, d + e.weight());            r.parent.put(v, u);            heap.add(new Entry<>(d + e.weight(), v));        }    }}

§4Why it works, and when it breaks

Suppose we settle u, the closest unsettled vertex, at distance d. Any other route to u must leave the settled region somewhere, through a vertex that is not settled yet; that vertex is at least as far as u, because u was the closest, and the rest of the route can only add to the total because weights are not negative. So no other route beats d (Exercise 2 proves it). The assumption is essential. Take S→A 2, S→B 3, A→C 3 and B→A −2: Dijkstra settles A at 2 and prices C at 5; then it settles B at 3 and finds that A would cost only 1 through B, too late, because A is already settled. It reports C = 5, but the route S B A C costs 3 − 2 + 3 = 4. The code refuses negative weights by default (Dijkstra needs non-negative edge weights); Bellman–Ford handles them, at a higher cost.

The cost: each arc is relaxed at most once, when its tail is settled, and a relaxation adds at most one heap entry; a heap operation costs log of its size, so the total is O((V + E) log V).

§5The standard libraries

heapq is the priority queue: a min-heap on a plain list, and tuples compare in order, so distance first, vertex second. There is no decrease-key, which is why the lazy deletion above is the usual solution.

PriorityQueue is the heap: give it Comparable entries or a Comparator. Its iterator is not sorted; only poll returns the minimum. There is no decrease-key either, so the lazy deletion above is the usual solution. Use a large int for infinity with care: Integer.MAX_VALUE + w overflows.

Video 4

Minimum spanning trees and union-find

spanning treeminimum spanning treecut propertyKruskalunion-findunion by sizepath compressionPrimO(E log V)

Minimum spanning trees and union-findVideo in preparation.

§1What we are looking for

Seven towns must be joined by cable, each possible link has a price, and building all eleven would cost 3 + 4 + … + 13 = 88. Which links should we build? A set of edges that connects all the vertices with the least total weight. If it had a cycle we could drop one edge of the cycle and stay connected, cheaper, so the best answer has no cycle: a connected graph with no cycle is a tree, with seven vertices exactly six edges. A tree that spans every vertex is a spanning tree; the cheapest is the minimum spanning tree.

§2The cut property

Split the vertices into any two groups. Look at all edges with one end in each group: the cheapest of them belongs to the MST. With the group {A, D, F} against the rest the edges between them cost 6, 9, 11, 12 and 13; the cheapest is A-B, 6, and indeed it is in the tree. Why? If the tree did not use it, adding it would create a cycle, which must cross the cut a second time through a more expensive edge; swap them and the tree gets cheaper (Exercise 3).

§3Kruskal's algorithm

Sort all edges by weight and go through them from the cheapest. Add an edge if it joins two vertices that are not yet connected; skip it if they are, because it would close a cycle. On the example graph (code/py/mst_demo_output.txt):

edge	weight	decision
A-D	3	accept
C-E	4	accept
D-F	5	accept
A-B	6	accept
B-E	7	accept
B-C	8	reject: B and C are already connected, through E
E-F	9	reject: already connected
E-G	10	accept
B-D	11	reject
F-G	12	reject
D-E	13	reject

Six edges, total weight 35, instead of 88.

Kruskal and its forest

Press Next edge: the edge list is sorted by weight, the current edge is highlighted in the graph and the union-find forest is drawn beside it. An accepted edge hangs the smaller tree under the bigger one; a rejected edge is struck through and the two roots are shown to be equal.

§4Union-find

Kruskal keeps asking one question: are these two vertices already connected? Searching the graph each time would be slow, so a data structure answers it: union-find (disjoint sets). Each group of connected vertices is a small tree whose root is the group's name. union joins two groups by hanging one root under the other, always the smaller tree under the bigger one, and the trees stay shallow; find walks up from a vertex to its root, and two vertices are in the same group when their roots are equal. How shallow? Merge 1,024 separate vertices in the worst way (pairs, then pairs of pairs, …): the deepest vertex ends up only 10 steps from its root, the base-2 logarithm of 1,024. A second trick, path compression: when find walks up a long path it points every vertex on the path straight at the root. A chain of 10 vertices has its bottom vertex 9 steps from the root; after one find, no vertex is more than 1 step away.

DisjointSets in code/py/mst.py keeps two dictionaries, parent and size; a root is its own parent. The tuple assignment self.parent[x], x = root, self.parent[x] evaluates the right side first, so the old parent is remembered before it is overwritten.

DisjointSets<T> in code/java/DisjointSets.java keeps two maps, parent and size; a root is its own parent. Because the class is generic, elements are compared with equals, not with ==.

def find(self, x):    root = x    while self.parent[root] != root:        root = self.parent[root]    while self.parent[x] != root:       # path compression        self.parent[x], x = root, self.parent[x]    return root def union(self, a, b):    ra, rb = self.find(a), self.find(b)    if ra == rb:        return False    if self.size[ra] < self.size[rb]:        ra, rb = rb, ra    self.parent[rb] = ra                # the smaller tree hangs under the bigger one    self.size[ra] += self.size[rb]    return True

public T find(T x) {    T root = x;    while (!parent.get(root).equals(root)) {        root = parent.get(root);    }    while (!parent.get(x).equals(root)) {   // path compression        T next = parent.get(x);        parent.put(x, root);        x = next;    }    return root;} public boolean union(T a, T b) {    T ra = find(a);    T rb = find(b);    if (ra.equals(rb)) {        return false;    }    if (size.get(ra) < size.get(rb)) {        T tmp = ra;        ra = rb;        rb = tmp;    }    parent.put(rb, ra);                     // the smaller tree hangs under the bigger one    size.put(ra, size.get(ra) + size.get(rb));    return true;}

§5Prim's algorithm

Prim grows a single tree from any vertex, say A. At each step it looks at all edges leaving the tree and adds the cheapest one; a priority queue finds it. From A: A-D (3), then D-F (5), then A-B (6), then B-E (7), then E-C (4), then E-G (10): total 35, the same tree. The two algorithms take different paths to the same answer (with distinct weights the MST is unique). When an edge is taken from the queue and its far end is already in the tree, it is skipped, exactly like a stale entry in Dijkstra.

Prim from A

The tree grows from A: the priority queue of edges leaving the tree is drawn as a sorted list, the cheapest is taken, and edges whose far end is already in the tree are struck through when they come to the front. A counter shows the total weight (35 at the end).

PREDICT

The cable network we built is the cheapest overall. Does it also give the cheapest route from A to G? And which is cheaper in total, the tree of cheapest routes from A (video 3) or the minimum spanning tree?

Show the answer

No. Inside the spanning tree the only route from A to G is A B E G, 6 + 7 + 10 = 23, while the cheapest route in the whole graph is A D F G, 20. And the tree of cheapest routes from A weighs 41, against 35 for the minimum spanning tree: different questions, different trees. The MST minimises the total cable; it does not minimise any single route.

The cost: Kruskal is dominated by sorting the edges, O(E log E), which is O(E log V) because E ≤ V²; the union-find steps are almost constant. Prim with a heap also costs O(E log V).

PITFALL · Three mistakes.

Kruskal without the cycle test simply adds every edge. Prim without skipping edges whose far end is already in the tree adds vertices twice. And the minimum spanning tree is not the tree of cheapest routes.

§6The standard libraries

Python has no union-find in the standard library; sorting with a key (sorted(edges, key=...)) and the heapq module are the tools we used.

Java has no union-find either; sorting a list with a Comparator and PriorityQueue are the standard tools.

Summary

Summary and Practice

Check yourself, then build some programs

A one-page map of the chapter, five self-check questions, ten exercises with solutions, and a way to test claims an AI makes about complexity.

knowledge mapself-checkexercises

§1Knowledge map

 graph = vertices + edges (directed or not, weighted or not);  sum of degrees = 2 × edges          │          ├── stored as: edge list (E) · adjacency list (V + E, the usual choice) · adjacency matrix (V², is there an edge? in 1 step)          │          ▼ search: a frontier of discovered-but-unexplored vertices, cost O(V + E)     ├── queue  → BFS: rings, fewest EDGES from the start (levels, parents)     └── stack / recursion → DFS: dives, discovery/finish times nested like brackets, finds cycles          │          ▼  weights ≥ 0, cheapest route Dijkstra: settle the closest vertex, relax its edges; priority queue + lazy deletion; O((V + E) log V); a negative edge breaks it          │          ▼  connect everything cheaply minimum spanning tree: cut property ⇒ greedy is safe     ├── Kruskal: sort the edges, union-find skips cycles; O(E log V)     └── Prim: grow one tree with a priority queue of edges leaving it; O(E log V)

One line each: a graph is dots and lines · the adjacency list is the usual choice for sparse graphs · BFS (queue) finds the fewest edges, DFS (stack) dives and finds cycles, both cost V + E · mark vertices when you discover them · Dijkstra settles the closest vertex and relaxes its edges, needs non-negative weights, uses a heap with lazy deletion · the cheapest edge across any cut belongs to the MST · Kruskal uses union-find (small trees, hang the smaller under the bigger, compress paths) · the MST is not the tree of cheapest routes.

§2Check your understanding

1. A graph has 1,000 vertices and about 3,000 edges. Which representation do you choose to list the neighbours of a vertex quickly and keep the memory small?

The list holds about 6,000 entries and listing a vertex's neighbours takes about 6 steps; the matrix needs 1,000,000 cells and scans a row of 1,000 cells; the edge list reads all 3,000 edges.

2. BFS from A on the example graph returns the route A B E G to G. What is true?

BFS counts edges and ignores weights; for the cheapest route we need Dijkstra.

3. In Dijkstra's run on the example graph, E first gets the distance 16 and later 13. What happens to the entry (E, 16) in the heap?

A binary heap cannot change the key of an entry inside it, so Dijkstra pushes a second entry and recognises the old one as stale (lazy deletion): the run makes 8 pushes and 8 pops, one of them stale.

4. Why does Dijkstra's algorithm need non-negative weights?

With S→A 2, S→B 3, A→C 3 and B→A −2 it reports C = 5, but the true distance is 4 (S, B, A, C).

5. Kruskal's algorithm on the example graph rejects the edge B-C (weight 8). Why?

Kruskal accepts an edge only when its ends are in different trees of the forest; union-find answers that question almost in constant time. The six accepted edges weigh 35 in total.

§3Exercises

Ten exercises in four layers: three proofs, two designs, three implementations with milestones, and two read-the-code. Proofs and designs are the same in both languages; the implementation exercises come as templates in PythonJava with tests that fail on purpose, and your job is to make every test pass. Try each exercise before you open its solution.

#	Layer	Topic	Video
1	Proof	BFS finds a route with the fewest edges	2
2	Proof	Dijkstra: why the popped distance is final, and what it costs	3
3	Proof	The cut property, and why Kruskal is correct	4
4	Design	Shortest route when the vertices carry the weights	3
5	Design	Finding a cycle in a directed graph	2
6	Implement	BFS with levels and parents	2
7	Implement	Routes from parents, and how many shortest routes there are	2
8	Implement	Union-find with union by size and path compression	4
9	Read the code	An AI-written BFS that "returns the distances"	2
10	Read the code	An AI-written Dijkstra that "examines every edge once"	3

PROOFS

Exercise 1 · BFS finds a route with the fewest edges. Run BFS from a start vertex s on an undirected graph (the version of video 2: a vertex is marked, given level[v] = level[u] + 1 and a parent when it is put into the queue). (a) Prove that the levels of the vertices, in the order in which they are taken out of the queue, never decrease and that two vertices that are next to each other in that order differ by at most 1. (Hint: induction on the number of vertices taken out; look at the queue.) (b) Let δ(v) be the smallest number of edges on a route from s to v. Prove that level[v] = δ(v) for every reachable vertex v. First show level[v] ≥ δ(v) (what route does the parent chain give?), then level[v] ≤ δ(v) by induction on δ(v), using (a). (c) Show that the adjacency list of every reachable vertex is read exactly once, so BFS costs V + 2E list entries in an undirected graph. Check it for the example graph from A: order, levels and the number of entries. (d) The example graph has three routes from A to G with three edges. Name them, and say which one BFS returns when the neighbours are visited in alphabetical order, and what its weight is compared with the cheapest route.

Solution

(a) Claim: at every moment the queue is [v₁, …, v_k] with level(v₁) ≤ … ≤ level(v_k) ≤ level(v₁) + 1, and the vertices taken out earlier have levels ≤ level(v₁). Initially the queue holds only s. Taking out v₁ and appending its newly discovered neighbours, each of level level(v₁) + 1: the new vertices come after v_k, and level(v₁) + 1 ≥ level(v_k) (v_k has level at most level(v₁) + 1), so the queue is still non-decreasing; the new first element v₂ has level ≥ level(v₁) and the new last one has level level(v₁) + 1 ≤ level(v₂) + 1. If nothing is appended the claim holds trivially. So the levels never decrease along the order in which vertices leave the queue and neighbours in that order differ by at most 1. ∎ (test_the_levels_along_the_visit_order_never_decrease_and_grow_by_at_most_one.)

(b) level[v] ≥ δ(v): following parents from v leads back to s along level[v] edges (each parent is one level closer: level[parent] = level[v] − 1), so there is a route with level[v] edges and δ(v) ≤ level[v]. level[v] ≤ δ(v), by induction on d = δ(v): for d = 0, v = s and level[s] = 0. For d ≥ 1 take a neighbour u of v on a route with d edges, so δ(u) = d − 1 and, by the induction hypothesis, level[u] = d − 1. When u is taken out, either v has been discovered before, by some w that left the queue before u, and by (a) level[w] ≤ level[u], so level[v] = level[w] + 1 ≤ d; or v is discovered now and level[v] = level[u] + 1 = d. Together level[v] = δ(v). ∎ (Checked against Floyd–Warshall on 300 random graphs.)

(c) Every vertex is put into the queue at most once (it is marked the moment it is put in) and taken out once, and the adjacency list of the vertex that is taken out is read once: V list fetches and Σ deg(v) = 2E entries in all, V + 2E. Example graph from A: order A B D C E F G, levels A 0, B 1, D 1, C 2, E 2, F 2, G 3, the seven lists hold 22 entries (2 · 11), so 7 + 22 = 29 steps (test_every_adjacency_list_is_read_exactly_once).

(d) Routes with three edges: A B E G (6 + 7 + 10 = 23), A D E G (3 + 13 + 10 = 26) and A D F G (3 + 5 + 12 = 20). In alphabetical order A takes B before D, B discovers E before D can, so G's parent is E and E's parent is B: BFS returns A B E G, weight 23, while the cheapest route is A D F G with weight 20: the fewest edges is not the cheapest (video 2).

Exercise 2 · Dijkstra: the popped distance is final, and what it costs. Dijkstra's algorithm of video 3 keeps a priority queue of pairs (distance, vertex) with lazy deletion: a vertex can be in the queue several times, an entry of a vertex that is already settled is skipped ("stale"), and all weights are ≥ 0. (a) State the invariant "when a vertex u is taken out of the queue for the first time, dist[u] is the true shortest distance δ(u)" and prove it. (Hint: suppose u is the first vertex for which it fails; follow a true shortest route from s to u until it leaves the set of settled vertices, and look at the first unsettled vertex y on it; compare dist[y] and dist[u]. Where do you use that weights are not negative?) (b) Prove that the keys taken out of the queue never decrease, and that the number of pushes is at most 2E + 1 for an undirected graph. Conclude the running time O((V + E) log V) with a binary heap. Check the pushes, pops and the single stale entry on the example graph from A (video 3: 8 pushes, 8 pops, 1 stale). (c) The directed graph S→A 2, S→B 3, A→C 3, B→A −2 has a negative arc. Run the algorithm by hand (a settled vertex is never looked at again), say where the invariant of (a) breaks, and give the distance it reports for C and the true one.

Solution

(a) Invariant: when a vertex is taken out of the queue for the first time, its dist equals δ, the true distance. Suppose u is the first vertex for which this fails, taken out with dist[u] > δ(u). Take a true shortest route s = x₀, …, x_m = u. Let y = x_j be the first vertex on it that is not yet settled (one exists, because u itself is unsettled; the source is settled first, so j ≥ 1 and the vertex before y, x_{j−1}, is settled). By the minimality of u, dist[x_{j−1}] = δ(x_{j−1}), and when x_{j−1} was settled it relaxed the arc to y, so dist[y] ≤ δ(x_{j−1}) + w(x_{j−1}, y) = δ(y) (the prefix of a shortest route is a shortest route), hence dist[y] = δ(y). Non-negative weights: the rest of the route from y to u has weight ≥ 0, so δ(y) ≤ δ(u) < dist[u]. Then the queue holds an entry of y with key dist[y] < dist[u] (or y is u), but u was taken out first although its key is not smaller: contradiction. ∎ The one place where the weights matter is the step δ(y) ≤ δ(u).

(b) Keys never decrease: the key taken out is the smallest in the queue; new entries have key d + w ≥ d (non-negative w), so nothing smaller than the key just taken out ever enters (test_popped_distances_never_decrease_and_are_final). Pushes: one push for the source and one for each improving relaxation; an arc u→v is relaxed only when u is settled, once per arc, and an undirected edge gives two arcs, so pushes ≤ 2E + 1 (and pops = pushes). The queue never holds more than 2E + 1 entries, log(2E + 1) = O(log V) since E ≤ V², so V settlings plus 2E relaxations cost O((V + E) log V). Example from A (dijkstra_demo): 8 pushes, 8 pops, 1 stale entry (E with key 16, because E later became 13 through B), distances A 0, B 6, C 14, D 3, E 13, F 8, G 20, bound 2 · 11 + 1 = 23.

(c) Start S: A = 2, B = 3. Take S's smallest, A (2): C = 5. Take B (3): the arc B→A has weight −2, so A could be 1, and the entry (1, A) is pushed, but A is already settled, so it is skipped as stale and never looked at again: C stays 5. The true distance is 4 (S, B, A, C: 3 − 2 + 3), found by Bellman–Ford (test_a_negative_arc_breaks_dijkstra_but_not_bellman_ford). The invariant of (a) breaks at the first pop of A: dist[A] = 2 but δ(A) = 1; the step "the rest of the route has weight ≥ 0" is false when an arc is negative.

Exercise 3 · The cut property, and why Kruskal is correct. In this exercise all edge weights are different, so a connected graph has exactly one minimum spanning tree (MST). (a) A cut is a split of the vertices into two non-empty sets S and V∖S. Prove the cut property: the lightest edge e that has one end in S and one end outside belongs to every MST. (Hint: take an MST T without e; adding e to T closes a cycle; where else does that cycle cross the cut?) (b) Kruskal's algorithm takes the edges in order of weight and accepts an edge when its two ends are in different trees of the forest built so far. Use (a) with a well-chosen cut to prove that every accepted edge belongs to the MST; then show that the accepted edges form a spanning tree. (The cut: the vertices of the tree that contains one end of the edge.) (c) For the example graph and the cut S = {A, D, F}: list the edges crossing the cut with their weights and say which one the cut property puts into the MST. Check that it is among the six edges Kruskal accepts in video 4.

Solution

(a) Let e = {u, v} be the lightest edge across the cut (S, V∖S), u ∈ S, v ∉ S, and let T be an MST without e. T is a tree, so T + e contains exactly one cycle, through e. The cycle goes from u ∈ S to v ∉ S and back, so it crosses the cut at least twice: besides e it uses another edge f across the cut. Weights are distinct and e is the lightest edge across the cut, so w(e) < w(f). Removing f breaks the cycle: T′ = T + e − f is connected, has V − 1 edges, so it is a spanning tree, and w(T′) = w(T) + w(e) − w(f) < w(T). That contradicts the minimality of T, so every MST contains e. ∎ (Exhaustively checked for all cuts of random 5-vertex graphs: test_the_lightest_edge_across_every_cut_is_in_the_minimum_spanning_tree.)

(b) Kruskal accepts e = {u, v} when u and v are in different trees. Let S be the tree that contains u (all vertices connected to u by accepted edges so far). Any edge e′ with one end in S and the other outside has not been accepted. If w(e′) < w(e), e′ was considered earlier, when its ends were in different trees (trees only grow, and the ends are in different trees now, so they were then), so it would have been accepted, joining its ends: contradiction. So e is the lightest edge across the cut (S, V∖S), and by (a) it belongs to the MST (test_every_edge_kruskal_accepts_is_the_lightest_edge_leaving_its_own_component). Every accepted edge joins two different trees, so the accepted edges never form a cycle; a rejected edge has both ends in the same tree, so when the list is used up every edge's ends are connected: the accepted edges connect the graph, form no cycle, and are V − 1 in number: a spanning tree consisting only of MST edges, i.e. the MST. ∎

(c) Edges across S = {A, D, F}: A-B 6, E-F 9, B-D 11, F-G 12, D-E 13. The lightest is A-B 6, so it belongs to the MST, and it is the fourth edge Kruskal accepts in video 4 (A-D 3, C-E 4, D-F 5, A-B 6, B-E 7, E-G 10: total 35).

DESIGNS

Exercise 4 · Shortest route when the vertices carry the weights. In a road network every town v charges a toll c(v) ≥ 0 each time you pass through it, the start and the destination included, and the roads themselves are free. The cost of a route is the sum of the tolls of all the towns on it. (a) Show how to turn this into an ordinary shortest-path problem with weights on the edges and then run Dijkstra's algorithm unchanged (or nearly). Which weight gets an arc u→v, and with what distance does the source start? Why is it important that tolls are not negative? (b) Use the example graph without its edge weights and the tolls A 1, B 5, C 2, D 1, E 3, F 4, G 1. Run your method by hand from A: which towns are settled in which order, and what is the cheapest route from A to G and its cost? Compare with the route BFS finds (the fewest edges) and with A D F G. (c) What changes if the toll is only paid when you leave a town? And if there were a toll for changing from road type to road type at a town? (A sentence each: what would the graph look like?)

Solution

(a) Give the arc u→v the weight c(v), the toll of the town you enter, and start Dijkstra at the source with distance c(source) (the start's toll is paid too). A route s = x₀, …, x_m then costs c(x₀) + Σ c(x_i) for i ≥ 1, exactly the sum of all the tolls. The arc weights are ≥ 0 exactly when the tolls are, and non-negative weights are what the invariant of Exercise 2 needs. (ex9_designs.py: cheapest_route_with_tolls.)

(b) Distances: A = 1 settled first. A relaxes B = 1 + 5 = 6 and D = 1 + 1 = 2. D (2) is settled: E = 2 + 3 = 5, F = 2 + 4 = 6 (B stays 6). E (5): C = 5 + 2 = 7, G = 5 + 1 = 6 (F stays 6). Then B, F and G (all 6; with ties broken by the letter, G is settled last of the three), then C (7). The route is A D E G, cost 1 + 1 + 3 + 1 = 6. BFS (fewest edges, alphabetical) finds A B E G, which costs 1 + 5 + 3 + 1 = 10, and A D F G costs 1 + 1 + 4 + 1 = 7. Both A D E G and A D F G have three edges, and A B E G also: BFS cannot tell them apart, tolls can (test_tolls_reduce_to_edge_weights, and against brute force on 200 random graphs).

(c) Toll paid when you leave a town: arc u→v gets weight c(u) and the source starts at 0; the destination's own toll is never paid (the route cost is the sum of the tolls of all towns except the last). A cost for changing road type at a town is not a property of a vertex or of an edge alone but of a pair of consecutive edges: make a vertex for every pair (town, road type you arrived by), with arcs between the pairs at the same town costing the change: the graph gets bigger (V × types vertices) but Dijkstra is again unchanged.

Exercise 5 · Finding a cycle in a directed graph. A directed graph is given as the list of out-neighbours of each vertex. Decide whether it contains a cycle and, if it does, return one. (a) The undirected test of video 2 ("skip the vertex we came from; any other vertex we have already seen means a cycle") gives a wrong answer for the directed graph A→B, A→C, B→C. Explain why, and give the rule that is correct for directed graphs: three states for a vertex (not started, being explored, finished) and what must be found. (b) Write the algorithm in pseudocode so that it returns the cycle as a list of vertices (hint: remember the DFS parent of every vertex), state its running time, and say why the answer is correct in both directions (cycle found ⇒ cycle exists, no cycle found ⇒ none exists). (c) Run it on A→B→C→A and on A→B, A→C, B→C. Which arc is the "back" arc in the first?

Solution

(a) In A→B, A→C, B→C, DFS from A reaches B, then C (via B), finishes C and B, and goes back to A, where it meets C again through the arc A→C. C is "already seen", so the undirected rule says "cycle". But C is finished: nothing leads back from C to A, so it is not a cycle: in a directed graph two different routes to the same vertex are fine (test_undirected_trick_does_not_work_for_directed_graphs). The correct rule: colour every vertex white (not started), gray (the call is still running, i.e. it is on the current DFS path) or black (finished). A cycle exists exactly when an arc leads from the vertex being explored to a gray vertex (a "back arc").

(b) visit(u): colour u gray; for each arc u→v: if v is gray, return the cycle: follow parent from u back to v, reverse it; if v is white, set parent[v] = u and visit(v), returning a cycle found there; finally colour u black. Start visit from every white vertex. Each vertex and arc is handled once: O(V + E). Back arc found ⇒ cycle: v is gray, so v is an ancestor of u on the DFS path, and the path from v down to u plus the arc u→v is a cycle. Cycle exists ⇒ found: take a cycle and let x be the first of its vertices that DFS starts. At that moment all other vertices of the cycle are white and connected to x by a path of white vertices, so all of them become descendants of x (the white-path theorem): visit(x) has not returned while they are explored, so x is gray when the last vertex of the cycle looks at its arc back to x. (Checked against Kahn's algorithm, which removes vertices without incoming arcs, on 500 random digraphs, and the returned cycle is verified arc by arc: test_found_cycle_is_a_real_cycle_and_agrees_with_kahn.)

(c) A→B→C→A: visit(A) colours A gray, B gray, C gray; the arc C→A goes to a gray vertex: the back arc; the cycle is [A, B, C]. A→B, A→C, B→C: C is finished (black) when the arc A→C is looked at, no back arc, no cycle.

IMPLEMENTATIONS (WITH MILESTONES)

Templates and tests · Python (.zip)Templates and tests · Java (.zip)

Each file lists its milestones at the top. Do them in order and run the tests after each one.

Exercise 6 · BFS with levels and parents — ex9_bfs.pyEx9Bfs.java. Implement bfs(graph, start) returning the visit order, the level (number of edges from the start) and the parent of every reachable vertex. The tests check the order, levels and parents of the example graph from A, compare the levels with a brute-force (Floyd–Warshall) computation on random graphs, and count how often a vertex's adjacency list is fetched: exactly once per reachable vertex, also on a complete graph of 40 vertices where a search that forgets to mark vertices in time makes the queue explode.

Solution

The reference solution (solutions/py/ex9_bfs.py, solutions/java/Ex9Bfs.java) is the textbook loop: put start in the queue with level 0, parent None; take the front vertex u, append it to the order, and for every neighbour v that has no level yet set level[v] = level[u] + 1, parent[v] = u and enqueue it. The test "lookups == V" fails for the version that marks a vertex when it is taken out of the queue (that version puts a vertex into the queue once for every neighbour processed before it, so on the complete graph of 40 vertices it makes 781 insertions (1 + 40 · 39 / 2) instead of 40 and, worse, reports levels up to 39 where every vertex is one edge from the start: see Exercise 9).

Exercise 7 · Routes from parents, and counting them — ex9_paths.pyEx9Paths.java. path_from_parents follows the parents back from the target; shortest_path runs the search and returns a route with the fewest edges (or nothing); count_shortest_paths returns, for every reachable vertex, the number of different routes with the fewest edges, in a single BFS (hint: add the count of u to every neighbour one level further away). The tests include the example graph from A (G is reached in 3 different ways) and compare with a brute force over all simple routes of random graphs.

Solution

path_from_parents follows parent from the target back to the start and reverses the list; None if the target has no parent entry. shortest_path is the BFS plus that. count_shortest_paths keeps ways[v]: when u is taken out and a neighbour v is one level further (level[v] == level[u] + 1, either just discovered or discovered earlier), ways[v] += ways[u], since every shortest route to u extends to a shortest route to v and every shortest route to v arrives through such a u. On the example graph from A: A 1, B 1, D 1, C 1, E 2, F 1, G 3: E is reached as A B E and A D E, F only as A D F, G as A B E G, A D E G and A D F G, the three routes of Exercise 1(d).

Exercise 8 · Union-find — ex9_unionfind.pyEx9UnionFind.java. Implement find, union and connected, then union by size (the smaller tree hangs under the bigger one), then path compression. The tests merge 1,024 singletons in blocks of 1, 2, 4, 8, … and demand that the deepest vertex is at most 10 steps from its root, flatten a chain of 10 vertices with one find, and compare with a naive labelling on random operations.

Solution

find walks up to the root and counts the links it follows, then walks the path again and points every vertex on it straight at the root (path compression). union finds both roots, returns False if they are equal, otherwise hangs the root of the smaller tree under the other one (the first argument's root stays on a tie) and adds the sizes; sets goes down by one. With union by size a tree of n elements has depth at most log₂ n (an element's depth increases only when its tree is hung under a tree at least as big, so the tree at least doubles each time): 1,024 singletons merged in blocks of 1, 2, 4, 8, … give a deepest vertex exactly 10 steps from its root; on a chain 0→1→…→9, find(0) makes every vertex a direct child of 9 (depth ≤ 1), and a second find(0) follows one link.

READ THE CODE

An AI assistant wrote each piece of code together with a claim. In both exercises the claim is wrong because of a bug. Find a small input that shows it (compare with a brute-force answer), say what exactly goes wrong and why the small examples you first try do not show it, and fix it. Use the habits from the chapter: compare with a brute-force answer, try more than the smallest graphs, and count the work, not just the time.

Exercise 9 — bfs_levels_9 in read/py/ex9_read.py / Ex9Read.bfsLevels9 in read/java/Ex9Read.java. The comment claims that it returns the visit order and the number of edges from the start to every vertex, and that marking a vertex visited when it is taken from the queue is just as good as marking it when it is put in.

Solution

What is wrong. The visit order is right (the first time a vertex is taken out is the first time it was put in, so the order is a BFS order; checked for all graphs on up to 5 vertices). The levels are wrong: level[v] = level[u] + 1 runs every time a vertex is put in the queue, and because visited is only set when it is taken out, a vertex that is already in the queue gets its level overwritten by every later vertex that finds it. The first level written is right (d + 1); a later one is wrong whenever the later vertex is deeper than the first: whenever an edge joins two vertices of the same level. Smallest example: the triangle 0-1-2 from 0: true levels {0: 0, 1: 1, 2: 1}, reported {0: 0, 1: 1, 2: 2} (vertex 1 is taken out first and finds 2 not yet visited, which is already queued by 0). On the example graph from A the edge B-D joins two level-1 vertices and the damage spreads along the whole graph: reported A 0, B 1, D 2, C 2, E 3, F 4, G 5 instead of A 0, B 1, D 1, C 2, E 2, F 2, G 3 (test_the_triangle_is_the_smallest_failure_and_the_example_graph_fails).

Why small examples do not show it. The levels are wrong exactly when an edge joins two vertices of the same level in the true BFS, i.e. when the component of the start contains an odd cycle (checked for every graph on 3, 4, 5 vertices). So trees, paths, even cycles, grids and every bipartite graph give the right answer. Even among small graphs the bug is rare at first: 1 of the 8 graphs on 3 vertices, 22 of 64 on 4, 621 of 1,024 on 5, so a test with a path or a tree, or with an even number of vertices in a cycle, passes. A random test against brute-force distances catches it quickly. A second, smaller problem: the queue can hold a vertex several times, so it needs Θ(E) space instead of Θ(V).

Fix. Mark at discovery: set level[v] (and a parent) only if v not in level, and drop the visited set and the continue at the pop. Then every vertex is put in the queue once, with the right level, and the adjacency list of each vertex is read once.

Exercise 10 — Dijkstra10 in read/py/ex9_read.py / Ex9Read.Dijkstra10 in read/java/Ex9Read.java. The comment claims that it is Dijkstra's algorithm with a binary heap and lazy deletion, that every edge is examined once and so the cost is O((V + E) log V), and that the distances are exact. (scans counts the adjacency entries looked at.)

Solution

What is wrong. Nothing is checked when an entry is taken out of the heap, so a stale entry (a vertex that has since become cheaper and has already been settled) is processed again: its whole adjacency list is scanned once more, although no relaxation can succeed from it (its key is not smaller than the current distance). The distances are still exact, so a correctness test passes, but the claim "every edge is examined once, O((V + E) log V)" is false. On the example graph from A, the single stale entry (E with key 16) costs 5 extra scans: 27 instead of 22 = 2E (test_on_the_example_graph_the_stale_entry_costs_five_extra_scans). How bad can it get? Take a vertex S joined to u₁ … u_k (weights 1 … k) and every u_i joined to t₀ … t_{m−1} with weight 3k − 2i: each t_j gets a better distance from every u_i in turn, so it is pushed k times, and each of its k − 1 stale entries scans its k neighbours again. For k = m = 10 / 20 / 40 (E = 110 / 420 / 1,640): the buggy version makes 1,120 / 8,440 / 65,680 scans, the fixed one 220 / 840 / 3,280 (2E): about k/2 times more, i.e. Θ(V·E) instead of Θ(E) (test_the_cost_grows_like_V_times_E_instead_of_E).

Why small examples do not show it. On paths and trees no vertex is ever pushed twice, so there are no stale entries, the two versions do exactly the same work (a path of 20 vertices: 38 scans for both), and the distances are always right. Only a count of the work, not the answer, shows the problem: that is why the exercise gives you scans.

Fix. Skip stale entries: after taking out (d, u), if d > dist[u]: continue (or keep a set of settled vertices, as the chapter's code does).

§4Working with AI

When an AI writes a graph algorithm it usually also claims that it works and how fast it is. Treat both as hypotheses:

Test against a brute-force answer on small random graphs, and not only on trees. The BFS of Exercise 9 gets every tree, path, even cycle and grid right and fails exactly on graphs with an odd cycle (1 of the 8 graphs on 3 vertices, 22 of 64 on 4, 621 of 1,024 on 5). Compare the levels with Floyd–Warshall distances on random graphs: it finds the bug at once.
Count the work, not just the time. The Dijkstra of Exercise 10 returns exact distances, so a correctness test passes, but it scans edges up to k/2 times more than needed. Give the code a counter (as steps and scans do in this chapter's code), or run the doubling test of chapter 1: if the work grows faster than the claimed O((V + E) log V), the claim is wrong.
Ask when a vertex is marked. "Visited" must be set when the vertex is put on the frontier. The version that marks when it is taken off either loops for ever or gets the levels wrong.
Ask what the code assumes about the weights. An AI that says "Dijkstra" for a graph with negative edges, or "BFS" for a weighted graph, is answering a different question. Test the claimed route against the cheapest route found by Bellman–Ford.
Ask which tree it built. A minimum spanning tree and a shortest-path tree are different (35 against 41 on the example graph); "the MST gives the cheapest route" is false.
Check the directed case separately. The undirected cycle test ("any seen vertex other than the one we came from") reports a cycle in A→B, A→C, B→C, which has none; a directed graph needs the three states.

PITFALL · A stale-entry check is a performance bug, not a correctness bug.

Removing the if u in done: continue of Dijkstra leaves every answer right, which is exactly why nobody notices. Always look at the loop that takes an entry out of the heap.

§5Key terms and further reading

Terms: graph · vertex · edge · directed · undirected · weight · degree · path · cycle · connected · edge list · adjacency list · adjacency matrix · sparse · dense · frontier · BFS · level · parent · DFS · discovery time · finish time · tentative distance · settle · relax · lazy deletion · stale entry · shortest-path tree · Bellman–Ford · spanning tree · minimum spanning tree · cut property · Kruskal · Prim · union-find · union by size · path compression.

Further reading

Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd edition, MIT Press (ISBN 9780262033848): graph representations, breadth-first and depth-first search, minimum spanning trees, single-source shortest paths, and disjoint-set data structures.
MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020, lectures "Breadth-First Search", "Depth-First Search", "Weighted Shortest Paths", "Bellman-Ford" and "Dijkstra": https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes/.
Stanford CS166 Advanced Data Structures, lecture "Disjoint-Set Forests", for the full analysis of union-find: https://web.stanford.edu/class/cs166/.
AIE1001 Interactive Notes, Lecture 10 (stacks, queues, linked lists and trees, the introduction this course builds on): https://boxi-cs.github.io/aie1001/L10/.