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.

Definition 7.1

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.

Theorem 7.1 (Number of edges in a tree)

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.

Definition 7.2

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.

3154276aebcd
Figure 7.1: A weighted graph on vertices a, b, c, d, e. The bold edges (ae = 1, cd = 2, ab = 3, bc = 5) form the minimum spanning tree: w(T) = 1 + 2 + 3 + 5 = 11.

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.

Common mistake

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.

Table 7.1: Number of spanning trees in the complete graph on n vertices, nn−2.
nNumber of spanning trees
33
416
5125
10100,000,000
15about 1.95 · 1015
Example 7.1

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.

152251610781011254118202524124050
Figure 7.2: A graph with 15 vertices and 20 edges that draws the letters M, S, and T. The 14 bold edges form the minimum spanning tree; its total weight is 141. The thin edges (15, 16, 18, 25, 40, 50) are not in the tree.

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.

Common mistake

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.

Definition 7.3

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.

Theorem 7.2 (Cut property)

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.

cut3154276aebcd
Figure 7.3: The cut {a, b} | {c, d, e}. The edges crossing the cut are ae = 1, be = 4, and bc = 5; the lightest, ae = 1, is safe and belongs to the MST.
Example 7.2

Several cuts of the graph in Figure 7.1 can be examined.

  1. {a, b} | {c, d, e}: the crossing edges are ae = 1, be = 4, bc = 5. The lightest is ae, which is in the MST.
  2. {d} | {a, b, c, e}: the crossing edges are cd = 2 and ed = 7. The lightest is cd, which is in the MST.
  3. {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.

Theorem 7.3 (Cycle property)

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. □

3154276aebcd
Figure 7.4: The edges of the cycle b–c–e have weights 4, 5, and 6. The heaviest edge, ec = 6, is in no MST.

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.

Table 7.2: The two properties and the algorithms that use them.
PropertyWhat it saysAlgorithms that use it
Cut propertyThe lightest edge crossing a cut can safely be added.Kruskal, Prim, Borůvka
Cycle propertyThe 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.

Theorem 7.4 (Uniqueness of the MST)

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.

Table 7.3: Overview of the greedy MST algorithms.
AlgorithmIdeaHelper structureTime
Kruskal (1956)Sort the edges from lightest to heaviest and add those that do not form a cycledisjoint setsO(E log E)
Prim (1957)Start at one vertex and grow the tree by the cheapest adjacent edgepriority queueO((V + E) log V)
Borůvka (1926)Every component adds its own cheapest edge simultaneouslydisjoint setsO(E log V)
Reverse-deleteTry the edges from heaviest to lightest and delete any whose removal keeps the graph connectedBFS/DFS or disjoint setsO(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.

1223457abcdefgreen: chosen · red: cycle (skip)blue: next, joins two trees
Figure 7.5: An intermediate state of Kruskal: a forest of two trees. The green edges are chosen. The red dashed edge of weight 4 connects two vertices of the same tree and would close a cycle, so it is skipped. The blue edge of weight 5 joins the two trees and is added.

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:

  1. Sort all the edges of the graph in increasing order of weight.
  2. From the sorted list, take the next edge of smallest weight.
  3. If the edge joins two vertices that belong to different trees, add it to the tree and merge the two trees.
  4. If the edge connects two vertices of the same tree, it would form a cycle and is skipped.
  5. 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 MST

The 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.

Example 7.3
  1. Start. Every vertex is a separate tree: {a} {b} {c} {d} {e}. No edge is chosen, w(T) = 0.
  2. Sorting. The edges are arranged by increasing weight: ae 1, cd 2, ab 3, be 4, bc 5, ec 6, ed 7.
  3. 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.
  4. 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.
  5. 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.
  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.
  7. 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.

ae1cd2ab3be4bc5ec6ed73154276aebcd
Figure 7.6: The step be = 4. The table above shows the sorted edges: green ones are chosen, the red one is rejected, and the blue ones have not been examined yet. Because b and e are in the same tree (blue vertices), be would close a cycle.

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.

Common mistake

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?

Theorem 7.5 (Correctness of Kruskal)

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

Definition 7.4

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.

Table 7.4: The cycle test with disjoint sets in Kruskal. The last column gives the parent array in the order a, b, c, d, e.
Edgefind(u)find(v)Decisionparent
start———a b c d e
ac = 1acadd, parent[a] = cc b c d e
de = 2deadd, parent[d] = ec b c e e
ab = 3cbadd, parent[c] = bc b b e e
bc = 4bbsame root: cycle, skipc b b e e
bd = 5beadd, parent[b] = ec 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.

1234567acbdeDisjoint-set forest (arrow: parent)abcdeparent[ ]caebbcedee
Figure 7.7: The disjoint-set forest after the MST is complete. The parent links have built the chain a → c → b → e; 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.

1234567acbdeDisjoint-set forest (arrow: parent)abcdeparent[ ]eaebecedee
Figure 7.8: The forest after the call 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).

Table 7.5: Trace of find and union. The parent array is given for indices 0, 1, 2, 3, 4.
StepEventparent
0start, every element is a root[0, 1, 2, 3, 4]
1union(0, 1): find(0) = 0, find(1) = 1 → parent[0] = 1[1, 1, 2, 3, 4]
2union(1, 2): roots 1 and 2 → parent[1] = 2[1, 2, 2, 3, 4]
3union(2, 3): roots 2 and 3 → parent[2] = 3[1, 2, 3, 3, 4]
4find(0) descends: 0 → 1 → 2 → 3; 3 is a root[1, 2, 3, 3, 4]
5on return: parent[2] = 3 (unchanged)[1, 2, 3, 3, 4]
6on return: parent[1] = 3[1, 3, 3, 3, 4]
7on return: parent[0] = 3; find(0) = 3[3, 3, 3, 3, 4]
8union(4, 0): find(4) = 4, find(0) = 3 (one step) → parent[4] = 3[3, 3, 3, 3, 3]
disjoint-set forest (arrow: parent)01234parent[ ]1021323344
Figure 7.9: The forest after three unions: because one root is attached under the other each time, the chain 0 → 1 → 2 → 3 has formed.

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.

disjoint-set forest (arrow: parent)01234parent[ ]3031323344
Figure 7.10: The forest after the call find(0): the vertices 0, 1, and 2 on the path are attached directly to the root 3.
Common mistake

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.

Theorem 7.6 (Rank and set size)

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.

Common mistake

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.

22344612534
Figure 7.11: A five-vertex graph: (1,3) = 2, (2,5) = 2, (1,2) = 3, (2,3) = 4, (3,4) = 4, (1,4) = 6. The same graph is also used in the Prim traces.
Table 7.6: Trace of kruskal(5, edges). parent is given for indices 1–5.
Edge ex = find(u)y = find(v)Actionparentw(T)
———init[1, 2, 3, 4, 5]0
(1,3) = 213add, parent[1] = 3[3, 2, 3, 4, 5]2
(2,5) = 225add, parent[2] = 5[3, 5, 3, 4, 5]4
(1,2) = 335add, parent[3] = 5[3, 5, 5, 4, 5]7
(2,3) = 455cycle, skip[3, 5, 5, 4, 5]7
(3,4) = 454add, 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.

22344612534
Figure 7.12: The result of Kruskal: (1,3), (2,5), (1,2), (3,4); total weight 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

EF1CF1DE2FH3AB4EH5GI5DG6AC7BD9EG10BC11HI12EI15BF2047119201126101553512ABCDEFGHISets: singletons · Weight: 0 · Connected: NO
Figure 7.13: The nine-vertex graph and the table of sorted edges. No edge has been chosen yet.
Table 7.7: Kruskal on the nine-vertex graph.
EdgeDecisionSets (singletons omitted)Total
EF 1add{E, F}1
CF 1add{C, E, F}2
DE 2add{C, D, E, F}4
FH 3add{C, D, E, F, H}7
AB 4add{C, D, E, F, H} {A, B}11
EH 5cycle (E–F–H)unchanged11
GI 5add{C, D, E, F, H} {A, B} {G, I}16
DG 6add{C, D, E, F, G, H, I} {A, B}22
AC 7add{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}.

EF1CF1DE2FH3AB4EH5GI5DG6AC7BD9EG10BC11HI12EI15BF2047119201126101553512ABCDEFGHISets: {C, D, E, F, H} {A, B} · Weight: 11 · Connected: NO
Figure 7.14: The step EH = 5. E and H are already in the same set through the path E–F–H; the edge would close a cycle and is not added.
EF1CF1DE2FH3AB4EH5GI5DG6AC7BD9EG10BC11HI12EI15BF2047119201126101553512ABCDEFGHISets: {A, B, C, D, E, F, G, H, I} · Weight: 29 · Connected: YES
Figure 7.15: After adding AC = 7: eight edges have been chosen, the graph is connected, and the MST has weight 29.

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.

Table 7.8: Complexity analysis of Kruskal.
ActionTimesCost
Sorting the edges by weight1O(E log E)
create(V)1O(V)
find (2 per edge)≤ 2EO(E · α(V)) with path compression + rank; O(E log V) with rank only
unionV − 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.

Example 7.4

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.

236471sabcdcheapest edge crossing the cut: 4
Figure 7.16: An intermediate state of Prim. The tree is {s, a, b}. The dashed line shows the cut between the tree and the remaining vertices. The edges crossing the cut have weights 6, 7, and 4; the cheapest, 4, is chosen and d enters the tree.

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.

Definition 7.5

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:

  1. Choose a starting vertex and add all edges belonging to it to the priority queue.
  2. From the queue, select the edge of smallest weight that leads to a vertex not in the tree.
  3. Add the new vertex connected by the selected edge to the tree.
  4. 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 MST

The 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).

