Algorithms · Lecture Notes
Chapter 7: Minimum Spanning Trees
A company wants to connect several cities with power lines. Laying a line between any two cities has a cost. It is enough for every city to be reachable from every other; two cities need not be joined directly. Which lines should the company build to make the total cost as small as possible? In mathematics this question is the minimum spanning tree problem. The chapter first introduces spanning trees, minimum spanning trees, and the two properties on which every algorithm rests: the cut property and the cycle property. It then turns to four greedy algorithms that solve the same problem. Kruskal adds edges from lightest to heaviest, and Prim grows a tree from a single vertex. Borůvka grows all components at once, while reverse-delete removes heavy edges. The disjoint-set structure that Kruskal needs for its cycle test gets a detailed treatment of its own. For each algorithm the notes give Java code, a step-by-step trace, and a cost analysis, and they close by comparing the four.
Learning outcomes
- Concepts
- Define spanning trees and minimum spanning trees (MSTs); explain and justify why a spanning tree has V − 1 edges, and state the cut and cycle properties.
- Kruskal and disjoint sets
- Sort the edges and keep those that do not form a cycle; perform the cycle test with disjoint sets (find / union); trace the effect of path compression and union by rank.
- Prim
- Grow the tree from one vertex; trace the key and parent arrays step by step, both with an array scan and with a priority queue; explain how Prim differs from Dijkstra.
- Borůvka, reverse-delete, and analysis
- Apply component-based and deletion-based approaches; compare the complexity of the four algorithms and choose the one that suits the structure of the graph.
7.1Spanning trees and minimum spanning trees
Graphs are the common language of problems built on objects and the connections between them. The graphs in these notes are undirected: an edge between u and v can be used in both directions. They are also weighted: each edge carries a number, which may stand for the length of a cable, the cost of a road, or the difference between two points. The number of vertices is written V and the number of edges E. The same letters can also denote the vertex and edge sets, depending on context, as in the notation G = (V, E).
The notion of a tree is already familiar from binary search trees and heaps. There a tree is a rooted data structure. In graph theory a tree is a more general object: every connected, acyclic undirected graph is a tree. There is no root and no limit on the number of children. Between any two vertices of a tree there is exactly one path. If there were no path the graph would not be connected; if there were two different paths, together they would form a cycle.
7.1.1The problem
By deleting some edges from a connected graph we can obtain a subgraph that still connects all the vertices but contains no cycle. Such a subgraph “spans” all the vertices of the graph.
Let G = (V, E) be a connected, undirected graph. A spanning tree of G is a connected, acyclic subgraph of G that contains all of its vertices. A spanning tree uses only edges that exist in G.
The number of edges in a spanning tree is determined exactly by the number of vertices. Every algorithm in this chapter uses this fact in its stopping condition.
Every tree on V vertices has exactly V − 1 edges. Adding a new edge to a tree creates exactly one cycle; deleting an edge from a tree splits it into two pieces.
Start with V vertices and no edges, so there are V separate pieces. Add the edges of the tree one at a time. If an edge joined two vertices of the same piece, a cycle would form, because a path between them already exists; a tree has no cycle, so this cannot happen. Hence every edge joins two different pieces and reduces the number of pieces by exactly one. At the end the tree is connected, so one piece remains. Going from V pieces down to one takes V − 1 edges. For the second claim, consider the unique path between u and v in the tree: the new edge (u, v) forms a cycle together with this path. When an edge is deleted, no other path remains between its endpoints, so the tree falls into two pieces. □
A graph usually has many spanning trees. When the edges are weighted, the total weights of these trees differ as well. What we are really after is the tree whose total is smallest.
In a connected, undirected graph with edge weights w(u, v), the weight of a spanning tree is the sum of its edge weights: w(T) = Σ(u,v) ∈ T w(u, v). A spanning tree of smallest weight is called a minimum spanning tree (MST).
The word “minimum” describes the total weight, not the tree itself. Since every spanning tree has V − 1 edges, there is no search for a tree with fewer edges. Trees differ only in which edges they choose. Figure 7.1 shows a small graph on five vertices and its minimum spanning tree.
The graph in the figure has seven edges. A spanning tree uses four edges to connect five vertices; three edges are left out. The four bold edges form a tree: from a one can reach e and b, from b one can reach c, and from c one can reach d, and there is no cycle. Each of the omitted edges be = 4, ec = 6, and ed = 7 would close a cycle if added to the tree. For example, adding be creates the cycle b → a → e → b.
Thinking of the MST as the “V − 1 lightest edges.” The four lightest edges in the figure are ae = 1, cd = 2, ab = 3, and be = 4, with total weight 10. But these four edges do not form a tree: they close a cycle among a, b, e, and {a, b, e} and {c, d} are never joined. The chosen edges must be both acyclic and connected, and that is where the real difficulty lies.
7.1.2How many spanning trees are there?
The crudest way to find an MST is to build every spanning tree, one by one, and compare their weights. The number of spanning trees shows why this does not work. A graph in which every pair of vertices is joined by an edge is called a complete graph. In 1889 Arthur Cayley showed that the complete graph on n vertices has exactly nn−2 spanning trees, a result known as Cayley's formula.
| n | Number of spanning trees |
|---|---|
| 3 | 3 |
| 4 | 16 |
| 5 | 125 |
| 10 | 100,000,000 |
| 15 | about 1.95 · 1015 |
The complete graph on four vertices has six edges, and a spanning tree uses three of them. Three edges can be chosen from six in C(6, 3) = 20 ways. Four of these selections are triangles: any three of the four vertices form a cycle and leave the fourth vertex out. Every other selection of three edges is acyclic and connects all four vertices. The number of spanning trees is therefore 20 − 4 = 16, and Cayley's formula gives 44−2 = 16 as well.
In a complete graph on fifteen vertices the number of spanning trees is in the quadrillions. Trying every tree is impractical even for small graphs. A graph that is not complete has fewer spanning trees, but the count still grows quickly: the seven-edge graph in Figure 7.1 has 21 spanning trees. Their weights range from 11 to 21, and only one tree has weight 11. Fortunately, finding the MST does not require counting trees. The problem is solved directly by greedy algorithms, which at each step make the choice that looks best locally. The cut and cycle properties explain why the greedy approach gives a correct answer here.
7.1.3An example: the “MST” graph
A larger example helps show which edges a spanning tree selects and which it leaves out. The graph in Figure 7.2 draws the letters M, S, and T. It has 15 vertices and 20 edges.
There are 14 bold edges, which equals V − 1 = 15 − 1. The total weight is computed as follows:
2 + 2 + 5 + 10 + 7 + 8 + 10 + 11 + 4 + 1 + 20 + 25 + 24 + 12 = 141
The six thin edges that are left out share a property. Each of them closes a cycle together with bold edges, and it is the heaviest edge of that cycle. The edge of weight 15 above the letter M forms a triangle with the two diagonal edges of weight 2; the heaviest edge of the triangle is 15. The edge of weight 16 below the M closes a cycle with the two legs (5 and 10) and the two diagonals (2 and 2). The thin edge of weight 25 at the lower left of the S closes a cycle with bold edges of weight 11, 1, and 4. In every case the other edges of the cycle keep the connection intact in place of the thin edge, and they are cheaper.
Some heavy edges, on the other hand, are in the tree: 20, 24, and the 25 between S and T. None of these is the heaviest edge of any cycle. For example, the edge of weight 40 that runs from the lower right of the S to the upper right end of the T closes a long cycle. The edges of weight 20, 25, and 24 are also on this cycle, but the heaviest edge of the cycle is 40. Likewise, the edge of weight 50 forms a triangle with 24 and 12. The graph also has a bridge: deleting the edge of weight 7 that joins M and S would split the graph into two pieces. A bridge lies on no cycle, so it must be in every spanning tree and therefore in every MST.
Explaining the presence of a heavy edge in the tree by saying “this edge is the only way to reach that vertex.” The bold edges of weight 20, 24, and 25 in the figure are not bridges; the graph stays connected if any one of them is deleted. They are in the tree because every cycle that contains them also contains a heavier edge (40 or 50). An edge's weight alone says nothing; what matters is its position in cycles and cuts.
7.1.4The cut property
All MST algorithms rest on two simple observations. The first concerns splitting the vertices into two groups.
A cut of a graph is a partition of its vertex set into two nonempty parts, written (S, V − S). An edge with one endpoint in S and the other in V − S is said to cross the cut. Among the edges crossing a cut, the one of smallest weight is the cut's lightest edge.
For every cut, the lightest edge crossing the cut belongs to some MST. If the lightest crossing edge is unique, it belongs to every MST.
Let e = (u, v) be the lightest edge crossing the cut, with u ∈ S and v ∈ V − S. Let T be an MST that does not contain e. Since T is a spanning tree, it contains a path from u to v. This path starts in S and ends in V − S, so it crosses the cut at least once. Call the edge where it crosses f. Deleting f from T and adding e gives a new tree T′. Deleting f splits the tree into two pieces, one containing u and the other containing v, and e reconnects them. So T′ is also a connected spanning tree with V − 1 edges. Its weight is w(T′) = w(T) − w(f) + w(e). Since e is the lightest edge of the cut, w(e) ≤ w(f), and therefore w(T′) ≤ w(T). Because T is minimal, so is T′, and it contains e. If e is the unique lightest edge, then w(e) < w(f) and w(T′) < w(T), a contradiction; so no MST avoids e. □
The idea of this proof is called an exchange argument. Take an optimal solution that does not contain the greedy choice. Modify one part of it, and it becomes a solution that contains the choice and is at least as good. The same idea underlies the correctness proofs of most greedy algorithms.
Several cuts of the graph in Figure 7.1 can be examined.
- {a, b} | {c, d, e}: the crossing edges are ae = 1, be = 4, bc = 5. The lightest is ae, which is in the MST.
- {d} | {a, b, c, e}: the crossing edges are cd = 2 and ed = 7. The lightest is cd, which is in the MST.
- {a, b, e} | {c, d}: the crossing edges are bc = 5, ec = 6, ed = 7. The lightest is bc. This edge is not among the lightest edges of the graph, yet it enters the MST.
The cut property speaks only about edges that cross the cut. The edge ab = 3 does not cross the first cut, so that cut says nothing about ab. That ab is in the MST is shown by another cut: the edges crossing {b} | {a, c, d, e} are ab = 3, be = 4, and bc = 5, and the lightest is ab.
7.1.5The cycle property
The second observation is in a sense the reverse of the cut property. The cut property tells us which edge can safely be chosen; the cycle property tells us which edge can safely be discarded.
If the heaviest edge of some cycle in the graph is unique, that edge is in no MST.
Let f = (u, v) be the unique heaviest edge of a cycle C, and suppose an MST T contains f. Deleting f from T splits the tree into two pieces, with u in one and v in the other. The edges of C other than f form a path from u to v. Since this path passes from one piece to the other, at least one of its edges, say e, joins the two pieces. Then T − f + e is again a spanning tree, and because w(e) < w(f), its weight is smaller than that of T. This contradicts the minimality of T. □
The cycle property carries a small caveat: the heaviest edge must be unique. If the largest weight in a cycle appears on two edges, one of them may be in an MST. For example, in a triangle with edge weights 1, 2, and 2, one of the edges of weight 2 is always chosen. In such a case the property says only this: there is an MST that omits one of the heaviest edges.
Together the two properties give the skeleton of the algorithms. Table 7.2 summarizes which algorithm uses which property.
| Property | What it says | Algorithms that use it |
|---|---|---|
| Cut property | The lightest edge crossing a cut can safely be added. | Kruskal, Prim, Borůvka |
| Cycle property | The heaviest edge of a cycle can safely be discarded. | Reverse-delete |
7.1.6When is the MST unique?
A graph can have more than one minimum spanning tree. This requires edges of equal weight. In a triangle with edge weights 1, 2, and 2, the edge of weight 1 together with either edge of weight 2 forms an MST. Both trees have weight 3. If all weights are distinct, no such freedom of choice remains.
If all edge weights of a connected graph are distinct, the MST is unique.
Let T be an MST and e any edge of T. Deleting e from T splits the vertices into two pieces, which define a cut. The only edge of T crossing this cut is e. If some crossing edge e′ were lighter than e, then T − e + e′ would be a lighter spanning tree, which is impossible. Since the weights are distinct, e is the unique lightest edge of this cut. By the cut property, e is in every MST. This holds for all edges of T. So every MST contains the V − 1 edges of T and has exactly V − 1 edges itself; hence every MST equals T. □
The converse of the theorem is false: a graph with equal-weight edges can still have a unique MST. The weights in Figure 7.1 are already distinct, so that graph has a single MST. When equal-weight edges are present, different algorithms, or even the same algorithm with a different edge order, may find different trees. The total weight of the trees found is always the same.
7.1.7Greedy MST algorithms
The cut property suggests a general method. At the start no edge is chosen. The chosen edges are grown so that at every moment they are part of some MST. At each step, find a cut that none of the chosen edges crosses, and add the lightest edge of that cut. Such an edge is called a safe edge: once it is added, the chosen set is guaranteed to be extendable to an MST. After V − 1 safe edges have been added, the tree is complete.
The four classical algorithms are different implementations of this general method. All of them are greedy: at each step they choose the locally best edge or discard the worst, and this decision is never revisited.
| Algorithm | Idea | Helper structure | Time |
|---|---|---|---|
| Kruskal (1956) | Sort the edges from lightest to heaviest and add those that do not form a cycle | disjoint sets | O(E log E) |
| Prim (1957) | Start at one vertex and grow the tree by the cheapest adjacent edge | priority queue | O((V + E) log V) |
| Borůvka (1926) | Every component adds its own cheapest edge simultaneously | disjoint sets | O(E log V) |
| Reverse-delete | Try the edges from heaviest to lightest and delete any whose removal keeps the graph connected | BFS/DFS or disjoint sets | O(E · (V + E)) |
All four algorithms find an MST of the same weight. If the weights are distinct, they find the same tree, because the MST is unique. They differ in the order in which they consider the edges and in the data structure they need. Kruskal and Borůvka work with a forest, that is, with several trees. Prim keeps a single tree at all times. Reverse-delete starts from the whole graph and thins it out. The years in the table are interesting too: the oldest algorithm is Borůvka's, written before computers existed, for a power-grid problem.
7.1.8Applications
The MST is not a theoretical curiosity; it is either the whole of many engineering problems or one step in them.
- Network design. Connecting cities, buildings, or devices with as little cable as possible is directly an MST problem. Electricity, water, fiber-optic, and road networks fall into this class. Borůvka's 1926 work also started from the electrical network of Moravia.
- Clustering. Treat the points as vertices and the distances between them as weights. If the k − 1 heaviest edges are deleted from the MST, k pieces remain and each piece is a cluster. This method is called single-linkage clustering. In the nine-vertex Kruskal example, deleting the two heaviest edges of the MST yields the clusters {A, B}, {C, D, E, F, H}, and {G, I}.
- Approximation algorithms. In the metric traveling salesman problem (TSP), a tour obtained by a depth-first traversal of the MST that skips repeated vertices is at most twice as long as the best tour. An exact solution of the TSP is very expensive, whereas the MST is found quickly.
- Image processing. Pixels are vertices, and the color difference between neighboring pixels is the weight. MST-based methods segment an image by grouping regions of similar color together.
- Circuit design. Connecting the pins of a chip that must be wired together with the least total conductor length is a preliminary step of VLSI routing.
- Other graph problems. Among the paths between two vertices, the one whose heaviest edge is lightest is called the bottleneck path. The path between two vertices in an MST is always such a path. The MST is also a basic approximate solution for the Steiner tree problem.
7.2Kruskal's algorithm
Kruskal's algorithm gives the most natural answer to the MST problem: take the cheapest edges first, as long as they do not form a cycle. Joseph Kruskal published it in 1956 in a short paper related to the traveling salesman problem. The idea of the reverse-delete algorithm appears in the same paper.
7.2.1The idea: merging a forest
At the start every vertex is a tree by itself; the graph is a forest of V trees. The edges are sorted from lightest to heaviest and examined in that order. If the edge under examination connects vertices of two different trees, it is added and the two trees merge. If both endpoints are already in the same tree, adding the edge would create a cycle, so it is skipped. Each addition reduces the number of trees by one. After V − 1 additions a single tree remains and the algorithm stops.
In the intermediate state shown, there are two trees, {a, b, c} and {d, e, f}. The next edge is bc = 4. A path b → a → c already exists between b and c; adding bc would close a cycle with this path. The following edge, bd = 5, connects two separate trees and is added. At this point the forest becomes a single tree.
A brief assessment of the algorithm follows. Kruskal is well suited to sparse graphs, where the number of edges is close to the number of vertices. Its code is simple: an edge list and a disjoint-set structure are enough. If the graph is not connected, the algorithm produces a separate tree for each component, that is, a minimum spanning forest. It also has weak points. Sorting the edges costs O(E log E). On dense graphs, where the number of edges approaches V2, the array-scan version of Prim can be faster. An extra structure is needed for the cycle test.
7.2.2Steps and pseudocode
The steps of the algorithm are as follows:
- Sort all the edges of the graph in increasing order of weight.
- From the sorted list, take the next edge of smallest weight.
- If the edge joins two vertices that belong to different trees, add it to the tree and merge the two trees.
- If the edge connects two vertices of the same tree, it would form a cycle and is skipped.
- Repeat steps 2–4 until V − 1 edges have been chosen (or the edges run out).
KRUSKAL(G):
MST = [ ]
disjointSet.create(V)
edges.sort(by ascending weight)
for each (u, v, weight) in edges:
if disjointSet.find(u) ≠ disjointSet.find(v):
MST.add((u, v, weight))
disjointSet.union(u, v)
return MSTThe only mysterious part of the pseudocode is the comparison disjointSet.find(u) ≠ disjointSet.find(v). find returns a representative that says which tree a vertex is in. If the representatives of the two endpoints differ, the edge connects two separate trees. union gathers two trees into one. The question “are these two vertices in the same tree?” is answered by the disjoint-set structure in nearly constant time. The structure is treated in detail in the next section.
7.2.3A worked example
Kruskal is applied to the five-vertex graph of Figure 7.1. The edges of the graph are ab = 3, ae = 1, bc = 5, be = 4, cd = 2, ed = 7, and ec = 6.
- Start. Every vertex is a separate tree: {a} {b} {c} {d} {e}. No edge is chosen, w(T) = 0.
- Sorting. The edges are arranged by increasing weight: ae 1, cd 2, ab 3, be 4, bc 5, ec 6, ed 7.
- ae = 1. a and e are in different trees, so the edge is added. The trees are {a, e} {b} {c} {d}, w(T) = 1.
- cd = 2. c and d are in different trees, so the edge is added. The trees are {a, e} {c, d} {b}, w(T) = 3.
- ab = 3. a and b are in different trees, so the edge is added. The trees are {a, b, e} {c, d}, w(T) = 6.
- be = 4. b and e are already in the same tree. Adding the edge would create the cycle b → a → e → b, so it is skipped.
- bc = 5. b and c are in different trees, so the edge is added. One tree remains: {a, b, c, d, e}, w(T) = 11.
V − 1 = 4 edges have been chosen, so the algorithm stops. There is no need to look at ec = 6 and ed = 7. The result is the tree of Figure 7.1.
The only edge rejected in the trace is be. It is the fourth-lightest edge of the graph in Figure 7.1. Kruskal skips it not because of its weight but because of its position: b and e are already connected by two cheaper edges.
Performing the cycle test by asking “is there a chosen edge between u and v?” In the example, at the step be no edge between b and e has been chosen; yet the two are connected through a, and be closes a cycle. The right question is “are u and v in the same component?” The length of the path between them is irrelevant.
7.2.4Why is Kruskal correct?
On a connected graph, the edges chosen by Kruskal's algorithm form a minimum spanning tree.
We show that every edge the algorithm adds is safe. When Kruskal decides to add an edge e = (u, v), the vertices u and v are in different trees. Let S be the tree of u and consider the cut (S, V − S). None of the chosen edges crosses this cut, because S is an entire tree. Every edge that crosses the cut joins two different trees, so none of these edges was skipped earlier on the grounds of forming a cycle. If a cut edge lighter than e existed, it would come before e in the sorted list and, since it joined two different trees at that moment as well, it would have been added. Hence e is the lightest edge of the cut and is safe by the cut property. The skipped edges, on the other hand, form cycles and so cannot belong to any tree. Since the graph is connected, V − 1 edges are chosen in the end, and they form an MST. □
If the weights are distinct, the sorted edge list is unique and Kruskal always finds the same tree. When there are equal-weight edges, the sort may arrange them in different orders. In that case the resulting tree may change, but its weight does not: the proof holds for whichever order is chosen.
7.3Disjoint sets (union-find)
The speed of Kruskal depends on how quickly the question “are two vertices in the same tree?” can be answered. Searching for a path with BFS or DFS for every edge takes O(V) and raises the total cost to O(E · V). The disjoint-set structure answers the same question in practically constant time.
7.3.1Structure and operations
A disjoint-set (union-find) structure maintains a collection of non-overlapping sets and offers three operations:
create(V): every element forms its own singleton set.find(x): returns the representative of the set containing x. The same representative is returned for all elements of one set.union(x, y): merges the sets containing x and y into one.
The most common representation is a forest. Each set is a tree, and the root of the tree is the representative of the set. The forest is stored in a single parent array (parent[] in the code): parent[i] is the parent of i, and at a root parent[r] = r. These trees have nothing to do with the MST itself. They carry only the information “who is in which set?”, and their shapes may differ from the edges of the graph.
create(V) writes parent[i] = i for every vertex. find(x) follows parent links up to the root and returns the root. union(x, y) finds the two roots and attaches one under the other. In Kruskal the usage is as follows: if find(u) == find(v), then u and v are in the same tree and the edge would close a cycle. The Java code from the slides is:
int find(int[] parent, int i) {
if (parent[i] != i)
parent[i] = find(parent, parent[i]); // path compression
return parent[i];
}
void union(int[] parent, int x, int y) {
parent[find(parent, x)] = find(parent, y);
}find is recursive. If parent[i] == i, then i is a root and is returned itself. Otherwise the root of the parent is found recursively, and on the way back the root found is written into parent[i]. Besides the method's main job of finding the root, this assignment has a side effect: every vertex on the path is attached directly to the root. This improvement is called path compression. union is a single line: the parent of the root of x is set to the root of y. If the two elements are already in the same set, both calls to find return the same root and the assignment points the root at itself; the structure does not change.
7.3.2The cycle test in Kruskal
How disjoint sets work inside Kruskal is traced on a five-vertex graph. The edges are sorted: ac 1, de 2, ab 3, bc 4, bd 5, cd 6, ce 7. For every accepted edge (u, v), parent[find(u)] = find(v) is applied.
| Edge | find(u) | find(v) | Decision | parent |
|---|---|---|---|---|
| start | — | — | — | a b c d e |
| ac = 1 | a | c | add, parent[a] = c | c b c d e |
| de = 2 | d | e | add, parent[d] = e | c b c e e |
| ab = 3 | c | b | add, parent[c] = b | c b b e e |
| bc = 4 | b | b | same root: cycle, skip | c b b e e |
| bd = 5 | b | e | add, parent[b] = e | c e b e e |
At the step ab, find(a) first climbs from a to its parent c. Since c is a root, the root c is returned. find(b) returns b itself. The roots differ, so the edge is added and the root c is attached under b. At the step bc, find(b) = b, and find(c) also reaches b along the path c → b. The roots are the same, so the edge would close a cycle. When four edges have been chosen, the MST is complete: ac + de + ab + bd = 1 + 2 + 3 + 5 = 11.
find(a) reaches the root in 3 steps.The MST is found correctly, but the disjoint-set forest has turned into a long chain. A call to find(a) follows the path a → c → b → e. This is where path compression comes in. As find(a) returns, it attaches every vertex on the path directly to the root: parent[a] = parent[c] = e. Vertex b is already attached to the root. Later lookups finish in one step.
find(a): the vertices a and c on the path are attached directly to the root e, and the parent array becomes e e e e e.7.3.3Code trace: find and union
How path compression plays out inside the recursion is traced step by step on a small example with elements 0, …, 4. The sequence of calls is union(0, 1), union(1, 2), union(2, 3), find(0), and union(4, 0).
| Step | Event | parent |
|---|---|---|
| 0 | start, every element is a root | [0, 1, 2, 3, 4] |
| 1 | union(0, 1): find(0) = 0, find(1) = 1 → parent[0] = 1 | [1, 1, 2, 3, 4] |
| 2 | union(1, 2): roots 1 and 2 → parent[1] = 2 | [1, 2, 2, 3, 4] |
| 3 | union(2, 3): roots 2 and 3 → parent[2] = 3 | [1, 2, 3, 3, 4] |
| 4 | find(0) descends: 0 → 1 → 2 → 3; 3 is a root | [1, 2, 3, 3, 4] |
| 5 | on return: parent[2] = 3 (unchanged) | [1, 2, 3, 3, 4] |
| 6 | on return: parent[1] = 3 | [1, 3, 3, 3, 4] |
| 7 | on return: parent[0] = 3; find(0) = 3 | [3, 3, 3, 3, 4] |
| 8 | union(4, 0): find(4) = 4, find(0) = 3 (one step) → parent[4] = 3 | [3, 3, 3, 3, 3] |
The first three unions produce a bad pattern. Each time one root is attached under the other, and the chain grows by one. find(0) now takes three steps. In general, if n elements are chained this way, a single find takes n − 1 steps. The call find(0) descends to the root recursively: first find(1) is called, then find(2), then find(3). find(3) finds the root and returns 3. As the recursion unwinds, each frame writes 3 into its own parent[i]. As a result 0, 1, and 2 are attached directly to 3. In the last union, find(0) finishes in one step and 4 goes under 3; all elements are in one set.
find(0): the vertices 0, 1, and 2 on the path are attached directly to the root 3.Writing union as parent[x] = y. This assignment attaches x itself to y; if x is not a root, x is cut off from its old tree, and the rest of that tree does not join the set of y. For example, with parent = [1, 1, 2], writing parent[0] = 2 merges 0 and 2 but leaves 1 outside. It is always the roots that must be linked: parent[find(x)] = find(y).
7.3.4Path compression and union by rank
The speed of disjoint sets depends on the height of the trees. Two improvements keep the height small. The first is the path compression seen above. The second chooses wisely, at union time, which root goes under which. Each root keeps a rank, an upper bound on the height of its tree. In a union, the root of smaller rank is attached under the root of larger rank. If the ranks are equal, one goes under the other and the rank of the new root increases by one. This method is called union by rank.
void unionByRank(int[] parent, int[] rank, int x, int y) {
int a = find(parent, x), b = find(parent, y);
if (a == b) return; // already one set
if (rank[a] < rank[b]) parent[a] = b; // shorter under taller
else if (rank[a] > rank[b]) parent[b] = a;
else { parent[b] = a; rank[a]++; } // tie: rank grows
}The code first finds the two roots; if they are the same there is nothing to do. If the ranks differ, the shorter tree goes under the taller one and no rank changes: the height of the taller tree does not grow. Only when two trees of equal rank are merged can the height grow by one, so the rank is increased only in that case. If the sequence of calls from the previous trace is repeated with this method, no chain forms. unionByRank(0, 1) finds equal ranks, attaches 1 under 0, and raises the rank of 0 to 1. In the later unions, 2, 3, and 4 are single-element trees of rank 0, and each goes under 0, whose rank is 1. The result is parent = [0, 0, 0, 0, 0], and the height of the tree stays at 1.
Under union by rank, a root of rank r has at least 2r elements in its tree. Hence in a structure of n elements every tree has height at most ⌊log2 n⌋, and a find takes O(log n) time.
We use induction. Initially every tree has one element and rank 0: 1 ≥ 20. When two trees of different ranks are merged, the rank of the new root does not change but its tree grows, so the inequality is preserved. When two trees of rank r are merged, the rank of the new root becomes r + 1. Each of the two trees has at least 2r elements, so the new tree has at least 2 · 2r = 2r+1 elements. Since the total number of elements is n, we get 2r ≤ n, that is, r ≤ log2 n. Because the height does not exceed the rank, the same bound holds for the height. □
The bound is tight. If 8 elements are merged in pairs, then in fours, then as one group of eight, always joining trees of equal rank, the rank reaches 3; with 1024 elements the same method brings the rank to 10. Adding path compression makes the structure much faster still. In 1975 Robert Tarjan showed that when both improvements are used together, the total cost of m operations is O(m · α(n)). Here α is the inverse of the very fast-growing Ackermann function. The inverse Ackermann function grows so slowly that α(n) ≤ 4 for every practical n not exceeding the number of atoms in the universe. For this reason the cost per operation is regarded as constant in the amortized sense. Amortized cost is the average cost per operation over a long sequence of operations. A single find can still take long, but that long walk speeds up the later calls.
Believing that path compression speeds up the single find call that performs it. The call that does the compression walks the whole long path itself. The gain comes in later calls: the vertices on the path are now one step from the root. The worst-case cost of a single operation and the amortized cost must therefore be assessed separately.
7.4Kruskal's code and complexity
7.4.1Java code
The Java implementation of Kruskal rests on an edge class. An edge holds its two endpoints and its weight. So that it can be sorted with Collections.sort, it implements the Comparable interface and compares edges by weight:
class Edge implements Comparable<Edge> {
int u, v, w; // endpoints and weight
Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
public int compareTo(Edge o) {
return Integer.compare(w, o.w); // ascending by weight
}
}Integer.compare(w, o.w) is the safe counterpart of the subtraction w − o.w. With very large or negative weights the subtraction can overflow; Integer.compare cannot. Vertices are numbered from 1 to V. The Kruskal code from the slides is:
void kruskal(int V, List<Edge> edges) {
Collections.sort(edges); // ascending
int[] parent = new int[V + 1];
for (int i = 1; i <= V; i++) parent[i] = i;
List<Edge> tree = new ArrayList<>();
int k = 0;
while (tree.size() < V - 1) {
Edge e = edges.get(k++);
int x = find(parent, e.u);
int y = find(parent, e.v);
if (x != y) { // different trees
tree.add(e);
parent[x] = y; // union
}
}
}The code works as follows, line by line. Collections.sort(edges) puts the edge list in ascending order of weight. Java's list sort is stable: edges of equal weight keep their original order in the list. The parent array has length V + 1 because vertices start at 1 and cell 0 is unused. The loop makes every vertex the root of its own set. tree holds the chosen edges, and k holds the index of the next edge in the sorted list.
The loop while (tree.size() < V - 1) runs until V − 1 edges have been chosen. In each round the next edge is taken and k increases by one. The roots of the two endpoints are found as x and y. If the roots differ, the edge is added to the tree and the two sets merge through parent[x] = y. union is not called here, because the roots have already been found; the assignment is made directly. If the roots are the same, nothing happens and the loop moves on to the next edge.
7.4.2Code trace: a five-vertex graph
The code is traced on a graph with vertices 1–5. The edges are (1,3) = 2, (2,5) = 2, (1,2) = 3, (2,3) = 4, (3,4) = 4, and (1,4) = 6.
Edge e | x = find(u) | y = find(v) | Action | parent | w(T) |
|---|---|---|---|---|---|
| — | — | — | init | [1, 2, 3, 4, 5] | 0 |
| (1,3) = 2 | 1 | 3 | add, parent[1] = 3 | [3, 2, 3, 4, 5] | 2 |
| (2,5) = 2 | 2 | 5 | add, parent[2] = 5 | [3, 5, 3, 4, 5] | 4 |
| (1,2) = 3 | 3 | 5 | add, parent[3] = 5 | [3, 5, 5, 4, 5] | 7 |
| (2,3) = 4 | 5 | 5 | cycle, skip | [3, 5, 5, 4, 5] | 7 |
| (3,4) = 4 | 5 | 4 | add, parent[5] = 4 | [3, 5, 5, 4, 4] | 11 |
In the third row, find(1) climbs to the parent of 1, which is 3, and returns 3; find(2) returns 5. The roots differ, and parent[3] = 5 merges the two trees. Note that the cell that changes is not that of 1 or 2 but that of the root 3. In the fourth row, find(2) and find(3) both find 5; since (2,3) does not join two separate trees, it forms a cycle and is skipped. In the fifth row, 4 is alone; (3,4) is added and parent[5] = 4. Now tree.size() is 4 = V − 1, and the loop ends. The edge (1,4) = 6 is never examined. The MST consists of the edges (1,3), (2,5), (1,2), and (3,4), and w(T) = 11.
The trace contains two pairs of equal-weight edges: (1,3) and (2,5), and (2,3) and (3,4). A stable sort leaves them in their list order. Had (3,4) come before (2,3) in the list, (3,4) would have been added first, and since the tree is complete with four edges, (2,3) would never have been examined. In this graph the result would not change. The reason (2,3) is skipped is that the path 2 → 1 → 3 has already been built from cheaper edges.
7.4.3A nine-vertex example
As a larger example, consider a graph with vertices A, …, I and 15 edges. The sorted edges are:
EF 1, CF 1, DE 2, FH 3, AB 4, EH 5, GI 5, DG 6, AC 7, BD 9, EG 10, BC 11, HI 12, EI 15, BF 20
| Edge | Decision | Sets (singletons omitted) | Total |
|---|---|---|---|
| EF 1 | add | {E, F} | 1 |
| CF 1 | add | {C, E, F} | 2 |
| DE 2 | add | {C, D, E, F} | 4 |
| FH 3 | add | {C, D, E, F, H} | 7 |
| AB 4 | add | {C, D, E, F, H} {A, B} | 11 |
| EH 5 | cycle (E–F–H) | unchanged | 11 |
| GI 5 | add | {C, D, E, F, H} {A, B} {G, I} | 16 |
| DG 6 | add | {C, D, E, F, G, H, I} {A, B} | 22 |
| AC 7 | add | {A, B, C, D, E, F, G, H, I} | 29 |
The ninth edge examined is AC = 7, and it is the eighth edge added. Since 8 = V − 1, the algorithm stops here; the last six edges, beginning with BD 9, are never examined. The weight of the MST is 29. This tree is also the source of the clustering example mentioned under applications. The two heaviest MST edges are AC = 7 and DG = 6. Deleting these two edges leaves three clusters: {A, B}, {C, D, E, F, H}, and {G, I}.
7.4.4Complexity
The cost of Kruskal is computed by splitting it into its operations. Table 7.8 gives how many times each operation is performed and what it costs.
| Action | Times | Cost |
|---|---|---|
| Sorting the edges by weight | 1 | O(E log E) |
create(V) | 1 | O(V) |
find (2 per edge) | ≤ 2E | O(E · α(V)) with path compression + rank; O(E log V) with rank only |
union | V − 1 |
The total is O(E log E), and the sorting determines this cost. In a connected graph E ≥ V − 1, so the O(V) initialization is also small next to the sort. Most sources write the same bound as O(E log V). The two forms denote the same order. In a simple undirected graph E ≤ V(V − 1)/2 < V2. Taking logarithms gives log E < 2 log V. Since constant factors do not change the order, O(E log E) = O(E log V). For example, in a complete graph with V = 1000 vertices, E = 499,500; log2 E ≈ 18.9 and 2 log2 V ≈ 19.9.
The situation changes if the edges already arrive sorted or if the weights are small integers. In the second case, counting sort sorts the edges in linear time. In these cases the total time is nearly linear: O(E · α(V)). If disjoint sets use only union by rank, each operation takes O(log V) in the worst case; with path compression added, the amortized cost per operation drops to O(α(V)). In both cases the sort dominates the total. The code from the slides does only path compression and uses no rank. This code is also known to be very fast in practice.
The memory requirement is that of the edge list and the parent array: O(V + E). The edge list is the input itself; the extra memory is the parent array and the V − 1 chosen edges.
7.4.5A disconnected graph
The code from the slides assumes the graph is connected. In a disconnected graph, V − 1 edges can never be chosen. When the list runs out, the loop condition is still true and edges.get(k++) runs past the end of the list.
Let V = 6 and the edges be (1,2) = 2, (2,3) = 3, (4,5) = 1, (5,6) = 4, (4,6) = 5. The graph has two components: {1, 2, 3} and {4, 5, 6}. The sorted list is (4,5), (1,2), (2,3), (5,6), (4,6). The first four edges are added; (4,6) forms a cycle and is skipped. Since tree.size() = 4 < 5, the loop continues, and the call edges.get(5) throws an IndexOutOfBoundsException.
The fix is to add the list bound to the loop condition. If tree.size() < V − 1 at the end, the graph is not connected. In that case the chosen edges form a minimum spanning forest: one minimum spanning tree for each component.
List<Edge> kruskalForest(int V, List<Edge> edges) {
Collections.sort(edges);
int[] parent = new int[V + 1];
for (int i = 1; i <= V; i++) parent[i] = i;
List<Edge> tree = new ArrayList<>();
int k = 0;
while (k < edges.size() && tree.size() < V - 1) {
Edge e = edges.get(k++);
int x = find(parent, e.u), y = find(parent, e.v);
if (x != y) { tree.add(e); parent[x] = y; }
}
return tree; // a forest if tree.size() < V - 1
}On the graph of the example, this version returns the edges (4,5), (1,2), (2,3), (5,6). The forest has two trees and total weight 1 + 2 + 3 + 4 = 10. The number of edges is V − 2. In general, a spanning forest of a graph with c components has V − c edges.
7.5Prim's algorithm
Kruskal works with small trees spread across the whole graph. Prim starts with a single tree and grows it step by step. The algorithm became known through Robert C. Prim's 1957 paper. Vojtěch Jarník had found the same method in 1930, and Edsger W. Dijkstra rediscovered it in 1959. For this reason some sources call it Jarník's algorithm or the Prim–Jarník algorithm.
7.5.1The idea: growing a single tree
A starting vertex is chosen; at first the tree consists of this vertex alone. At each step, among the vertices not in the tree, the one that connects to the tree by the cheapest edge is selected. This vertex and the edge connecting it are added to the tree. The algorithm ends when all vertices are in the tree. There is a single tree at every moment; there is no forest as in Kruskal.
At every step Prim chooses the lightest edge of a cut: the cut lies between the tree built so far and the remaining vertices. The edge c–d = 1 in the figure is the lightest edge of the graph, but it does not cross the cut; neither of its endpoints is in the tree. Prim can use this edge only after d has entered the tree. Kruskal, on the same graph, would have started with c–d = 1.
An assessment of the algorithm follows. Prim is well suited to dense graphs: with an adjacency matrix it runs in O(V2) time. There is no need to sort the edges. It works naturally with an adjacency list or matrix. Its weakness is that its performance depends on the data structure used: an array, a binary heap, and a Fibonacci heap give different running times. On a disconnected graph it covers only the component of the starting vertex.
7.5.2Key and parent
If “the vertex that connects to the tree by the cheapest edge” were searched for anew at every step, the algorithm would be slow. Prim stores this information for each vertex in two arrays and updates it as the tree grows.
In Prim's algorithm, for a vertex v not in the tree:
key[v]: the weight of the cheapest edge connecting v to the tree built so far. It starts at ∞ and is 0 at the source.parent[v](π): the endpoint, in the tree, of this cheapest edge. When the algorithm finishes, the edges (parent[v], v) give the MST.
When a new vertex u enters the tree, only the keys of the neighbors of u can change, because new ways of connecting to the tree open up only through u. For each neighbor v not in the tree, if w(u, v) < key[v], the key and parent are updated: key[v] = w(u, v), parent[v] = u. Then the vertex outside the tree with the smallest key is selected. The key of this vertex is the weight of the lightest edge crossing the cut.
7.5.3Pseudocode
The steps of Prim can be listed as follows:
- Choose a starting vertex and add all edges belonging to it to the priority queue.
- From the queue, select the edge of smallest weight that leads to a vertex not in the tree.
- Add the new vertex connected by the selected edge to the tree.
- Add the edges of the new vertex to the queue; repeat steps 2–4 until all vertices are in the tree.
The pseudocode on the slides has two parts. The first part initializes the arrays, and the second is the main loop:
PRIM(G, source):
MST = [ ]
dist = [ ]
parent = [ ]
visited = [ ]
for each v in V:
dist[v] = ∞
visited[v] = 0
dist[source] = 0
priorityQueue.add(source, 0)while priorityQueue is not empty:
u = priorityQueue.extractMin()
if visited[u] == 0:
visited[u] = 1
for each (u, v, weight) in G[u]:
if visited[v] == 0 and
weight < dist[v]:
dist[v] = weight
parent[v] = u
priorityQueue.add(v, weight)
for each v in V
(except source and dist[v] ≠ ∞):
MST.add((parent[v], v, dist[v]))
return MSTThe last loop adds an edge only for vertices other than the source with dist[v] ≠ ∞: a vertex whose key is still ∞ was not reachable from the source, and parent[v] is undefined. The dist array in the pseudocode is the key array of the definition. The name can be misleading: the value is not a distance but the weight of a single edge. The code may add a vertex to the queue more than once. Every time a vertex's key decreases, a new entry goes into the queue; the old entry is not deleted and stays in the queue. This is why this version is called lazy Prim. When the old entry finally leaves the queue, the check visited[u] discards it. The queue holds at most E entries, since each edge can cause one key decrease. The total time is O(E log E).
Skipping the visited check in the lazy version. When an old entry leaves the queue, its vertex is already in the tree. Without the check the vertex would “enter the tree” a second time, its neighbors would be examined again, and the parent array could be corrupted. The first thing to do after every extraction from the queue is to check whether the vertex has been processed before.
7.5.4Step by step: the priority queue
Prim is started at vertex 1 on the five-vertex graph of Figure 7.11. The classical textbook notation is used here: the queue Q starts with all vertices, and each vertex stays in the queue together with its key. In the tables π is the parent; “/” means that no parent has been assigned yet.
| Step | Vertex extracted | Edge added | Queue Q (after) | w(T) |
|---|---|---|---|---|
| 0 | — | — | 1 (0, /), 2 (∞, /), 3 (∞, /), 4 (∞, /), 5 (∞, /) | 0 |
| 1 | 1 | — | 3 (2, 1), 2 (3, 1), 4 (6, 1), 5 (∞, /) | 0 |
| 2 | 3 | (1,3) = 2 | 2 (3, 1), 4 (4, 3), 5 (∞, /) | 2 |
| 3 | 2 | (1,2) = 3 | 5 (2, 2), 4 (4, 3) | 5 |
| 4 | 5 | (2,5) = 2 | 4 (4, 3) | 7 |
| 5 | 4 | (3,4) = 4 | empty | 11 |
The steps are explained as follows. At initialization only the source has key 0, so the first vertex extracted is 1. The neighbors of 1 are updated: key(3) = 2, key(2) = 3, key(4) = 6. In the second step the smallest key belongs to 3; vertex 3 is extracted and (1,3) enters the tree. For the neighbor 4 of 3, since (3,4) = 4 < 6, we get key(4) = 4 and π(4) = 3. For the other neighbor 2, since (2,3) = 4 > key(2) = 3, there is no change. In the third step 2 is extracted and (1,2) is added; the key of 5 becomes 2. In the fourth step 5 is extracted; it has no other neighbor outside the tree. In the last step 4 is extracted and (3,4) is added.
The resulting tree consists of the edges (1,3), (1,2), (2,5), (3,4) and w(T) = 11. Kruskal had found the same tree on the same graph. The order in which the edges are added differs, however: Kruskal adds 2, 2, 3, 4, whereas Prim adds 2, 3, 2, 4. Prim adds the edge (2,5) of weight 2 after the edge (1,2) of weight 3 because 5 becomes adjacent to the tree only after 2 has entered it.
7.5.5Why is Prim correct?
On a connected graph, the edges (parent[v], v) chosen by Prim's algorithm form a minimum spanning tree.
At the beginning of a step, let the vertices in the tree be S and consider the cut (S, V − S). Both endpoints of every chosen edge are in S; none crosses the cut. key[v] is the weight of the cheapest edge from v to S. This invariant is maintained at every step, because when a new vertex enters the tree only the values of its neighbors can change, and the update does exactly that. When u with the smallest key is selected, (parent[u], u) is the lightest edge crossing the cut. By the cut property this edge is safe. At each step one vertex and one safe edge are added to the tree; after V − 1 steps an MST is obtained. □
A consequence of the proof is that the starting vertex does not matter. Prim started from a different vertex adds the edges in a different order. If the weights are distinct, it still finds the same tree in the end; if there are equal weights, it may find a different tree of the same weight.
7.6Prim's code and complexity
7.6.1The adjacency-matrix version
The shortest implementation of Prim uses no priority queue. The graph is given as an adjacency matrix: G[u][v] is the weight of the edge between u and v, or 0 if there is no edge. The vertex with the smallest key is found at each step by scanning the array from start to end.
void prim(int[][] G, int source) {
int V = G.length;
int[] key = new int[V];
int[] parent = new int[V];
boolean[] inTree = new boolean[V];
Arrays.fill(key, Integer.MAX_VALUE);
key[source] = 0;
parent[source] = -1;
for (int s = 0; s < V - 1; s++) {
int u = minKey(key, inTree);
inTree[u] = true;
for (int v = 0; v < V; v++)
if (G[u][v] != 0 && !inTree[v]
&& G[u][v] < key[v]) {
key[v] = G[u][v];
parent[v] = u;
}
}
}The code works as follows, line by line. Every cell of the key array is set to Integer.MAX_VALUE, which stands in for ∞. The source's key is 0 and its parent is −1; −1 means “no parent.” The inTree array records which vertices have entered the tree.
The outer loop runs V − 1 times. In each round minKey finds the vertex outside the tree with the smallest key, and this vertex is taken into the tree. The inner loop visits all neighbors of this vertex. Three conditions are tested together: G[u][v] != 0 says the edge exists, !inTree[v] says the neighbor is not yet in the tree, and G[u][v] < key[v] says the new edge is cheaper than the old best. If all three hold, the key and parent are updated.
That the outer loop runs V − 1 times rather than V is a deliberate choice. Once V − 1 vertices are in the tree, the key and parent of the last vertex can no longer change: the other endpoints of all edges connecting it to the tree are in the tree, and all of them have been examined. The last vertex is not marked in the inTree array, but its parent value is correct. The code on the slides uses a minKey helper. The helper can be written as follows:
int minKey(int[] key, boolean[] inTree) {
int min = Integer.MAX_VALUE, index = -1;
for (int v = 0; v < key.length; v++)
if (!inTree[v] && key[v] < min) {
min = key[v];
index = v;
}
return index;
}In a tie the helper picks the vertex with the smaller index, because the comparison uses <: a later equal key does not replace the minimum already found. In a disconnected graph all keys outside the tree may remain ∞; then the method returns −1 and the access inTree[-1] inside prim raises an error. The code assumes a connected graph.
7.6.2Code trace: the A–F graph
The code is traced on a graph with six vertices. The vertices are A–F with indices 0–5. The source is B (index 1). The edges are AB = 1, BC = 3, AD = 3, BD = 2, BE = 6, BF = 5, CE = 4, CF = 4, DE = 3, and EF = 2.
key[B] = 0.Round s | u | Neighbors updated | key | w(T) |
|---|---|---|---|---|
| — | — | init | ∞, 0, ∞, ∞, ∞, ∞ | 0 |
| 0 | B (0) | A → 1, C → 3, D → 2, E → 6, F → 5 (parent B in all cases) | 1, 0, 3, 2, 6, 5 | 0 |
| 1 | A (1) | none: AD = 3 > key[D] = 2 | 1, 0, 3, 2, 6, 5 | 1 |
| 2 | D (2) | E → 3 (parent D) | 1, 0, 3, 2, 3, 5 | 3 |
| 3 | C (3) | F → 4 (parent C); CE = 4 > 3, E unchanged | 1, 0, 3, 2, 3, 4 | 6 |
| 4 | E (3) | F → 2 (parent E) | 1, 0, 3, 2, 3, 2 | 9 |
| — | (F) | loop ends; the parent of F is E | 1, 0, 3, 2, 3, 2 | 11 |
In the first round minKey returns B, because only B's key is finite. All five neighbors of B are updated. In the second round the smallest key is A's (1); (B, A) enters the tree. The only neighbor of A outside the tree is D, but AD = 3 is larger than D's current key, 2. In the third round D (2) enters and E's key drops from 6 to 3: connecting E through D is cheaper than connecting it through B.
In the fourth round the keys of C and E are equal (3). minKey chooses C, which has the smaller index. The edge of weight 4 from C to F is cheaper than F's current key, 5, so F's parent becomes C. In the fifth round E (3) enters, and through EF = 2 the key of F drops to 2. The outer loop makes five rounds and ends. F is not formally taken into the tree, but its parent is E. The MST is read from the edges (parent[v], v): BA, BC, BD, DE, EF. The total is 1 + 3 + 2 + 3 + 2 = 11.
What would happen if E were chosen in the tie? E enters, and F's key becomes 2; then C (3) and F (2) compete and F is chosen. Finally C enters too. The chosen edges would again be BA, BD, DE, EF, BC; only the order would change. Although this graph has equal-weight edges, its MST is unique.
7.6.3The lazy priority-queue version
On sparse graphs, scanning the array from start to end in every round is an unnecessary cost. Java's PriorityQueue class removes the smallest element in O(log n) time. The lazy version on the slides writes the method of the pseudocode in Java. The graph is given as an adjacency list: adj.get(u) is the list of edges leaving u. key, parent, inTree, and adj are class fields.
void primPQ(int source) {
Arrays.fill(key, INF);
key[source] = 0;
PriorityQueue<int[]> pq =
new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.add(new int[] { source, 0 });
while (!pq.isEmpty()) {
int u = pq.poll()[0];
if (inTree[u]) continue; // stale
inTree[u] = true;
for (Edge e : adj.get(u))
if (!inTree[e.v] && e.w < key[e.v]) {
key[e.v] = e.w; parent[e.v] = u;
pq.add(new int[] { e.v, e.w });
}
}
}Each entry in the queue is a two-element array: {vertex, key}. The comparator a[1] - b[1] orders the entries by key. As long as the weights are small, the subtraction is safe; with very large weights it is more correct to write Integer.compare(a[1], b[1]). In each round the loop removes the smallest entry. If the vertex is already in the tree, the entry is stale and is skipped with continue. Otherwise the vertex enters the tree and its neighbors are examined. For every neighbor whose key decreases, a new entry is added to the queue. The old entry is not removed; the removal is postponed until the moment the entry leaves the queue. This postponement is called lazy deletion.
The code is traced on the five-vertex graph with source 1. The queue column in Table 7.11 gives the contents before the entry is removed, sorted by key.
| Queue (before) | Extracted | Action | key |
|---|---|---|---|
| (1,0) | (1,0) | 1 enters the tree; 2 → 3, 3 → 2, 4 → 6 | 0, 3, 2, 6, ∞ |
| (3,2) (2,3) (4,6) | (3,2) | 3 enters (edge 1–3); 4 → 4; for 2, 4 > 3, unchanged | 0, 3, 2, 4, ∞ |
| (2,3) (4,4) (4,6) | (2,3) | 2 enters (edge 1–2); 5 → 2 | 0, 3, 2, 4, 2 |
| (5,2) (4,4) (4,6) | (5,2) | 5 enters (edge 2–5); no update | 0, 3, 2, 4, 2 |
| (4,4) (4,6) | (4,4) | 4 enters (edge 3–4); no update | 0, 3, 2, 4, 2 |
| (4,6) | (4,6) | 4 is already in the tree: stale entry, continue | 0, 3, 2, 4, 2 |
In the second row the key of 4 drops from 6 to 4, and the entry (4,4) is added to the queue. The old entry (4,6) stays in the queue. Vertex 4 enters the tree through the entry (4,4). The entry (4,6) is extracted last and skipped. When the queue is empty, the MST edges are read as (parent[v], v): 1–3 (2), 1–2 (3), 2–5 (2), and 3–4 (4); total 11.
The counterpart of the lazy version is the eager version, which decreases the key in place. The eager version keeps a single entry per vertex in the queue and updates that entry when the key decreases. This operation is called decrease-key. Java's PriorityQueue class does not offer this operation directly, which is why the lazy version is common in Java implementations. The lazy version keeps at most E entries in the queue instead of V, but since log E ≤ 2 log V, the order does not change.
7.6.4A nine-vertex example
The nine-vertex example of Kruskal is solved with Prim starting from A. Each row gives the key and parent values after the vertex that enters the tree in that step.
| Entering | A | B | C | D | E | F | G | H | I | Total |
|---|---|---|---|---|---|---|---|---|---|---|
| A | 0/− | 4/A | 7/A | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 |
| B | 0/− | 4/A | 7/A | 9/B | ∞ | 20/B | ∞ | ∞ | ∞ | 4 |
| C | 0/− | 4/A | 7/A | 9/B | ∞ | 1/C | ∞ | ∞ | ∞ | 11 |
| F | 0/− | 4/A | 7/A | 9/B | 1/F | 1/C | ∞ | 3/F | ∞ | 12 |
| E | 0/− | 4/A | 7/A | 2/E | 1/F | 1/C | 10/E | 3/F | 15/E | 13 |
| D | 0/− | 4/A | 7/A | 2/E | 1/F | 1/C | 6/D | 3/F | 15/E | 15 |
| H | 0/− | 4/A | 7/A | 2/E | 1/F | 1/C | 6/D | 3/F | 12/H | 18 |
| G | 0/− | 4/A | 7/A | 2/E | 1/F | 1/C | 6/D | 3/F | 5/G | 24 |
| I | 0/− | 4/A | 7/A | 2/E | 1/F | 1/C | 6/D | 3/F | 5/G | 29 |
The table shows several things clearly. The key of F first becomes 20 through B and drops to 1 when C enters. The key of D is 9 through B and drops to 2 when E enters. The key of I changes three times: 15 through E, 12 through H, and 5 through G. A vertex's key only decreases; it cannot grow. When H enters the tree, the edge EH = 5 can no longer be used, because E and H are both in the tree. Kruskal had skipped the same edge on the grounds of forming a cycle.
The resulting weight is 29, the same as that of the tree Kruskal found. The orders in which the two algorithms add edges, however, are clearly different. Kruskal adds the weights in the order 1, 1, 2, 3, 4, 5, 6, 7. Prim adds them in the order 4, 7, 1, 1, 2, 3, 6, 5: it first takes the expensive edges around A, and reaches the cheap edges only when the tree gets to them.
7.6.5Complexity
The running time of Prim depends on the cost of two operations: extracting the vertex with the smallest key and decreasing the key of a neighbor. The first operation is performed V times. The second is performed at most E times, because each edge is examined once, when one of its endpoints enters the tree. In an undirected graph every edge appears in two adjacency lists; the number of examinations does not exceed 2E.
| Implementation | Extract min | Decrease key | Total |
|---|---|---|---|
| Adjacency matrix + array scan | V × O(V) | O(1) | O(V2) |
| Adjacency list + binary heap | V × O(log V) | E × O(log V) | O((V + E) log V) |
| Lazy version: edge copies in the queue | ≤ E insertions and extractions, each O(log E) | O(E log E) | |
| Fibonacci heap | O(log V) amortized | O(1) amortized | O(E + V log V) |
In the matrix version the outer loop runs V − 1 times. In each round minKey scans V cells and the inner loop visits V neighbors. The total is O(V2), independent of the number of edges. In the heap version each extraction and each decrease-key takes O(log V); the total is O((V + E) log V). In a connected graph E ≥ V − 1, so this expression is often shortened to O(E log V).
Which version is better depends on the density of the graph. In a dense graph (E ≈ V2) the matrix version is best with O(V2); the heap version rises to O(V2 log V). In a sparse graph (E ≈ V), on the other hand, the heap version takes O(V log V), while the matrix version needlessly spends O(V2).
Compare the two versions on a graph with V = 1000 vertices. The matrix version takes about V2 = 106 steps. For the heap version take log2 1000 ≈ 10.
- E = 5000 (sparse): E log V ≈ 5000 · 10 = 5 · 104. The heap version does about 20 times less work.
- E = 500,000 (nearly complete): E log V ≈ 5 · 106. The matrix version does about 5 times less work.
The crossover is roughly at E log V ≈ V2; here E ≈ 105. Constant factors shift the boundary somewhat, but the direction does not change.
7.6.6How Prim differs from Dijkstra
The code of Prim is very similar to that of Dijkstra's shortest-path algorithm. Both start at a source, extract the vertex with the smallest key from a priority queue, and update its neighbors. The only difference is the meaning of the key.
| Prim (MST) | Dijkstra (shortest paths) | |
|---|---|---|
key[v] | the single cheapest edge connecting v to the tree | total path length from the source to v |
| Update | w(u, v) < key[v] | dist[u] + w(u, v) < dist[v] |
| Result | tree of smallest total weight | shortest-path tree |
| Source | does not affect the result (same weight) | determines the result |
| Negative weights | no problem | does not work correctly |
Run Dijkstra from B on the A–F graph. The distances are A = 1, C = 3, D = 2, E = 5 (B → D → E), and F = 5. F is reached directly by the edge BF = 5; the path B → D → E → F costs 2 + 3 + 2 = 7. The shortest-path tree consists of the edges BA, BC, BD, DE, BF and has total weight 1 + 3 + 2 + 3 + 5 = 14.
Prim, on the other hand, attaches F to E: the cheapest way to connect F to the tree is EF = 2. Prim's tree has weight 11. Both trees span all the vertices. One minimizes the total weight, the other the distances from the source.
A similar difference shows up in the five-vertex graph. The shortest path from 1 to 4 has length 6, and this distance is obtained both by the direct edge (1,4) and by the path 1 → 3 → 4. So the shortest-path tree may use the edge (1,4) = 6. The MST chooses the edge (3,4) = 4 instead.
Writing Prim's update condition as key[u] + G[u][v] < key[v]. This line turns Prim into Dijkstra, and the result is a shortest-path tree. On the A–F graph this mistake attaches F to B and yields a tree of weight 14 instead of 11. In Prim the key is always the weight of a single edge; a sum is never written.
7.7Borůvka's algorithm
The oldest algorithm for finding a minimum spanning tree is Otakar Borůvka's work of 1926. Borůvka was working on the problem of building the electrical network of the Moravia region as cheaply as possible. The method was rediscovered several times afterwards; because of Georges Sollin's work in the 1960s it is also called Sollin's algorithm.
7.7.1The idea: all components at once
At the start every vertex is an independent component. The algorithm proceeds in rounds. In each round every component chooses the cheapest edge connecting it to the outside. All the chosen edges are added together, and the components they connect merge. Rounds continue until a single component remains. On a connected graph the algorithm produces V − 1 edges.
The cheapest outgoing edge of a component is the lightest edge of the cut between that component and the rest of the vertices. By the cut property this edge is safe. Kruskal and Prim choose a single cut at each step; Borůvka uses as many cuts as there are components, all at once, in every round.
In the graph of the figure, the cheapest edge of e is ef = 6, because its other edge is ae = 9. Vertex f chooses bf = 3. An edge can be chosen from both ends; ab is the choice of both a and b, but it is added only once. At the end of the first round the components are {a, b, e, f}, {c, d}, and {g, h}. In the second round bc = 4 and fg = 5 are added and the tree is complete; the total weight is 22.
The most important advantage of the algorithm is that the components' choices are independent of one another. The cheapest edge of each component can be found on a separate processor. This makes Borůvka very well suited to parallel and distributed computation. The number of rounds is also small: at most ⌈log2 V⌉. It has weaknesses too. It is more complicated to code than Kruskal and Prim. When there are equal-weight edges a consistent tie-breaking rule is needed; otherwise a cycle can form.
7.7.2Steps and pseudocode
- At the start every vertex counts as a component (set) by itself.
- For each component, find the edge of smallest weight that connects it to another component.
- Add all the edges found; merge the components they connect. The same edge is not added twice.
- Repeat steps 2 and 3 until a single component remains. If no edge is added in a round, the graph is not connected; stop, and the result is a minimum spanning forest.
BORUVKA(G):
MST = [ ]
componentCount = |V|
while componentCount > 1:
cheapest = [ ] // per component
for each e = (u, v, weight) in E:
cu = disjointSet.find(u)
cv = disjointSet.find(v)
if cu ≠ cv:
cheapest[cu] = min(cheapest[cu], e)
cheapest[cv] = min(cheapest[cv], e)
added = false
for each (u, v, weight) in cheapest:
if disjointSet.find(u) ≠ disjointSet.find(v):
MST.add((u, v, weight))
disjointSet.union(u, v)
componentCount -= 1
added = true
if not added: break // forest
return MSTBorůvka does not sort the edges. In each round it scans all edges once and, for each component, keeps the smallest outgoing edge seen so far. The components are tracked with a disjoint-set structure: if the find results of an edge's two endpoints are the same, the edge lies inside a component and is ignored. In the second loop, find is asked again as the chosen edges are added. The reason is that two components may have chosen the same edge. When it is added for the first time, the two components merge; when its turn comes the second time, its endpoints are already in the same component and the edge is skipped.
7.7.3A six-vertex example
The algorithm is run on a graph with vertices A–F and nine edges. The edges are AB = 1, BC = 5, AD = 4, BE = 3, BD = 7, BF = 6, CF = 9, DE = 8, and EF = 2.
| Component | Outgoing edges | Cheapest |
|---|---|---|
| {A} | AB 1, AD 4 | AB 1 |
| {B} | AB 1, BC 5, BE 3, BD 7, BF 6 | AB 1 |
| {C} | BC 5, CF 9 | BC 5 |
| {D} | AD 4, BD 7, DE 8 | AD 4 |
| {E} | BE 3, DE 8, EF 2 | EF 2 |
| {F} | BF 6, CF 9, EF 2 | EF 2 |
Two components each choose AB and EF, but each is added once. In round 1 four distinct edges are added: AB, BC, AD, and EF. Two components remain: {A, B, C, D} and {E, F}. The total weight is 1 + 5 + 4 + 2 = 12.
In round 2 the edges between the two components are BE = 3, BF = 6, CF = 9, and DE = 8. Both components choose the cheapest, BE = 3. BE is added and a single component remains. The MST consists of the edges AB, BC, AD, EF, BE and has weight 12 + 3 = 15.
On the same graph Kruskal adds the edges one at a time, in the order of weights 1, 2, 3, 4, 5: AB, EF, BE, AD, BC. In Borůvka, four edges are added at once in the first round. The tree found is the same.
7.7.4A twelve-vertex example
The strength of Borůvka shows more clearly on larger graphs. Consider a graph with vertices A–L and 20 edges. The edges are:
AB 13, AC 6, BC 7, BD 1, CD 14, CE 8, CH 20, DE 9, DF 3, EF 2, EJ 18, GH 15, GJ 19, GK 10, GI 5, HJ 17, IK 11, JK 16, JL 4, KL 12
| Round | Cheapest edges of the components | Distinct edges added | Number of components | Total |
|---|---|---|---|---|
| 1 | A: AC 6, B: BD 1, C: AC 6, D: BD 1, E: EF 2, F: EF 2, G: GI 5, H: GH 15, I: GI 5, J: JL 4, K: GK 10, L: JL 4 | AC, BD, EF, GI, GH, JL, GK | 12 → 5 | 43 |
| 2 | {A, C}: BC 7, {B, D}: DF 3, {E, F}: DF 3, {G, H, I, K}: KL 12, {J, L}: KL 12 | BC, DF, KL | 5 → 2 | 65 |
| 3 | {A, …, F}: EJ 18, {G, …, L}: EJ 18 | EJ | 2 → 1 | 83 |
In the first round seven distinct edges are added and the number of components drops from 12 to 5. H's choice is noteworthy: all of H's edges are expensive (15, 17, 20), and the cheapest is GH 15. This edge is safe despite being heavy, because it is the lightest edge of the cut {H}. K also chooses GK 10; IK 11 and KL 12 are more expensive. G, H, I, and K are thus gathered into one component.
In the second round the component {A, C} chooses BC 7. The components {B, D} and {E, F} choose the same edge, DF 3. The two components on the right side both choose KL 12. Three distinct edges are added and two components remain. In the third round only two edges connect the two halves: CH 20 and EJ 18. The cheaper one is EJ 18, and both components choose it. The MST is complete after three rounds and has weight 83.
On this graph Kruskal adds 11 edges in 11 separate steps. Borůvka builds the same tree in three rounds: 7 + 3 + 1 edges. Each round scans all edges once; the total work is 3 · 20 = 60 edge examinations.
7.7.5Java code and trace
The Java code on the slides gives the body of the main loop. edges is the edge list, parent the parent array of the disjoint sets, tree the chosen edges, and componentCount the number of remaining components, which starts at V.
while (componentCount > 1) {
Edge[] cheapest = new Edge[V];
for (Edge e : edges) { // 1) find cheapest
int r1 = find(parent, e.u), r2 = find(parent, e.v);
if (r1 == r2) continue; // same component
if (cheapest[r1] == null || e.w < cheapest[r1].w)
cheapest[r1] = e;
if (cheapest[r2] == null || e.w < cheapest[r2].w)
cheapest[r2] = e;
}
boolean added = false;
for (Edge e : cheapest) { // 2) add them all
if (e == null) continue;
int r1 = find(parent, e.u), r2 = find(parent, e.v);
if (r1 == r2) continue; // already added
tree.add(e);
parent[r1] = r2; // union
componentCount--;
added = true;
}
if (!added) break; // forest
}In each round the cheapest array is created anew. The index of the array is the root of a component; the cell holds the cheapest outgoing edge of that component found so far. The first loop scans all edges. If the roots of an edge's two endpoints are the same, the edge lies inside a component and is passed over with continue. Otherwise the edge is a candidate for both roots: for each root, it is written into the cell if the cell is empty or the new edge is cheaper.
The second loop walks through the cheapest array. Empty cells belong to vertices that are not roots and are skipped. For each candidate edge the roots are found again. If the roots are the same, the edge has already been added in this round, or the two components have been joined by another edge; the edge is skipped. Otherwise the edge enters the tree, parent[r1] = r2 merges the components, the component count drops by one, and added becomes true. If no edge is added in a round, no component has an outgoing edge, that is, the graph is not connected; break leaves the loop and tree is a minimum spanning forest. Without this check componentCount would never fall to 1 and the loop would run forever.
The code is traced on the six-vertex example. The vertices are A–F with indices 0–5. The edges stand in the list in this order: AB, BC, AD, BE, BD, BF, CF, DE, EF.
| Stage | Event | componentCount |
|---|---|---|
| Round 1, scan | AB(1): cheapest[A] = cheapest[B] = AB. BC(5): cheapest[C] = BC. AD(4): cheapest[D] = AD. BE(3): cheapest[E] = BE. BD(7): no change. BF(6): cheapest[F] = BF. CF(9), DE(8): no change. EF(2): cheapest[E] = cheapest[F] = EF. | 6 |
| Round 1, add | cheapest[A] = AB: roots A, B → add, parent[A] = B | 5 |
cheapest[B] = AB: both endpoints in the same component → skip | 5 | |
cheapest[C] = BC: roots B, C → add, parent[B] = C | 4 | |
cheapest[D] = AD: roots C, D → add, parent[C] = D | 3 | |
cheapest[E] = EF: roots E, F → add, parent[E] = F | 2 | |
cheapest[F] = EF: same component → skip | 2 | |
| Round 2, scan | AB, BC, AD, BD, EF stay inside components. Of the edges between components, BE(3), BF(6), CF(9), DE(8), the cheapest is BE: cheapest[D] = cheapest[F] = BE. | 2 |
| Round 2, add | cheapest[D] = BE: roots D, F → add, parent[D] = F | 1 |
cheapest[F] = BE: same component → skip; loop ends | 1 |
In the scan of round 1, E's candidate is first BE(3) and then changes when EF(2) comes. F's candidate is likewise first BF(6) and then EF(2). In the add loop, when AD is added, find(A) follows the path A → B → C and finds C. Since the roots are C and D, parent[C] = D is written. In round 2 the component roots are D and F, so the candidate edge is written into the cells cheapest[D] and cheapest[F]. The resulting weight is 15.
7.7.6Complexity and tie-breaking
On a connected graph with V vertices, Borůvka runs at most ⌈log2 V⌉ rounds, and its total running time is O(E log V).
Suppose c > 1 components at the start of a round. Since the graph is connected, every component has at least one outgoing edge, and every component chooses an edge. The chosen edge joins the component with at least one other component. Each new component formed at the end of the round contains at least two old components. Hence the new number of components is at most ⌊c/2⌋. After k rounds at most V/2k components remain; once k ≥ log2 V, this number drops to 1. Each round scans all edges once and makes two find calls per edge. If the nearly constant cost of disjoint sets is ignored, a round takes O(E). The total is O(E log V). □
The observation ⌊c/2⌋ in the proof actually gives a slightly tighter bound. For V = 1000 the number of components falls in the worst case as 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1; 9 rounds suffice. ⌈log2 1000⌉ = 10 is a safe upper bound. In practice the number of rounds is often even smaller, because more than two components can merge in one round. The twelve-vertex example finished in 3 rounds; ⌈log2 12⌉ = 4. Borůvka does not sort the edges; it only compares weights.
Equal weights create a special problem in Borůvka. As an example take a triangle a, b, c whose edges all have weight 1. If ties are resolved arbitrarily, a may choose ab, b may choose bc, and c may choose ca. If all three edges are added at once, a cycle forms. To prevent this, a consistent tie-breaking rule is needed: when weights are equal, edges are compared by, say, their indices in the list. Then all the edges fall into a strict order and no cycle can form. When edges are added simultaneously (for example in a parallel implementation), such a consistent tie-breaker is required. In the sequential code on the slides, however, the check find(r1) == find(r2) in the second loop already prevents a cycle: an edge whose endpoints are now in the same component is not added.
Recomputing the edges chosen in a round as the components are updated within the same round. In Borůvka all of a round's choices are made with respect to the components at the start of the round; the additions come afterward. If selection and addition are interleaved, the algorithm turns into something between Kruskal and Prim, and the bound on the number of rounds loses its validity.
7.8The reverse-delete algorithm
7.8.1The idea: Kruskal's mirror image
The reverse-delete algorithm is also greedy and was proposed in Kruskal's 1956 paper. Whereas Kruskal starts from an empty graph and adds small edges, reverse-delete starts from the whole graph and tries to delete large edges. The edges are sorted by weight in descending order. Starting from the heaviest edge, every edge whose deletion does not break the connectivity of the graph is deleted. An edge whose deletion would disconnect the graph is left in place.
The algorithm rests on the cycle property. If the graph stays connected when an edge is deleted, there is another path between its endpoints; the edge lies on a cycle. Because edges are processed in descending order, the remaining edges of this cycle are at most as heavy as it is. The heavier edges have either already been deleted or remain because they are bridges. So the deleted edge is the heaviest edge of a cycle in the remaining graph, and by the cycle property an MST does not need it. An edge that cannot be deleted is a bridge at that moment and must be in every spanning tree.
Reverse-delete has mostly theoretical and instructional value. Every deletion requires a connectivity test, and this test is expensive; in practice the algorithm is usually slow.
7.8.2Steps, pseudocode, and complexity
- Sort all the edges in descending order of weight.
- Delete the next heaviest edge.
- If the graph is no longer connected, put the deleted edge back.
- Repeat steps 2 and 3 until all edges have been processed.
REVERSE_DELETE(G):
MST = all edges
edges.sort(descending)
for each (u, v, weight) in edges:
MST.remove((u, v, weight))
disjointSet.reset()
for each (x, y) in MST:
disjointSet.union(x, y)
root = disjointSet.find(V[0])
if some v has disjointSet.find(v) ≠ root:
MST.add((u, v, weight)) // put back
return MSTThe pseudocode tests connectivity with disjoint sets. After every deletion the structure is reset and union is called for all remaining edges. Then the root of the first vertex is found. If some vertex has a different root, the graph has fallen apart and the deleted edge is put back once. The edge put back is the edge (u, v, weight) deleted at the start of the loop; the v in the condition line is used only in the sense of “some vertex,” and the two names should not be confused.
The complexity calculation is simple. A connectivity test is made for every edge. The test takes O(V + E) with BFS or DFS, and rebuilding with disjoint sets is of the same order. E tests come to O(E · (V + E)) in total. The O(E log E) cost of sorting is small next to this. For a graph with V = 1000 and E = 5000, this means about 3 · 107 steps; Kruskal makes do with about 6 · 104 steps on the same graph.
7.8.3A seven-vertex example
Reverse-delete is run on a graph with vertices 0–6 and 11 edges. The total weight of the edges is 90. The descending order is as follows:
3–4 15, 5–6 11, 1–3 9, 4–6 9, 1–2 8, 4–5 8, 1–4 7, 0–1 7, 3–5 6, 2–4 5, 0–3 5
| Edge | w | Still connected if deleted? | Result |
|---|---|---|---|
| 3–4 | 15 | yes | deleted |
| 5–6 | 11 | yes | deleted |
| 1–3 | 9 | yes | deleted |
| 4–6 | 9 | no: 6 would be isolated | kept |
| 1–2 | 8 | yes | deleted |
| 4–5 | 8 | yes | deleted |
| 1–4, 0–1, 3–5, 2–4, 0–3 | 7, 7, 6, 5, 5 | no: each is a bridge | kept |
The first three deletions remove cycle edges. When 3–4 = 15 is deleted, 3 and 4 stay connected through the path 3 → 0 → 1 → 4. When 4–6 = 9 comes up, 5–6 has already been deleted, and the only edge of 6 is 4–6. If this edge were deleted, 6 would be isolated, so it is put back. 1–2 = 8 and 4–5 = 8 can be deleted, because 2 is reached through 2–4 and 5 through 3–5. At this point the remaining six edges form a tree and each is a bridge; none can be deleted. The number of remaining edges is 6 = V − 1, and the MST weight is 9 + 7 + 7 + 6 + 5 + 5 = 39.
On the same graph Kruskal first adds the edges of weight 5, 5, 6, 7, 7. It then skips the two edges of weight 8 and the edge 1–3 of weight 9 because they form cycles. Finally it adds 4–6 = 9. The two algorithms reach the same tree from opposite directions: Kruskal decides what to add, reverse-delete decides what to keep.
7.8.4Java code and trace
void reverseDelete(int V, List<Edge> edges) {
edges.sort((a, b) -> b.w - a.w); // descending
int i = 0;
while (i < edges.size()) {
Edge e = edges.remove(i); // delete tentatively
if (!isConnected(V, edges)) {
edges.add(i, e); // put back
i++;
}
}
}edges.sort((a, b) -> b.w - a.w) puts the edges in descending order; writing the comparator as b − a reverses the order. i is the index of the next edge to examine in the list. In each round of the loop the edge is tentatively deleted with edges.remove(i). After the deletion the list shifts by one and the next edge comes to index i again; so if the deletion succeeds, i is not incremented. If deleting the edge disconnects the graph, edges.add(i, e) puts the edge back in its old place and i increases by one. The loop ends when i reaches the length of the list. At that point the edges remaining in the list are the MST. The isConnected method used by the code can be written with BFS:
boolean isConnected(int V, List<Edge> edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (Edge e : edges) { adj.get(e.u).add(e.v); adj.get(e.v).add(e.u); }
boolean[] seen = new boolean[V];
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(0); seen[0] = true;
int count = 1;
while (!queue.isEmpty()) {
int x = queue.poll();
for (int y : adj.get(x))
if (!seen[y]) { seen[y] = true; count++; queue.add(y); }
}
return count == V; // reached every vertex?
}The method first builds the adjacency list from the edge list, then starts a BFS from vertex 0 and counts the vertices reached. If the count equals V, the graph is connected. Each call takes O(V + E); since there are E calls, the total cost is the O(E · (V + E)) computed above.
The code is traced on the lettered version of the same seven-vertex graph: vertices 0–6 are named A–G. The edge list is given in alphabetical order: AB 7, AD 5, BC 8, BD 9, BE 7, CE 5, DE 15, DF 6, EF 8, EG 9, FG 11. The sort is stable; edges of equal weight keep this order.
| Edge | isConnected | Action | i (after) |
|---|---|---|---|
| DE 15 | true | stays deleted | 0 |
| FG 11 | true | stays deleted | 0 |
| BD 9 | true | stays deleted | 0 |
| EG 9 | false: G is isolated | put back | 1 |
| BC 8 | true | stays deleted | 1 |
| EF 8 | true | stays deleted | 1 |
| AB 7 | false: {A, D, F} gets cut off | put back | 2 |
| BE 7 | false: {C, E, G} gets cut off | put back | 3 |
| DF 6 | false: {F} gets cut off | put back | 4 |
| AD 5 | false: {D, F} gets cut off | put back | 5 |
| CE 5 | false: {C} gets cut off | put back | 6 |
At the EG step FG has already been deleted, and the only connection of G is EG. When the AB step is reached, the edges of A are AB and AD, the remaining edges of D are AD and DF, and the remaining edge of F is only DF. If AB were deleted, A, D, and F would be cut off from the other vertices. After the last row i = 6 equals the length of the list and the loop ends. The remaining tree consists of the edges AB, AD, BE, CE, DF, and EG; its weight is 39.
Incrementing i even when the deletion succeeds. edges.remove(i) shifts the list one place to the left; the next edge is now at index i. If i is incremented, an edge is skipped without being examined after every successful deletion, and the result may be not a tree but a subgraph containing superfluous edges.
7.9Comparing the four algorithms
The four algorithms solve the same problem and rest on the same theoretical foundation, but they work differently and have different costs. Table 7.20 shows the differences side by side.
| Kruskal | Prim | Borůvka | Reverse-delete | |
|---|---|---|---|---|
| Perspective | edge-oriented | vertex-oriented | component-oriented | edge-oriented (deletion) |
| Intermediate state | forest | single tree | forest | connected graph |
| Property used | cut | cut | cut | cycle |
| Data structure | sorted edges + disjoint sets | priority queue / array | disjoint sets | BFS/DFS |
| Time | O(E log E) | O(V2) or O((V + E) log V) | O(E log V) | O(E · (V + E)) |
| Best suited for | sparse graphs | dense graphs | parallel / distributed | teaching, theory |
| Disconnected graph | gives a forest | one component | gives a forest | preserves components |
The rows of the table correspond to a few practical questions. If the graph arrives as an edge list and is sparse, Kruskal is the easiest and fastest choice. If the graph is given as an adjacency matrix and is dense, Prim with an array scan gives the best result with O(V2); no sorting or heap is needed. When a sparse graph is given as an adjacency list, Prim with a heap is of the same order as Kruskal. If the work is to be distributed across several processors, the independent choices of Borůvka are a great convenience. Reverse-delete is hardly used in production code; it is instructive as an algorithmic counterpart of the cycle property.
Behavior on disconnected graphs also matters. Kruskal and Borůvka complete each component separately and return a minimum spanning forest. Prim covers only the component of the starting vertex; to find the forest it must be restarted from each component it has not covered. Reverse-delete never disconnects a component, so it preserves the components as they are; it is enough to write the connectivity test so that it preserves the number of components.
The nine-vertex graph shows the difference concretely. Kruskal and Prim find the same tree (29). Kruskal adds the edges in the order 1, 1, 2, 3, 4, 5, 6, 7, Prim in the order 4, 7, 1, 1, 2, 3, 6, 5. Kruskal's insertion order is weight order; Prim's follows the direction in which the tree grows.
These four algorithms are not the end of the story. In 1995 Karger, Klein, and Tarjan gave a randomized algorithm with linear expected time. In 2000 Bernard Chazelle published a deterministic algorithm whose running time involves the inverse Ackermann function and is nearly linear. Whether a deterministic MST algorithm with strictly linear time exists is still an open question.
7.10Common mistakes
This section gathers the warnings scattered through the chapter, together with the list of mistakes from the slides.
Mistaking the MST for a shortest-path tree. The MST minimizes the total weight; the MST path between two vertices need not be a shortest path. In the A–F graph the B–F path in the MST is B → D → E → F and has length 7; the direct edge BF has weight 5.
Testing for a cycle by adjacency. In Kruskal the question “are u and v directly connected?” is not enough. The question to ask is whether the two endpoints are in the same component: find(u) == find(v).
Adding distances in Prim. Writing key[u] + w gives Dijkstra. In Prim the key is the weight of a single edge only.
Fearing negative weights. MST algorithms work correctly with negative weights too, because they only compare weights. The proofs of the cut and cycle properties do not look at the sign of the weights either. The problem with negative weights is specific to Dijkstra. In fact, if the same constant is added to all weights, the MST does not change. The order of the edges is preserved. Since every spanning tree has V − 1 edges, the totals of all trees increase by the same amount.
Forgetting disconnected graphs. A disconnected graph has no MST; it has a minimum spanning forest. The condition while (tree.size() < V − 1) runs past the end of the list when the edges run out. The condition k < edges.size() must be added.
Applying the algorithms to a directed graph. These algorithms are for undirected graphs. In a directed graph, the cheapest structure that reaches every vertex from a root is called a minimum spanning arborescence, and the problem is solved by the Chu–Liu/Edmonds algorithm. Applying Kruskal or Prim unchanged to directed edges gives a wrong result.
7.11Summary
- Spanning tree and MST: a connected, acyclic subgraph that contains all the vertices of a connected, undirected graph is a spanning tree and has exactly V − 1 edges. The one of smallest total weight is called a minimum spanning tree. A complete graph has nn−2 spanning trees, so greedy algorithms are used instead of trying them all.
- Cut property: the lightest edge of every cut belongs to some MST; if the lightest edge of the cut is unique, it is in every MST. Kruskal, Prim, and Borůvka rest on this property.
- Cycle property: the unique heaviest edge of a cycle is in no MST. Reverse-delete rests on this property. If all weights are distinct, the MST is unique.
- Kruskal: edges are examined in ascending order; if
find(u) ≠ find(v), the edge is added and two trees merge. The time is O(E log E) = O(E log V), and the sort dominates. - Disjoint sets: in the
parent[]forest each set is a tree and the root is the representative. Path compression and union by rank together give an amortized O(α(V)) per operation; α does not exceed 4 in practice. With rank alone each operation is O(log V). - Prim: a single tree is grown;
key[v]is the weight of the cheapest single edge connecting v to the tree. It takes O(V2) with an array scan, O((V + E) log V) with a binary heap, O(E log E) with the lazy version, and O(E + V log V) with a Fibonacci heap. - Prim and Dijkstra: the code is almost identical; Prim makes a single edge weight the key, Dijkstra the total distance from the source. Prim's result has the same weight regardless of the source and is also correct with negative weights.
- Borůvka: in each round every component chooses its cheapest outgoing edge and these edges are added at once. The number of components at least halves every round; at most ⌈log2 V⌉ rounds, total O(E log V). With equal weights a consistent tie-breaker is needed.
- Reverse-delete: edges are deleted in descending order; if the graph falls apart, the edge is put back. Because a connectivity test is made at every deletion, the time is O(E · (V + E)).
- Choosing: sparse graph and edge list → Kruskal; dense graph and adjacency matrix → Prim with an array scan; parallel computation → Borůvka; forest in a disconnected graph → Kruskal or Borůvka.
7.12Key terms
- spanning tree
- minimum spanning tree (MST)
- minimum spanning forest
- connected component
- cut
- cut property
- cycle property
- bridge
- greedy algorithm
- exchange argument
- Kruskal's algorithm
- union-find, disjoint sets
- path compression
- union by rank
- amortized analysis
- Prim's algorithm
- priority queue
- parent
- adjacency matrix
- adjacency list
- Dijkstra's algorithm
- Borůvka's algorithm
- reverse-delete algorithm
- bottleneck
7.13Test Yourself
Questions 1–6 use the same graph K. The vertices of K are A–F, and its edges are AB = 7, AC = 3, AD = 6, BC = 4, BE = 2, CD = 5, CE = 8, CF = 9, DF = 1, and EF = 10.
Which edges cross the cut {A, C} | {B, D, E, F} in K? What does the cut property say, and about which edge?
Answer
The edges crossing the cut are AB 7, AD 6, BC 4, CD 5, CE 8, and CF 9. AC 3 does not cross the cut, because both its endpoints are on the same side. The lightest crossing edge is BC 4, and since it is the unique lightest one, it is in every MST.
Which edges does Kruskal add in K, and in what order? How many edges are rejected, and which edges are never examined? What is w(T)?
Answer
The sorted list is DF 1, BE 2, AC 3, BC 4, CD 5, AD 6, AB 7, CE 8, CF 9, EF 10. Each of the first five edges joins two separate trees and is added; no edge is rejected. Since the fifth addition reaches V − 1 = 5, AD, AB, CE, CF, and EF are never examined. w(T) = 1 + 2 + 3 + 4 + 5 = 15.
If Prim is run on K from A, in what order do the vertices enter the tree? What is the key array after C enters the tree?
Answer
The order is A (0), C (3), B (4), E (2), D (5), F (1). After A, the keys are B = 7, C = 3, D = 6, E = F = ∞. When C enters, B drops to 4 through BC and D to 5 through CD; E = 8 and F = 9. The array for A, …, F is 0, 4, 3, 5, 8, 9. The parents end up as B → C, D → C, E → B, F → D; the total is again 15.
In how many rounds does Borůvka finish on K? Which edges are added in each round?
Answer
In round 1, A and C both choose AC 3, B and E both choose BE 2, and D and F both choose DF 1. Three distinct edges are added, and the components {A, C}, {B, E}, and {D, F} form. In round 2, {A, C} and {B, E} choose BC 4, and {D, F} chooses CD 5. Two edges are added and a single component remains: 2 rounds, weight 15.
Which edges does reverse-delete delete on K? At which edge is the first “kept” decision made, and why?
Answer
The deleted edges are EF 10, CF 9, CE 8, AB 7, and AD 6. The first “kept” decision is made at CD 5: after AD and CF are deleted, CD is the only edge connecting D and F to the remaining vertices. After that BC, AC, BE, and DF are also kept because they are bridges.
If Dijkstra is run on K from A, which edges form the shortest-path tree and what is its weight? How does this tree differ from the tree Prim finds from A?
Answer
The distances are B = 7, C = 3, D = 6, E = 9 (A → B → E), F = 7 (A → D → F). The tree consists of the edges AB, AC, AD, BE, DF and has weight 7 + 3 + 6 + 2 + 1 = 19. Prim's tree (AC, BC, CD, BE, DF) has weight 15. Dijkstra reaches B directly by AB 7; the path A → C → B is also 7 and is not shorter. Prim, on the other hand, connects B to C by the edge of weight 4.
A disjoint-set structure with elements 0–6 uses
findwith path compression andunionfrom the slides. The callsunion(0, 1),(2, 3),(0, 2),(4, 5),(6, 4),(5, 0)are made in this order. What is the finalparentarray? What doesfind(6)change afterwards?Answer
Steps:
parent[0] = 1;parent[2] = 3;find(0) = 1,find(2) = 3→parent[1] = 3;parent[4] = 5;find(6) = 6,find(4) = 5→parent[6] = 5. In the last callfind(5) = 5;find(0)follows the path 0 → 1 → 3 and attaches 0 directly to 3. Thenparent[5] = 3is written. The array becomes[3, 3, 3, 3, 5, 3, 5].find(6)follows the path 6 → 5 → 3 and setsparent[6] = 3:[3, 3, 3, 3, 5, 3, 3]. Since 4 is not on this path, it stays attached to 5.How is the maximum spanning tree of K found, and what is its weight?
Answer
Kruskal processes the edges in descending order (or all weights are replaced by −w and ordinary Kruskal is run). The order is EF 10, CF 9, CE 8, AB 7, AD 6, CD 5. EF and CF are added; CE forms a cycle (C–F–E); AB and AD are added; finally CD is added. The tree is EF, CF, AB, AD, CD and its weight is 10 + 9 + 7 + 6 + 5 = 37.
How many edges does the minimum spanning forest have in a graph with 50 vertices and 3 components? What does the Kruskal code from the slides do on this graph?
Answer
Each component needs (component size − 1) edges; the total is 50 − 3 = 47 edges. The code on the slides expects 49 edges. After adding 47 edges the list runs out and
edges.get(k++)throws anIndexOutOfBoundsException.Two versions of Prim are compared on a graph with V = 104 vertices: the array-scan version O(V2) and the binary-heap version O((V + E) log V). Which does less work for E = 5 · 104 and for E = 5 · 107?
Answer
V2 = 108, and log2 104 ≈ 13.3. For E = 5 · 104 the heap version takes about 6 · 104 · 13.3 ≈ 8 · 105 steps; it is better by more than a factor of a hundred. For E = 5 · 107 (nearly all of a complete graph) the heap version takes about 6.6 · 108 steps; the array version is better by a factor of 6–7.
7.14Further reading
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 19 and 21: gives the inverse-Ackermann analysis of disjoint sets and the general MST method, with the notion of a safe edge, together with proofs.
- R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Sections 1.5 and 4.3: presents disjoint sets, lazy and eager Prim, and Kruskal with Java code and experimental measurements.
- R. L. Graham and P. Hell, “On the History of the Minimum Spanning Tree Problem”, Annals of the History of Computing 7(1), 1985: compares the work of Borůvka, Jarník, Kruskal, and Prim and examines the early history of the problem.
- R. E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM 22(2), 1975: the paper that first proved the inverse-Ackermann bound for path compression and union by rank.
7.15References
- O. Borůvka, “O jistém problému minimálním”, Práce Moravské přírodovědecké společnosti 3, 1926.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapter 19: disjoint sets, Chapter 21: MST).
- R. L. Graham, P. Hell, “On the History of the Minimum Spanning Tree Problem”, Annals of the History of Computing 7(1), 43–57, 1985.
- J. B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society 7(1), 1956.
- R. C. Prim, “Shortest Connection Networks and Some Generalizations”, Bell System Technical Journal 36(6), 1957.
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Section 4.3: Minimum Spanning Trees).
- R. E. Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM 22(2), 1975.
Related pages: Chapter 7 slides · © Sercan Külcü. All rights reserved.