Common mistake

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.

Table 7.9: Prim with a priority queue, source 1. The queue contents are sorted by key; each item has the form vertex (key, π).
StepVertex extractedEdge addedQueue Q (after)w(T)
0——1 (0, /), 2 (∞, /), 3 (∞, /), 4 (∞, /), 5 (∞, /)0
11—3 (2, 1), 2 (3, 1), 4 (6, 1), 5 (∞, /)0
23(1,3) = 22 (3, 1), 4 (4, 3), 5 (∞, /)2
32(1,2) = 35 (2, 2), 4 (4, 3)5
45(2,5) = 24 (4, 3)7
54(3,4) = 4empty11

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.

22344612534
Figure 7.17: The state after 1 leaves the queue. The dashed blue lines are the cheapest connections, shown with π, that are not yet final: 2 to 3, 3 to 2, 6 to 4.

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.

22344612534
Figure 7.18: The final state of Prim: the queue is empty. The MST consists of the edges (1,3), (1,2), (2,5), (3,4); w(T) = 11.

7.5.5Why is Prim correct?

Theorem 7.7 (Correctness of Prim)

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.

1332654432ABCDEF
Figure 7.19: The A–F graph. The source is B; initially all keys are ∞ and key[B] = 0.
Table 7.10: Trace of prim(G, 1). The key array is given in the order A, B, C, D, E, F; ∞ is the initial value.
Round suNeighbors updatedkeyw(T)
——init∞, 0, ∞, ∞, ∞, ∞0
0B (0)A → 1, C → 3, D → 2, E → 6, F → 5 (parent B in all cases)1, 0, 3, 2, 6, 50
1A (1)none: AD = 3 > key[D] = 21, 0, 3, 2, 6, 51
2D (2)E → 3 (parent D)1, 0, 3, 2, 3, 53
3C (3)F → 4 (parent C); CE = 4 > 3, E unchanged1, 0, 3, 2, 3, 46
4E (3)F → 2 (parent E)1, 0, 3, 2, 3, 29
—(F)loop ends; the parent of F is E1, 0, 3, 2, 3, 211

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.

1332654432ABCDEF
Figure 7.20: The fourth round: the keys of C and E are equal (3); C, with the smaller index, enters the tree. The blue dashed edges are the current cheapest connections of the vertices not yet in the tree.

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.

1332654432ABCDEF
Figure 7.21: The result of Prim: AB, BD, BC, DE, EF; total 11.

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.

Table 7.11: Trace of primPQ(1). Entries have the form (vertex, key); key is given for indices 1–5.
Queue (before)ExtractedActionkey
(1,0)(1,0)1 enters the tree; 2 → 3, 3 → 2, 4 → 60, 3, 2, 6, ∞
(3,2) (2,3) (4,6)(3,2)3 enters (edge 1–3); 4 → 4; for 2, 4 > 3, unchanged0, 3, 2, 4, ∞
(2,3) (4,4) (4,6)(2,3)2 enters (edge 1–2); 5 → 20, 3, 2, 4, 2
(5,2) (4,4) (4,6)(5,2)5 enters (edge 2–5); no update0, 3, 2, 4, 2
(4,4) (4,6)(4,4)4 enters (edge 3–4); no update0, 3, 2, 4, 2
(4,6)(4,6)4 is already in the tree: stale entry, continue0, 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.

22344612534pq
Figure 7.22: The last step: the stale entry (4,6) has been extracted and skipped; the queue is empty. The tree edges are 1–3, 1–2, 2–5, 3–4.

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.

Table 7.12: Prim on the nine-vertex graph (from A). Each cell holds key / parent; “−” means that no parent has been assigned.
EnteringABCDEFGHITotal
A0/−4/A7/A∞∞∞∞∞∞0
B0/−4/A7/A9/B∞20/B∞∞∞4
C0/−4/A7/A9/B∞1/C∞∞∞11
F0/−4/A7/A9/B1/F1/C∞3/F∞12
E0/−4/A7/A2/E1/F1/C10/E3/F15/E13
D0/−4/A7/A2/E1/F1/C6/D3/F15/E15
H0/−4/A7/A2/E1/F1/C6/D3/F12/H18
G0/−4/A7/A2/E1/F1/C6/D3/F5/G24
I0/−4/A7/A2/E1/F1/C6/D3/F5/G29

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.

47119201126101553512ABCDEFGHI
Figure 7.23: After H enters the tree: total 18. The red dashed edge EH = 5 would now form a cycle; the blue dashed edges are the current cheapest connections for G and I.

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.

47119201126101553512ABCDEFGHI
Figure 7.24: I enters: all vertices are in the tree and the MST has weight 29.

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.

Table 7.13: The cost of different implementations of Prim.
ImplementationExtract minDecrease keyTotal
Adjacency matrix + array scanV × O(V)O(1)O(V2)
Adjacency list + binary heapV × 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 heapO(log V) amortizedO(1) amortizedO(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).

Example 7.5

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.

  1. E = 5000 (sparse): E log V ≈ 5000 · 10 = 5 · 104. The heap version does about 20 times less work.
  2. 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.

Table 7.14: Comparison of Prim and Dijkstra.
Prim (MST)Dijkstra (shortest paths)
key[v]the single cheapest edge connecting v to the treetotal path length from the source to v
Updatew(u, v) < key[v]dist[u] + w(u, v) < dist[v]
Resulttree of smallest total weightshortest-path tree
Sourcedoes not affect the result (same weight)determines the result
Negative weightsno problemdoes not work correctly
Example 7.6

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.

Common mistake

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.

1429367518abcdefghround 1: each vertex chooses itsown cheapest edge → 8 components become 3
Figure 7.25: The first round of Borůvka. Each vertex chooses its own cheapest edge: ab = 1, cd = 2, bf = 3, ef = 6, gh = 1. Five edges are added at once; eight components drop to three.

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

  1. At the start every vertex counts as a component (set) by itself.
  2. For each component, find the edge of smallest weight that connects it to another component.
  3. Add all the edges found; merge the components they connect. The same edge is not added twice.
  4. 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 MST

Borů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.

Table 7.15: Borůvka on the six-vertex graph, round 1. Each component and its own cheapest outgoing edge.
ComponentOutgoing edgesCheapest
{A}AB 1, AD 4AB 1
{B}AB 1, BC 5, BE 3, BD 7, BF 6AB 1
{C}BC 5, CF 9BC 5
{D}AD 4, BD 7, DE 8AD 4
{E}BE 3, DE 8, EF 2EF 2
{F}BF 6, CF 9, EF 2EF 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.

154736982ABCDEF
Figure 7.26: Round 1: the cheapest outgoing edge chosen by each component is shown in blue. Four distinct edges are chosen.

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.

154736982ABCDEF
Figure 7.27: End of round 2: BE has been added and a single component remains. The MST has weight 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

Table 7.16: Borůvka rounds on the twelve-vertex graph.
RoundCheapest edges of the componentsDistinct edges addedNumber of componentsTotal
1A: 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 4AC, BD, EF, GI, GH, JL, GK12 → 543
2{A, C}: BC 7, {B, D}: DF 3, {E, F}: DF 3, {G, H, I, K}: KL 12, {J, L}: KL 12BC, DF, KL5 → 265
3{A, …, F}: EJ 18, {G, …, L}: EJ 18EJ2 → 183

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.

1367114820932181519105171116412ABCDEFGHIJKL
Figure 7.28: Round 2: the five components (in colors) and the cheapest outgoing edge of each (blue). The thick green edges were added in round 1.

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.

1367114820932181519105171116412ABCDEFGHIJKL
Figure 7.29: End of round 3: EJ has been added; all twelve vertices are in one component. The MST 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.

Table 7.17: Trace of the Borůvka code (six-vertex example).
StageEventcomponentCount
Round 1, scanAB(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, addcheapest[A] = AB: roots A, B → add, parent[A] = B5
cheapest[B] = AB: both endpoints in the same component → skip5
cheapest[C] = BC: roots B, C → add, parent[B] = C4
cheapest[D] = AD: roots C, D → add, parent[C] = D3
cheapest[E] = EF: roots E, F → add, parent[E] = F2
cheapest[F] = EF: same component → skip2
Round 2, scanAB, 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, addcheapest[D] = BE: roots D, F → add, parent[D] = F1
cheapest[F] = BE: same component → skip; loop ends1

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.

154736982ABCDEF
Figure 7.30: The scan of round 2: the cheapest edge between the two components (colors), BE(3), is shown dashed in blue.

7.7.6Complexity and tie-breaking

Theorem 7.8 (Number of Borůvka rounds)

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.

Common mistake

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.

349abc
Figure 7.31: The basic step of reverse-delete: the heaviest edge of the cycle a–b–c, of weight 9, is deleted; a and c are still connected through b.

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

  1. Sort all the edges in descending order of weight.
  2. Delete the next heaviest edge.
  3. If the graph is no longer connected, put the deleted edge back.
  4. 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 MST

The 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

Table 7.18: Reverse-delete on the seven-vertex graph.
EdgewStill connected if deleted?Result
3–415yesdeleted
5–611yesdeleted
1–39yesdeleted
4–69no: 6 would be isolatedkept
1–28yesdeleted
4–58yesdeleted
1–4, 0–1, 3–5, 2–4, 0–37, 7, 6, 5, 5no: each is a bridgekept

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.

58911871596752465130
Figure 7.32: The step 4–6 = 9. The gray dotted edges have been deleted. Since 5–6 has been deleted, the only connection of 6 is 4–6 (red dashed); if the edge were deleted, 6 would be cut off, so it is put back.

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.

Table 7.19: Trace of reverseDelete(7, edges).
EdgeisConnectedActioni (after)
DE 15truestays deleted0
FG 11truestays deleted0
BD 9truestays deleted0
EG 9false: G is isolatedput back1
BC 8truestays deleted1
EF 8truestays deleted1
AB 7false: {A, D, F} gets cut offput back2
BE 7false: {C, E, G} gets cut offput back3
DF 6false: {F} gets cut offput back4
AD 5false: {D, F} gets cut offput back5
CE 5false: {C} gets cut offput back6

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.

7589751568911ABCDEFG
Figure 7.33: The result of reverse-delete: AB, AD, BE, CE, DF, EG; total 39. The gray dotted edges have been deleted.
Common mistake

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.

Table 7.20: Comparison of the four MST algorithms.
KruskalPrimBorůvkaReverse-delete
Perspectiveedge-orientedvertex-orientedcomponent-orientededge-oriented (deletion)
Intermediate stateforestsingle treeforestconnected graph
Property usedcutcutcutcycle
Data structuresorted edges + disjoint setspriority queue / arraydisjoint setsBFS/DFS
TimeO(E log E)O(V2) or O((V + E) log V)O(E log V)O(E · (V + E))
Best suited forsparse graphsdense graphsparallel / distributedteaching, theory
Disconnected graphgives a forestone componentgives a forestpreserves 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.

Common mistake

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.

Common mistake

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).

Common mistake

Adding distances in Prim. Writing key[u] + w gives Dijkstra. In Prim the key is the weight of a single edge only.

Common mistake

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.

Common mistake

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.

Common mistake

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. A disjoint-set structure with elements 0–6 uses find with path compression and union from the slides. The calls union(0, 1), (2, 3), (0, 2), (4, 5), (6, 4), (5, 0) are made in this order. What is the final parent array? What does find(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 call find(5) = 5; find(0) follows the path 0 → 1 → 3 and attaches 0 directly to 3. Then parent[5] = 3 is written. The array becomes [3, 3, 3, 3, 5, 3, 5]. find(6) follows the path 6 → 5 → 3 and sets parent[6] = 3: [3, 3, 3, 3, 5, 3, 3]. Since 4 is not on this path, it stays attached to 5.

  8. 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.

  9. 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 an IndexOutOfBoundsException.

  10. 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

  1. O. Borůvka, “O jistém problému minimálním”, Práce Moravské přírodovědecké společnosti 3, 1926.
  2. 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).
  3. 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.
  4. 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.
  5. R. C. Prim, “Shortest Connection Networks and Some Generalizations”, Bell System Technical Journal 36(6), 1957.
  6. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Section 4.3: Minimum Spanning Trees).
  7. 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.