Data Structures and Algorithms with C · Lecture Notes

Chapter 17: Minimum Spanning Trees

A subgraph that connects all the vertices of a graph without forming a cycle is called a spanning tree. If the edges have a cost, we look among these trees for the one with the smallest total cost. Connecting villages to the electric grid with the least cable, or adding computers to a network with the cheapest links, are examples of this problem. The chapter starts with the definition, the number and the properties of spanning trees. Then come two classic greedy algorithms. Kruskal's algorithm tries edges from cheapest to most expensive and catches cycles with sets (union-find). Prim's algorithm grows a single tree by the cheapest edge and is coded with arrays or with a heap. The C code of both algorithms is explained line by line, traced step by step on the same example graph, and its cost is computed with justification. The main lesson of the chapter is this: the same algorithm runs at a completely different speed depending on the data structure chosen.

Learning outcomes

Define
Explain the spanning tree, tree edges and nontree edges, and the spanning trees produced by depth-first or breadth-first search.
Count
Discuss ways of generating the spanning trees of a graph, the notion of isomorphism and why the number of trees grows so fast.
Kruskal
Code in C and trace by hand Kruskal's algorithm, which selects edges by increasing cost and catches cycles with the union-find structure.
Prim
Implement Prim's algorithm, which grows a single tree, with O(n²) arrays and with a heap.
Analyze
Compare the bounds O(e log e), O(n²) and O(e log n); choose the algorithm according to whether the graph is dense or sparse.
Approach
See how a min-heap and disjoint sets speed up an algorithm: first discover the data structure, then code.

17.1Spanning trees

A graph G = (V, E) consists of vertices (V) and edges (E) that join pairs of vertices. In this chapter the number of vertices is written n = |V| and the number of edges e = |E|, and unless stated otherwise the graph is undirected. If there is a path between every pair of vertices, the graph is connected. A path that returns to the vertex it started from is a cycle. A connected graph without cycles is a tree; there is no need to choose a root in a tree.

The whole question of this chapter fits in one sentence: which of a graph's edges are enough to connect its vertices, and which of these is the cheapest? Let us first make the word “enough” precise.

17.1.1A traversal splits the edges into two groups

There are two basic ways to traverse a graph. Depth-first search (DFS) moves to a neighbor and descends as deep as possible; when there is nowhere left to go it backtracks. It is written with recursion or with a stack. Breadth-first search (BFS) visits all neighbors of the start vertex, then their neighbors; it is written with a queue. Both mark each vertex once and finish in O(n + e) time with adjacency lists.

When a traversal has visited all the vertices of a connected graph, the edges have been divided into two groups:

  • T: tree edges. These are the edges that the traversal processed, that is, edges that lead to a vertex not seen before. Every vertex other than the start is reached exactly once by such an edge. So the number of tree edges is exactly n − 1.
  • N: nontree edges. These are the edges the traversal looked at but did not process; their other endpoint is already marked. In DFS they are also called back edges, in BFS cross edges.
0123456701234567depth-first spanning tree (from 0)breadth-first spanning tree (from 0)
Figure 17.1: The DFS (left) and BFS (right) spanning trees of the eight-vertex example graph, starting from 0. The thick red edges are tree edges; the dashed ones are nontree edges. DFS: N = {(0,2), (1,4), (6,7)}; BFS: N = {(4,7), (5,7), (6,7)}.

The graph in Figure 17.1 has 10 edges: (0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7), (4,7), (5,7), (6,7). The adjacency lists are sorted in increasing order. Table 17.1 shows in order which edge DFS processes or skips, and why.

Table 17.1: DFS from 0 on the graph in Figure 17.1. Each row is a look at one edge; “tree” is a processed edge, “nontree” is an edge skipped because it leads to a marked vertex.
OrderCurrent vertexEdge examinedOther endpointResult
10(0,1)1 newtree
21(1,0)0 is markededge we came by
31(1,3)3 newtree
43(3,7)7 newtree
57(7,4)4 newtree
64(4,1)1 is markednontree: (1,4)
77(7,5)5 newtree
85(5,2)2 newtree
92(2,0)0 is markednontree: (0,2)
102(2,6)6 newtree
116(6,7)7 is markednontree: (6,7)

The seven tree edges are (0,1), (1,3), (3,7), (7,4), (7,5), (5,2), (2,6); this agrees with the expectation n − 1 = 7. The other edges looked at during the returns (for example 1 in the list of 3) were not written into the table because they give no new information. When BFS starts from 0 on the same graph, it first marks 1 and 2, then 3, 4, 5, 6 and finally 7. The tree edges are (0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (3,7). The first edge to reach 7 is (3,7); (4,7), (5,7), (6,7) remain outside the tree.

The two traversals produced two different trees from the same graph. Both span all the vertices, and neither has a cycle. So the “edges enough to connect all the vertices” are not a single set. Other trees come out again when the start vertex or the order of the neighbors changes.

17.1.2Definition of a spanning tree

Definition 17.1

Let G = (V, E) be a connected graph. A tree that contains all the vertices of G and whose edges are chosen from E is called a spanning tree of G. A spanning tree has n vertices and n − 1 edges; it has no cycle.

The two conditions in the definition complement each other. “Contains all the vertices” makes the tree spanning: no vertex is left out. “Its edges are chosen from E” forbids inventing new connections: only edges that exist in the graph can be used. A graph that is not connected has no spanning tree. In such a graph each component has its own spanning tree, and their collection is called a spanning forest.

K4a)b)c)d)e)
Figure 17.2: The complete graph on four vertices, K4, and five of its spanning trees. a, c, d, e are paths; b is a star.

The K4 on the left of Figure 17.2 is the complete graph: every pair of vertices is joined by an edge, for a total of 4 · 3 / 2 = 6 edges. Each of the five drawings next to it selects three of these six edges. All four vertices are used in each and none has a cycle; all five are spanning trees.

Of these five trees, a, c, d and e have the same shape: four vertices lined up on a single line. Only the position of each vertex along the path differs. b is different: one vertex is connected directly to the other three. The first shape is called a path, the second a star.

Definition 17.2

Two graphs are isomorphic if their vertices can be matched one to one and, under this matching, the edges of one correspond exactly to the edges of the other. Isomorphism is denoted by ≡.

For the trees in the figure we write a ≡ c ≡ d ≡ e; b is isomorphic to none of them. A quick way to see this is to look at the degrees. In a path two vertices have degree 1 and two have degree 2. In a star one vertex has degree 3 and three have degree 1. Two isomorphic graphs must have the same degree sequence; since it differs here, a and b cannot be isomorphic. The converse is not true: two graphs with the same degree sequence need not be isomorphic. So comparing degrees can only refute isomorphism, not prove it.

Counting the spanning trees of K4 is easy. Three of the six edges can be chosen in C(6, 3) = 20 ways. Four of these choices are triangles: choosing three of the four vertices and taking the three edges among them forms a cycle and leaves the fourth vertex out. All of the remaining 16 choices are trees. The number of stars equals the number of choices of the center: 4. The number of paths is found from the orderings of the four vertices. There are 4! = 24 orderings, but each path is read twice (from either end). The number of paths is 24 / 2 = 12. The total is 12 + 4 = 16.

Theorem 17.1 (Cayley's formula)

The number of spanning trees of the complete graph Kn on n vertices is nn−2.

For n = 4 the formula gives 42 = 16, which agrees with the count above. The number grows very fast: K5 has 125 spanning trees and K10 has a hundred million. The proof is outside the scope of this chapter. What matters here is the consequence: generating spanning trees one by one and choosing the best is a hopeless task even for small graphs. Once the edges are given weights, the question “how many?” turns into “which is the cheapest?”, and the size of this number confronts us again.

17.1.3Isomorphism, drawings and planarity

A graph is not just its picture on paper. The graph is determined by its vertices and edges; the positions of vertices on the paper are a choice. The same graph can be drawn in forms that look nothing alike. Figure 17.3 is a striking example.

123abc1b2a3cK3,3another drawing: a single crossing (red)
Figure 17.3: Two drawings of the same graph (K3,3). On the left the nine edges cross at many points. In the drawing on the right only the red dashed edge (a,2) crosses the edge (b,3).

K3,3 consists of six vertices split into two groups: {1, 2, 3} and {a, b, c}. Each vertex of each group is connected to the three vertices of the other group and not to those in its own group. There are 3 · 3 = 9 edges in total. The drawing on the left applies this definition directly and the edges tangle with one another. In the drawing on the right the vertices are placed elsewhere and the edge (1,c) is routed around the outside. All nine edges are still there, but now only one crossing remains.

Showing that two drawings are the same graph means showing isomorphism: every vertex on the left corresponds to a vertex on the right, and the edges are matched accordingly. The matching here is easy, because the labels have been kept. Given two unlabeled drawings, the problem gets harder. Simple criteria such as the degree sequence are not enough; splitting the vertices into layers with DFS or BFS helps narrow the matching but gives no general solution. Graph isomorphism is a famous problem whose status, whether an efficient algorithm is known, was debated for a long time. The instructor suggests this problem as a nice senior-year project: a program that turns one drawing into the other with a three-dimensional display and finds which vertices have to move. The instructor then adds that questions of this kind are really hard and can be tackled seriously only at the master's or doctoral level. What is stressed is not that the problem is unsolvable, but that it takes effort.

The question of crossings has a name as well. A graph that can be drawn without any edges crossing is called planar. K3,3 is not planar: however the vertices are placed, at least one crossing remains. The drawing on the right reaches this lower bound. The question has a concrete counterpart in engineering. On a printed circuit board, conductor tracks cannot cross on the same layer. A circuit that must be connected in the form of K3,3 does not fit on a single layer and needs at least two.

17.1.4How many different spanning trees are there?

The crudest way to generate spanning trees is to try all possible edge sets. Since a spanning tree has exactly n − 1 edges, n − 1 of the e edges are chosen. This can be done in C(e, n − 1) ways. For each choice it is checked whether there is a cycle; those without cycles are trees. If isomorphic trees are not to be counted separately, the isomorphic ones must also be weeded out.

Consider a graph with four vertices in the shape of a square: the vertices A, B, C, D are connected in order, and there is also a diagonal between A and C. Three of the five edges can be chosen in C(5, 3) = 10 ways. Two of these are triangles (ABC and ACD) and form a cycle; 8 spanning trees remain.

A cleverer method is to start from one spanning tree and move to the other trees by exchanging edges. Figure 17.4 shows the method step by step.

ABCDinitial tree T (3 edges)ABCD+ (D,A) → cycle A-B-C-D-AABCD(A,B) removed → new treeABCD(B,C) removed → new tree
Figure 17.4: Generating spanning trees by exchanging along a cycle. Top left: the tree T found by DFS. Top right: the nontree edge (D,A) has been added and the cycle A-B-C-D-A has formed. Bottom row: removing (A,B) and (B,C) from the cycle gives two new trees.
  1. First a spanning tree is found, for example by DFS. In the figure, T = {(A,B), (B,C), (C,D)}.
  2. A nontree edge is added. Since there is a single path between every pair of vertices in a tree, the new edge forms exactly one cycle. When (D,A) is added, the cycle is A-B-C-D-A.
  3. One of the edges on the cycle is removed. The cycle is broken, the vertices stay connected, and the result is a new spanning tree. Removing (A,B) gives {(B,C), (C,D), (D,A)}. Putting (A,B) back and removing (B,C) gives another one, and removing (C,D) a third.
  4. The process is repeated for all nontree edges and for every new tree found. On this graph all 8 spanning trees are reached in the end.

The method works but is long. The same tree is reached many times by different routes, and every new tree must be checked separately for whether it was found before. That is why it is not preferred for counting trees or finding the cheapest tree. When an exact count is needed, Kirchhoff's matrix-tree theorem is used. This theorem gives the number in one stroke by taking the determinant of a matrix built from the degree and adjacency information of the graph. By the theorem, the eight-vertex graph in Figure 17.1 has 64 spanning trees and the seven-village graph, the main example of the chapter, has 46. The details of the theorem are an advanced topic.

17.1.5Properties of spanning trees

A spanning tree has four properties that are used in algorithms. Figure 17.5 shows them on the BFS spanning tree.

012345670123456701234567
Figure 17.5: Properties of a spanning tree. Left: the BFS spanning tree: 8 vertices, 7 edges. Middle: the nontree edge (6,7) has been added and the cycle 6-2-0-1-3-7-6 has formed. Right: the tree edge (0,2) has been deleted and {2, 5, 6} has been cut off from the tree.
Theorem 17.2 (Properties of a tree)

For a graph T with n vertices, any two of the following three properties imply the third: (i) T is connected; (ii) T has no cycle; (iii) T has exactly n − 1 edges. In that case T is a tree and the following also hold:

  1. There is a single path between every pair of vertices.
  2. Adding an edge to the tree creates exactly one cycle.
  3. Deleting any edge of the tree splits it into two pieces.

From (i) and (ii) to (iii): a connected graph without cycles has at least one leaf (a vertex of degree 1). One end of a longest path must be a leaf; otherwise the path could be extended or a cycle would close. Deleting a leaf and the single edge touching it neither breaks connectivity nor creates a cycle. When this deletion is repeated n − 1 times, a single vertex and zero edges remain; so there were n − 1 edges at the start. The unique-path property follows from this too: if there were two different paths between two vertices, these paths would join to form a cycle. When an edge (u, v) is added, the single tree path between u and v is closed by the new edge and exactly one cycle forms. When an edge is deleted, the single path between its endpoints is broken and the endpoints end up in separate pieces. The other two directions are shown by similar counting. ∎

In the figure these properties can be seen one by one. The BFS tree in the left drawing connects 8 vertices with 7 edges. In the middle drawing, when (6,7) is added, the new edge joins the single tree path 6-2-0-1-3-7 from 6 to 7 and the cycle 6-2-0-1-3-7-6 is closed. This graph is no longer a tree. In the right drawing, when (0,2) is deleted, vertices 2, 5 and 6 can no longer be connected to 0. A spanning tree is the subgraph with the fewest edges among those that keep the vertices connected. One edge too many means a cycle, one edge too few means a disconnection.

Using the second and third properties together gives a method for generating spanning trees: add a nontree edge, and remove an edge from the single cycle that forms. The correctness proofs of the minimum spanning tree algorithms also rest on the same two properties.

The applications of spanning trees also come from these properties:

  • Discarding redundant links. In a computer network, cycles can make a broadcast packet circulate forever. A spanning tree of the network is chosen and only its links are used.
  • Broadcast tree. To send a message from one source to all vertices, the edges of the spanning tree are followed; each vertex receives the message once.
  • Electric circuits. Kirchhoff used spanning trees to find an independent set of circuit equations. Each nontree edge forms a single cycle; each of these cycles gives an independent voltage equation.

17.2The minimum-cost spanning tree

17.2.1The weighted graph and the problem

In real problems the edges are not equal. The road between two cities has a length, the line between two computers has a rental fee, the cable to be laid between two villages has a cost. A graph whose edges have been assigned such a number is a weighted graph, and G(V, E, w) is written instead of G(V, E). Here w(u, v) is the weight of the edge (u, v). In this chapter the weight is also called the cost.

Definition 17.3

The cost of a spanning tree of a connected weighted graph is the sum of the weights of the edges in the tree. The spanning tree with the smallest cost is called the minimum spanning tree (MST).

The definition says “the smallest one”, not “the smallest ones”; even so, more than one spanning tree can have the same smallest cost. If all edge weights are distinct, the minimum spanning tree is unique. If there are equal weights there may be several trees, but all have the same cost.

Two example problems make this concrete. In the first, the vertices are the computers of an institution, and the edge weights are the cost of laying a line between two computers. We look for the cheapest set of lines that connects all the computers to one another. In the second, electric or fiber-optic cable is to be taken to seven villages. A feasibility study has worked out how many kilometers of cable are needed from which village to which. For pairs of villages that cannot be connected directly because there is a mountain or a lake between them, the cost is infinite; these edges are not written into the graph at all.

2810161412221825240156243
Figure 17.6: The main example of the chapter: seven villages (0–6) and the lengths in kilometers of the cables that can be laid between them. There are nine edges.

The edges of the graph in Figure 17.6 with their weights are: (0,1) = 28, (0,5) = 10, (1,2) = 16, (1,6) = 14, (2,3) = 12, (3,4) = 22, (3,6) = 18, (4,5) = 25, (4,6) = 24. All the Kruskal and Prim traces in the chapter are on this graph. The graph has 46 spanning trees. Six of the nine edges can be chosen in C(9, 6) = 84 ways; 38 of these form cycles. The costs of the 46 trees range from 99 to 129. The cost of the cheapest tree is 99 and it is unique; the two cheapest trees after it have cost 101. These numbers were found by trying all the choices one by one on a computer. The goal is to reach the tree of cost 99 directly, without doing this trial.

The instructor underlines an important point here: when looking for a minimum spanning tree, cycles are avoided. A village receiving electricity by two routes, for example laying a backup line so that “if power does not come from Lower Tepecik, let it come from Upper Tepecik”, is not the subject of this problem. A cycle means a backup connection, and a backup connection is extra cost. Networks that require reliability are designed with other problems.

17.2.2The greedy approach

Many algorithms are known for the minimum spanning tree: the algorithms of Kruskal, Prim and Sollin (Borůvka) are the best known; there is also a method called reverse-delete. This chapter concentrates on the first two; the other two are described briefly.

There are a few general methods in algorithm design. Backtracking extends a partial solution step by step and, on reaching a dead end, undoes the last decision. Dynamic programming stores the solutions of small subproblems and builds the larger ones from them. The greedy method, on the other hand, makes the choice that looks best at the moment at every step and never changes this choice again. The instructor calls this attitude “stubborn”: a greedy algorithm does not go back; once it has taken an edge it does not let it go.

Minimum spanning tree algorithms are greedy and obey three rules:

  1. An edge that forms a cycle is not taken.
  2. Among the edges that can be chosen, the one with the least cost is preferred.
  3. In a graph with n vertices exactly n − 1 edges are chosen.

The first rule makes the result a tree and the third makes it span all the vertices; together they are conditions (ii) and (iii) of Theorem 17.2. The second rule keeps the cost small. The difference between the algorithms lies in how they define the set of “edges that can be chosen”. In Kruskal's this set is all the edges not yet tried. In Prim's it is only the edges that touch the growing tree.

The slides of the chapter open with a saying attributed to Michelangelo: “Beauty is the purgation of superfluities.” A minimum spanning tree is exactly this: the plainest network that preserves connectivity, with the excess thrown away.

17.2.3Why does the greedy choice give the right result?

Greedy algorithms do not find the best result in most problems. Choosing the largest coin each time to make change uses too many coins in some currency systems. So for the minimum spanning tree we must show why the greedy choice is never regretted. The key to this is the cut property.

Definition 17.4

Splitting the vertices of a graph into two nonempty groups, S and V − S, is called a cut. An edge with one endpoint in S and the other in V − S crosses the cut.

Theorem 17.3 (Cut property)

Take any cut in a connected weighted graph. If (u, v) is the edge of least weight among the edges crossing the cut, then there is a minimum spanning tree that contains (u, v). If the weights are distinct, (u, v) is in every minimum spanning tree.

Let T be a minimum spanning tree that does not contain (u, v). Add (u, v) to T. By Theorem 17.2 exactly one cycle forms. The cycle leaves u (on the side of S), arrives at v (on the other side) and returns to u. To get back to S from the other side, it must cross the cut at least once more; this crossing is made by a tree edge, say (x, y). Since (u, v) is the lightest edge of the cut, w(u, v) ≤ w(x, y). Delete (x, y): the cycle is broken and we again obtain a spanning tree. The cost of the new tree is not greater than that of T. Since T is minimum, the costs are equal; the new tree is also minimum and contains (u, v). If the weights are distinct, w(u, v) < w(x, y) and the new tree would be cheaper than T. This is a contradiction; so T must already contain (u, v). ∎

Kruskal and Prim select the lightest edge of some cut at every step. In Prim's the cut is obvious: S is the vertices of the tree built so far, and the selected edge is the cheapest edge leaving the tree. In Kruskal's the endpoints of the selected edge stand in two separate clusters. If the cluster of one endpoint is taken as S, the edge is the cheapest of the edges crossing this cut. Had there been a cheaper crossing edge, Kruskal would have looked at it earlier and the two clusters would already have merged. So both algorithms select an edge of a minimum spanning tree at every step, and no choice ever has to be undone later.

The cut property has a twin: the cycle property. The heaviest edge on a cycle (if the weights are distinct) is in no minimum spanning tree. The reverse-delete method rests on this property.

Common mistake

Thinking “let every vertex choose the cheapest edge touching it, and that's it”. This rule is a special case of the cut property (the cut between a single vertex and the rest), and the selected edges really do belong to the MST. But it is not sufficient. In the seven-village example, (0,5) is chosen for 0 and 5, (1,6) for 1 and 6, (2,3) for 2 and 3, and (3,4) for 4. Three separate clusters result, and the tree is not completed. Sollin's algorithm finishes the job by repeating this rule on clusters in rounds.

17.3Kruskal's algorithm

17.3.1The algorithm

Joseph B. Kruskal published the algorithm in 1956. The idea is one sentence: try the edges in order from cheapest to most expensive; take one that does not form a cycle and discard one that does. The correctness of the algorithm has a proof and rests on the cut property. Reading the proof explains better why the algorithm is built this way. The pseudocode is as follows:

T = {};                    /* chosen edges */
while (|T| < n-1 && E ≠ Ø) {
    pick the cheapest edge (v,w) from E;
    E = E - {(v,w)};
    if ((v,w) does not form a cycle in T)
        T = T ∪ {(v,w)};
    else
        discard (v,w);
}
if (|T| < n-1)
    printf("no minimum spanning tree\n");

In the code, T is the set of chosen edges and E the set of edges not yet tried; |T| denotes the number of chosen edges.

  • Line 1. At the start no edge has been chosen. Every vertex is its own single-vertex cluster.
  • Line 2. The loop stops when one of its two conditions fails. If n − 1 edges have been chosen, the tree is complete; there is no need to look at more edges. It also stops if no edge is left to choose.
  • Lines 3–4. The cheapest of the remaining edges is taken and removed from the set. An edge is tried at most once.
  • Lines 5–8. If the edge does not form a cycle with the edges chosen so far, it is added to the tree; if it does, it is discarded. A discarded edge is never considered again. An edge that forms a cycle with the chosen ones will form a cycle again whatever is chosen afterward.
  • Lines 10–11. If fewer than n − 1 edges have been chosen when the loop ends, the edges have run out but the tree could not be completed. This shows that the graph is not connected, and there is no minimum spanning tree.

The intermediate states of Kruskal's algorithm are a forest, not a tree. The chosen edges can form several disjoint clusters (connected components). Clusters grow by merging, and in the end a single cluster remains. That an edge forms a cycle means that its two endpoints are already in the same cluster.

17.3.2Kruskal step by step

When the nine edges of the seven-village graph are sorted by cost, this sequence results: (0,5) 10, (2,3) 12, (1,6) 14, (1,2) 16, (3,6) 18, (3,4) 22, (4,6) 24, (4,5) 25, (0,1) 28. Table 17.2 shows the decision for each edge, and Figure 17.7 shows four selected moments.

Table 17.2: Kruskal on the seven-village graph. The “Clusters” column is the state after the decision; singleton clusters are not written.
StepEdgewClusters of the endpointsDecisionClustersTotal
1(0,5)10{0} and {5}add to tree{0,5}10
2(2,3)12{2} and {3}add to tree{0,5} {2,3}22
3(1,6)14{1} and {6}add to tree{0,5} {2,3} {1,6}36
4(1,2)16{1,6} and {2,3}add to tree{0,5} {1,2,3,6}52
5(3,6)18both in {1,2,3,6}cycle, discard{0,5} {1,2,3,6}52
6(3,4)22{1,2,3,6} and {4}add to tree{0,5} {1,2,3,4,6}74
7(4,6)24both in {1,2,3,4,6}cycle, discard{0,5} {1,2,3,4,6}74
8(4,5)25{1,2,3,4,6} and {0,5}add to tree{0,1,2,3,4,5,6}99
—(0,1)28never examined: 6 edges have been chosen
2810161412221825240156243281016141222182524015624328101614122218252401562432810161412221825240156243
Figure 17.7: Four moments of Kruskal's algorithm. Top left: after the third step there are three separate clusters: {0,5}, {2,3}, {1,6}. Top right: (3,6) is drawn as a red dashed line because it forms a cycle, and it is discarded. Bottom left: (3,4) has been added and the total has risen to 74. Bottom right: the tree is complete: six edges, total 99.

Four rows of the table need attention. In the fourth step (1,2) merges two separate clusters, {1,6} and {2,3}. Before this step the number of clusters (singletons included) was 4; afterward it drops to 3. In the fifth step both endpoints of (3,6) are in the same cluster. The path 3-2-1-6 from 3 to 6 already exists in the tree; (3,6) would close this path and form a cycle. In the seventh step the same holds for (4,6): the path 4-3-2-1-6 is ready. In the eighth step the sixth edge is chosen and the algorithm stops. The most expensive edge, (0,1), is never looked at.

The tree found is {(0,5), (2,3), (1,6), (1,2), (3,4), (4,5)} and its cost is 10 + 12 + 14 + 16 + 22 + 25 = 99. This is the cheapest of the 46 spanning trees.

17.3.3How not to code Kruskal

Two lines of the pseudocode remain vague: “pick the cheapest edge” and “if it does not form a cycle”. How these two jobs are done determines the speed of the code. In class, the instructor first deliberately goes down a wrong path and then shows the right one. Seeing the wrong path makes it easier to understand the right one.

Someone looking at the cluster counts in the table makes an observation: the clusters first rose to two, then to three, then fell back to two. “I've got it!”, they say, “I'll keep the clusters of the chosen edges in lists.” The unchosen edges are in an array as well. Searching the array for the cheapest edge every time, deleting it and shifting the rest is a bad idea. It is better to sort the edges once by cost and keep them as triples (end1, end2, cost).

With this plan the trace goes as follows. (0,5) arrives: it is searched for in the lists; neither 0 nor 5 is there, and a new list is opened. New lists are opened for (2,3) and (1,6) as well. When (1,2) arrives, 1 is found in one list and 2 in another. Since they are in different lists, there is no cycle; the edge is taken and the two lists are merged. When (3,6) arrives, both are in the same list: a cycle!

This code works correctly. But for each edge both endpoints are searched for in all the lists, and this search takes O(n). The total cost is O(e · n). The instructor is frank at this point: the cycle was caught and the result is correct, but this is not how it is coded, and code written this way earns no points on the exam. The algorithm itself is not wrong; the data structure behind it is. The instructor also says Kruskal's coding could be given as homework, and that they wonder whether students can discover the necessary data structures on their own.

Common mistake

Checking for a cycle with the question “have both endpoints been chosen before?” In the fourth step of the seven-village example both endpoints of (1,2) are on previously chosen edges: 1 on (1,6) and 2 on (2,3). By this rule the edge is rejected. Yet the endpoints are in different clusters and (1,2) is an edge of the MST. The right question is “are the two endpoints in the same cluster?”

17.3.4Two questions, two data structures

At each step of Kruskal's algorithm two questions are asked, and each has a data structure that answers it.

1) Which edge has the least cost? This question points to a structure that asks again and again for the smallest item: a priority queue implemented as a min-heap. In a min-heap every node is less than or equal to its children; the smallest item is at the root. Taking the root (deleteMin) takes O(log e). A heap can be built in two ways. If the edges are inserted one by one, O(e log e) is needed. If the edge array is ready, bottom-up heap construction needs only O(e). In this method, every node from the last internal node up to the root is sifted down and the array turns into a heap. The third way is to sort the edges once; in C the standard library function qsort is used for this.

2) Does this edge form a cycle? If the two endpoints of the edge are in different clusters, it does not form a cycle. The clusters are disjoint sets: every vertex is in exactly one set. Two operations are needed on disjoint sets. Find tells which set a vertex is in by returning the root of the set. Union gathers two sets into one. This pair is called union-find for short. The cycle question thus comes down to a comparison: do find(3) and find(2) give the same root?

The instructor shares the surprise at this point: heaps and sets have long since been taught in the background, but the student, without noticing that they would be useful in Kruskal's algorithm, goes and tries to keep lists. The sets taught in primary school speed up a graph algorithm here.

The slides give the cost with a detailed formula. If the heap is built by inserting the edges one by one, about |E| · lg |E| work is needed. Then the smallest edge is taken |V| times; each removal takes lg |E| and each set check almost constant time. The total is |E| · lg |E| + |V| · (lg |E| + Θ(1)). If the heap is built bottom-up, the first term drops to 2|E|. The “almost constant” time here is the cost of union-find, bounded by the inverse Ackermann function α. The formula is optimistic at one point: edges that form cycles are also taken from the heap. In the worst case the smallest can be taken e times, not n − 1. The safe upper bound is O(e log e).

17.3.5Union-find and the comparison function

The C implementation of Kruskal rests on three small parts: an edge structure, the union-find operations and a comparison function for qsort.

typedef struct { int u, v, w; } edge;

int find(int parent[], int i)   /* root: parent < 0 */
{
    while (parent[i] >= 0) i = parent[i];
    return i;
}
void unite(int parent[], int a, int b)   /* a, b are roots */
{
    if (parent[a] <= parent[b]) {   /* a is the bigger set */
        parent[a] += parent[b];  parent[b] = a;
    } else {
        parent[b] += parent[a];  parent[a] = b;
    }
}
int cmp(const void *x, const void *y)
{
    return ((const edge *)x)->w - ((const edge *)y)->w;
}
  • Line 1. Each edge is three integers: the endpoints u, v and the weight w. Thanks to typedef, the type name can be used as edge without writing struct. On x86-64 sizeof(edge) is 12 bytes; there is no padding, since all three fields are 4-byte ints.
  • Lines 3–7. find finds the root of the set of a vertex. The sets are kept as trees in an array: parent[i] is the parent of i in the tree. The root has no parent; at a root, parent is a negative number. The loop climbs through parents until it reaches a negative value. The returned root is the name of the set.
  • Lines 8–15. unite takes two roots and merges their sets. The parameters must be roots; if it is called with a non-root vertex, the tree is corrupted. The absolute value of the negative number stored at the root is the set size: parent[a] = −4 says that the set of a has 4 elements. The condition parent[a] <= parent[b] means that the set of a is larger than or equal to the other (−4 < −2). The larger set stays as the root: the sizes are added (parent[a] += parent[b]) and the root of the smaller set is attached under the larger one (parent[b] = a). The else branch does the same job in the opposite direction.
  • Lines 16–19. cmp has the signature that qsort wants: it takes two const void *, and returns a negative number if the first is smaller, a positive one if larger, and zero if equal. The void * pointers are converted to const edge * and the weights are subtracted.

The in-memory view of the sets is a single integer array. At the start each vertex is the root of its own set and has size 1; the array is {−1, −1, −1, −1, −1, −1, −1}. In the seven-village example, after the first four edges are added, the array becomes {−2, −4, 1, 2, −1, 0, 1}. This array defines three trees. 0 is a root (size 2) and is the parent of 5. 1 is a root (size 4); 2 and 6 are attached directly to 1, and 3 to 2. 4 is alone. The call find(parent, 3) follows the path 3 → 2 → 1 and returns 1.

Theorem 17.4 (Weighting rule)

If in a union the smaller set is always attached under the larger (the weighting rule), the height of the tree of a set with m elements is at most ⌊lg m⌋ + 1. So find takes O(log n).

The depth of a vertex grows by one only when its own set is attached under a set that is larger or equal. At that moment the size of the set containing the vertex at least doubles. The size starts at 1 and cannot exceed m; doubling can happen at most ⌊lg m⌋ times. If the depth of the root is counted as 1, the height is at most ⌊lg m⌋ + 1. ∎

Without the rule, in the worst case the trees would turn into chains. If, in the form unite(0, 1), unite(0, 2), …, the large set were attached under the small one each time, find would take O(n) steps.

One more improvement is possible: path compression. In the book of Horowitz, Sahni and Anderson-Freed the same idea goes by the name collapsing rule. After finding the root, find attaches every vertex on the path it climbed directly to the root. Later searches pass the same path in one step:

int find(int parent[], int i)       /* with path compression */
{
    int root = i, next;
    while (parent[root] >= 0) root = parent[root];     /* pass 1: find the root */
    while (i != root) {                        /* pass 2: hook the path vertices to the root */
        next = parent[i];
        parent[i] = root;
        i = next;
    }
    return root;
}

The first loop finds the root and the second loop walks the path once more. The old parent of each vertex is saved in next, and then the vertex is attached to the root. Without the saving, the rest of the path would be lost. When the weighting rule and path compression are used together, the amortized cost per operation over a sequence of operations is O(α(n)). α is the inverse Ackermann function and does not exceed 4 even for n as large as the number of atoms in the universe; in practice it is constant. On a random graph with 2000 vertices (8000 edges), the number of links climbed by Kruskal's find calls was measured as 21,464 without path compression and 12,348 with it.

Common mistake

Writing unite(parent, k[i].u, k[i].v), that is, uniting the endpoints of the edge directly. unite expects two roots. If an endpoint is not a root, its parent value points to a parent; the function takes this value for a set size and the array is corrupted. The roots are first found with find, and the union is done between the roots.

The subtraction in the cmp function also hides a trap. The difference of two large weights can exceed the int limit; for example 2,000,000,000 − (−2,000,000,000) overflows and the sign comes out wrong. Here the weights are small nonnegative integers and no overflow occurs. In a general-purpose comparison the form (a > b) − (a < b) is safe.

17.3.6The main loop of kruskal() and its trace

With the parts ready, the main loop fits in eleven lines. In the code, k is the edge array of e items; T is the array of n − 1 items in which the chosen edges will be written; parent is the set array of n items. i and t are integers.

for (i = 0; i < n; i++) parent[i] = -1;
qsort(k, e, sizeof(edge), cmp);
for (i = 0, t = 0; i < e && t < n - 1; i++) {
    int a = find(parent, k[i].u);
    int b = find(parent, k[i].v);
    if (a != b) {                 /* no cycle */
        T[t++] = k[i];
        unite(parent, a, b);
    }                             /* otherwise discard */
}
if (t < n - 1) printf("no tree\n");
  • Line 1. Every vertex is made the root of its own set; since its size is 1, its parent value is −1. The cost is O(n).
  • Line 2. The edges are arranged in increasing order of cost. qsort is given the start of the array, the number of items, the size in bytes of one item and the comparison function. qsort does not know the type of the items; with sizeof(edge) it learns how many bytes each item has and moves items byte by byte. The cost is O(e log e).
  • Line 3. Starting from the beginning of the array, edges are tried. Two counters are initialized together: i is the index of the edge being tried and t is the number of chosen edges. The loop stops when the edges run out or when n − 1 edges have been chosen. If the second condition is forgotten, the algorithm still gives the right result, but all the remaining edges are tried in vain after the tree is complete.
  • Lines 4–5. The roots of the two endpoints of the edge are found. a and b are declared in the loop body; since C99 it is allowed to declare variables inside a block.
  • Lines 6–9. If the roots differ, the endpoints are in separate sets and the edge does not form a cycle. The edge is copied into T (structure assignment copies all three fields at once), t grows by one and the two sets are united. If the roots are the same, nothing is done; the edge is discarded.
  • Line 11. If the loop ended while t < n − 1, the edges have run out; the graph is not connected.

The code was compiled in the form given in the slides and run with a test driver. Table 17.3 is the program's own output: the roots found for each edge and the parent array after the union.

Table 17.3: Trace of the main loop of kruskal() on the seven-village graph. a, b: the roots found in lines 4–5. The last column is parent[0..6] after the decision.
ik[i]abDecisiontparent[]
————start0−1 −1 −1 −1 −1 −1 −1
0(0,5,10)05add1−2 −1 −1 −1 −1 0 −1
1(2,3,12)23add2−2 −1 −2 2 −1 0 −1
2(1,6,14)16add3−2 −2 −2 2 −1 0 1
3(1,2,16)12add4−2 −4 1 2 −1 0 1
4(3,6,18)11discard4unchanged
5(3,4,22)14add5−2 −5 1 2 1 0 1
6(4,6,24)11discard5unchanged
7(4,5,25)10add61 −7 1 2 1 0 1
8—condition t < n − 1 false: the loop ends; cost 99
2810161412221825240156243parent[]0-11-12-13-14-15-16-1k[]sorted0-51002-31211-61421-21633-61843-42254-62464-52570-1288
2810161412221825240156243parent[]0-21-421324-15061k[]sorted0-51002-31211-61421-21633-61843-42254-62464-52570-1288▲ i
2810161412221825240156243parent[]011-72132415061k[]sorted0-51002-31211-61421-21633-61843-42254-62464-52570-1288
Figure 17.8: Three frames from the trace of kruskal(). Top: the start, every parent is −1 and the edges are sorted. Middle: i = 4: both endpoints of (3,6) have root 1, the edge forms a cycle and is discarded. Bottom: the final state: the root 1 holds the single set of seven vertices (parent[1] = −7); the faint boxes are the discarded edges.

A few details of the trace show how the weighting rule works. At i = 0 both sets have 1 element; parent[0] <= parent[5] is true by equality, so 0 stays the root. At i = 3, {1,6} and {2,3} are again of equal size; 1 stays the root, 2 goes under it, and the size becomes −4. From this point on, finding the root of 3 takes two steps: 3 → 2 → 1. At i = 7, the set of 1 has five elements and that of 0 has two; the small set (0) is attached under the large one (1) and parent[0] becomes 1. In the final array the deepest vertices are 3 and 5; both are two links from the root. For a set of seven elements, the bound given by Theorem 17.4 is ⌊lg 7⌋ + 1 = 3 levels; the tree is within this bound.

The same driver tried two more cases. On an exam graph with distinct weights the cost came out as 16. On a disconnected graph (two components, five vertices) only three edges were chosen and the program printed “no tree”. In all the experiments a wrapper that counts malloc and free calls counted 12 allocations and 12 frees; there is no leak.

17.3.7The complexity of Kruskal's algorithm

The cost of Kruskal's algorithm is obtained by adding up how many times each line of the code runs and how long each run takes. Table 17.4 gives this sum by groups of lines.

Table 17.4: The cost of Kruskal's algorithm with union-find.
StepCostExplanation
Sorting or building the heapO(e log e) or O(e)qsort or bottom-up heap construction
Taking the smallest edgeO(log e), at most e timesdeleting the root in a min-heap; O(1) in a sorted array
find (twice per edge)O(log n) with the weighting rule; ≈ O(α(n)) with path compressionat most 2e calls
uniteO(1)exactly n − 1 times
TotalO(e log e) = O(e log n)since e ≤ n², log e ≤ 2 log n

In the total, the dominant term is the sorting. The find calls cost at most 2e · O(log n), which is also O(e log n). The equality in the last row rests on a simple observation. In a simple graph e ≤ n(n − 1)/2 < n². Taking logarithms gives log e < 2 log n; the constant factor drops out in O notation and O(e log e) = O(e log n). In a connected graph e ≥ n − 1, so in the other direction log n = O(log e) also holds. The memory cost is O(n + e) for the edge array, T and parent.

In the best case none of the first n − 1 edges forms a cycle and the loop ends after n − 1 rounds. But the sorting still processes all the edges, and a comparison-based sort in general takes O(e log e); the early completion of the tree does not reduce this cost. If a heap is used, the table changes. The heap is built in O(e), and then only as many smallest edges as needed are taken. If the tree is completed early, the total is O(e + k log e), where k is the number of edges tried. This is why a heap is asked for in the homework. On a dense graph with random weights (2000 vertices, about two million edges) the tree was completed after only 9685 edges had been tried; qsort, however, sorted all two million edges.

The comparison with the “bad” coding that keeps lists sums up the main idea of the chapter. In the bad coding, for every edge the endpoints are searched for in all the lists: O(n) per edge, O(e · n) in total. For seven villages the difference is negligible. On a graph with 5000 vertices and six million edges, however, e · n exceeds thirty billion while e log e is about a hundred and forty million. The algorithm is the same; only the data structure behind it changes.

17.4Prim's algorithm

17.4.1The algorithm

The history of Prim's algorithm is interesting. The Czech mathematician Vojtěch Jarník published the algorithm in 1930. Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959 rediscovered the same algorithm independently of one another. That is why it also appears in sources as the DJP algorithm or the Prim–Jarník algorithm.

In Kruskal's algorithm the chosen edges could form disjoint clusters. Prim's algorithm, on the other hand, grows a single tree. It starts with a start vertex and at each step adds the cheapest edge that connects a vertex in the tree to a vertex outside the tree. The pseudocode is as follows:

T  = {};
TV = {0};           /* tree vertices: start from 0 */
while (|T| < n-1) {
    pick the cheapest edge (u,v) with u ∈ TV and v ∉ TV;
    if (no such edge) break;
    TV = TV ∪ {v};
    T  = T  ∪ {(u,v)};
}
if (|T| < n-1)
    printf("no minimum spanning tree\n");
  • Lines 1–2. T is the set of chosen edges and TV the set of vertices that have joined the tree. The start vertex is 0; any vertex can be chosen.
  • Lines 3–4. In each round the cheapest edge with one endpoint in TV and the other outside TV is sought. Only these are the edges that can be chosen.
  • Line 5. If there is no such edge, the tree cannot reach the remaining vertices; the graph is not connected.
  • Lines 6–7. The outer endpoint of the edge is added to TV and the edge itself to T.
  • Lines 9–10. If the loop ended early, there is no minimum spanning tree.

No cycle check is needed in Prim's algorithm. One endpoint of the chosen edge is in the tree and the other is outside; the condition v ∉ TV already guarantees that the edge goes to a new vertex. An edge that goes to a new vertex cannot form a cycle. The chosen edge is the cheapest edge crossing the cut S = TV; the cut property says that every choice is correct.

17.4.2Prim step by step

Let Prim be started from 0 on the seven-village graph. Table 17.5 gives TV, the edges that can be chosen and the choice in each round.

Table 17.5: Prim from 0 on the seven-village graph. The “Candidates” column holds the edges with one endpoint in TV and the other outside.
RoundTV (at start of round)Candidate edgesChosenTotal
1{0}(0,1) 28, (0,5) 10(0,5)10
2{0, 5}(0,1) 28, (5,4) 25(5,4)35
3{0, 5, 4}(0,1) 28, (4,3) 22, (4,6) 24(4,3)57
4{0, 5, 4, 3}(0,1) 28, (3,2) 12, (3,6) 18, (4,6) 24(3,2)69
5{0, 5, 4, 3, 2}(0,1) 28, (2,1) 16, (3,6) 18, (4,6) 24(2,1)85
6{0, 5, 4, 3, 2, 1}(1,6) 14, (3,6) 18, (4,6) 24(1,6)99
2810161412221825240156243281016141222182524015624328101614122218252401562432810161412221825240156243
Figure 17.9: Four moments of Prim's algorithm. Filled vertices are in TV, thick yellow edges are the candidate edges of that round, and thick red edges are in the tree. Top left: round 1. Top right: round 3. Bottom left: round 5. Bottom right: the tree is complete, total 99.

The “candidates” column of the table changes in every round. When a vertex enters the tree, the edges touching it join the candidates. When both endpoints of an edge are in the tree, that edge drops out of the candidates. For example, (0,1) is a candidate for five rounds but a cheaper candidate is always found. At the start of the sixth round 1 is also in the tree; both endpoints of (0,1) are in TV and it is no longer a candidate. The slides draw attention to this point separately: (0,1) still looks “choosable” in the drawing, but if it were chosen it would form a cycle.

The tree Prim found is {(0,5), (5,4), (4,3), (3,2), (2,1), (1,6)} and is the same as Kruskal's; only the order in which the edges were chosen differs. This is not a coincidence. In the seven-village graph all weights are distinct and the minimum spanning tree is unique. Changing the start vertex does not change the result: Prim started from 3 chooses the edges in the order (3,2), (2,1), (1,6), (3,4), (4,5), (5,0) and again arrives at 99.

17.4.3The real difficulty of coding Prim

The fourth line of the pseudocode is a single sentence but is not easy to code: “pick the cheapest edge with one endpoint in the tree and the other outside”. This line runs in every round and carries the following requirements:

  • The candidate edge with the least cost must be obtainable in one move.
  • When an edge is chosen, new edges are added to the candidates and edges with both endpoints in the tree are removed. The candidate set changes in every round.
  • When 0 is chosen, a structure is needed that sees only (0,1) and (0,5); it should not even look at the rest of the edges of the graph.

A naive coding scans all the edges in every round and looks for the cheapest among those with an endpoint in the tree. This costs O(e) per round, O(n · e) in total. It is the Prim counterpart of the list mistake in Kruskal's algorithm.

The instructor stresses the importance of the topic with two observations. First: a student who can find an efficient solution for this line has reached a certain level in data structures. Someone who says “Prim has already written it, I'll just code it” and translates the pseudocode directly into code sees the complexity suddenly grow. Second: if this problem were given to a graph theorist who had never heard the word “algorithm”, they too would do what Prim did: choose the cheapest edge. What sets the computer engineer apart is discovering which data structure must stand behind this choice.

The solution rests on this observation: it is not necessary to keep all the candidate edges. For each vertex v outside the tree a single number is enough: the cost of the cheapest edge connecting v to the tree. This number is kept in the array lowcost[v], and the tree end of that edge in the array closest[v]. The cheapest candidate edge is the edge of the vertex outside the tree with the smallest lowcost value. When a vertex u enters the tree, only the lowcost values of the neighbors of u can change. This idea gives two implementations: O(n²) with arrays and O(e log n) with a min-heap.

17.4.4The O(n²) implementation with arrays

The graph is kept as a cost matrix: w[u][v] is the weight of the edge (u, v). If there is no edge, w[u][v] is a large constant INF; the diagonal is 0. in_tree[v] says whether v is in the tree (v ∈ TV). The C code of Prim in the slides is as follows:

in_tree[0] = 1;                    /* TV = {0} */
for (v = 0; v < n; v++)
    lowcost[v] = w[0][v], closest[v] = 0;
for (k = 1; k < n; k++) {
    u = cheapest(lowcost, in_tree, n);  /* O(n) */
    if (u < 0) break;                /* no tree */
    in_tree[u] = 1;  total += lowcost[u];
    for (v = 0; v < n; v++)
        if (!in_tree[v] && w[u][v] < lowcost[v])
            lowcost[v] = w[u][v], closest[v] = u;
}
  • Line 1. 0 is taken into the tree. The other in_tree items and total must have been set to 0 beforehand; the code fragment assumes this.
  • Lines 2–3. At the start only 0 is in the tree. So the cheapest connection of each v to the tree is directly the edge (0, v): lowcost[v] = w[0][v], closest[v] = 0. For vertices with no edge, lowcost stays INF. The comma operator performs two assignments in a single statement.
  • Line 4. n − 1 more vertices will be added to the tree; the loop runs n − 1 rounds.
  • Lines 5–6. cheapest returns, among the vertices outside the tree, the one with the smallest lowcost value. If all lowcost values are INF, no vertex is left that can be connected to the tree; the function returns −1 and the loop is broken.
  • Line 7. u is taken into the tree; its edge is (closest[u], u) and its cost is added to the total.
  • Lines 8–10. The vertex u that has just entered the tree may offer a cheaper connection to the vertices outside. For each v outside the tree, if w[u][v] is smaller than the recorded lowcost[v], the record is updated: now the cheapest connection of v is through u.

The function cheapest is not given in the slides. Its implementation is a simple linear search:

int cheapest(const int lowcost[], const int in_tree[], int n)
{
    int v, u = -1;
    for (v = 0; v < n; v++)
        if (!in_tree[v] && lowcost[v] < INF &&
            (u < 0 || lowcost[v] < lowcost[u]))
            u = v;
    return u;            /* -1: no vertex left connected to TV */
}

The search looks only at vertices outside the tree that can be connected to it (whose lowcost value is not INF). The condition u < 0 makes the first suitable vertex the candidate; every later vertex with a smaller lowcost value takes the candidate's place.

Table 17.6: Trace of prim() (seven villages, from 0). The “Updated” column holds the records changed by lines 8–10. The arrays in the last row are the state when the loop ends.
kuEdge entering the treetotalUpdated (lowcost, closest)
——start0lowcost = 0 28 ∞ ∞ ∞ 10 ∞; closest all 0
15(0,5) 1010lowcost[4] = 25 (5)
24(5,4) 2535lowcost[3] = 22 (4), lowcost[6] = 24 (4)
33(4,3) 2257lowcost[2] = 12 (3), lowcost[6] = 18 (3)
42(3,2) 1269lowcost[1] = 16 (2)
51(2,1) 1685lowcost[6] = 14 (1)
66(1,6) 1499none
7—loop ends; lowcost = 0 16 12 22 25 10 14, closest = 0 2 3 4 5 0 1
2810161412221825240156243in_tree01102030405060lowcost028∞∞∞10∞closest0000000
2810161412221825240156243in_tree01102031415160lowcost0281222251018closest0034503
2810161412221825240156243in_tree01112131415161lowcost0161222251014closest0234501
Figure 17.10: Three frames from the trace of prim(). Top: the start: only 1 (28) and 5 (10) are connected to 0. Middle: after 3 has entered the tree: lowcost[2] = 12 and lowcost[6] = 18 have been updated. Bottom: the final state: the closest array holds the edges of the tree and the lowcost array their costs.

The two arrays in the final state are the tree itself. For every v ≠ 0, (closest[v], v) is a tree edge and lowcost[v] is its cost: (2,1) 16, (3,2) 12, (4,3) 22, (5,4) 25, (0,5) 10, (1,6) 14. The sum of lowcost except for its first item is 99. The record of 6 changed three times: first 24 (through 4), then 18 (through 3), and last 14 (through 1). Each update is a vertex that has just entered the tree opening a cheaper route to 6.

Cost. The outer loop runs n − 1 rounds. In each round cheapest looks at n vertices and the update loop scans n columns. That is O(n) per round, O(n²) in total. This time is independent of the number of edges; the best and worst cases are the same: Θ(n²). Memory is O(n²) for the matrix and O(n) for the arrays. In a dense graph, that is when e ≈ n², looking at all the edges at least once already requires Ω(n²). So this version is ideal for dense graphs.

The code was compiled in the form given in the slides and run; the values in Table 17.6 are the program's output. On a disconnected graph cheapest returned −1 in the third round, the loop was broken and only two edges were chosen.

Common mistake

Using INT_MAX for infinity and getting overflow in sums. The comparison w[u][v] < lowcost[v] is safe with INT_MAX. But if a vertex that cannot be connected to the tree is chosen by mistake, total += lowcost[u] overflows. If the same code is adapted to problems such as shortest paths and d[u] + w[u][v] is computed, the sum overflows directly; signed integer overflow is undefined behavior in C. The safe way is to choose a constant that is larger than all possible sums but whose double still fits in an int; here INF = 1,000,000 was used. In addition, the condition lowcost[v] < INF in cheapest prevents a vertex that cannot be connected from being chosen.

Common mistake

Forgetting the condition !in_tree[v] in the update loop. The lowcost and closest values of a vertex in the tree record the edge by which it entered and must never change again. Without the condition, the first corruption comes immediately. In the round when u enters the tree, for v = u the value w[u][u] = 0 is smaller than the recorded value. So lowcost[u] becomes 0 and closest[u] becomes u. This version was tried on the seven-village graph. total still came out as 99 because it was added before the record was corrupted; but when the loop ended, the closest array was 0 1 2 3 4 5 6. Every vertex appeared linked to itself and none of the tree's edges was left. If the diagonal were INF instead of 0, this time the neighbors in the tree would corrupt each other's records. The general name of this mistake is not removing from the candidate set the edges that have both endpoints in the tree.

17.4.5Speeding up with a heap

The array version scans n vertices in every round. In a sparse graph, for example when e ≈ 4n, most of these scans are wasted: the lowcost value of most vertices outside the tree is still infinite. Two improvements are made together. The graph is kept with adjacency lists; that way, when a vertex enters the tree, only its real neighbors are looked at. The smallest lowcost value is also taken not by a linear search but from a min-heap. The code in the slides is as follows:

/* adjacency list + min-heap (key = lowcost) */
heap_push(H, 0, 0);
while (!heap_empty(H)) {
    u = heap_pop_min(H);          /* O(log n) */
    if (in_tree[u]) continue;    /* stale entry */
    in_tree[u] = 1;
    for (p = graph[u]; p; p = p->link)
        if (!in_tree[p->vertex] &&
            p->weight < lowcost[p->vertex]) {
            lowcost[p->vertex] = p->weight;
            closest[p->vertex] = u;
            heap_push(H, p->vertex, p->weight);
        }
}

In the adjacency list, each vertex has a list; graph[u] points to the first item of the list of u. Each item has three fields: the neighbor's number vertex, the weight of the edge weight and link, which points to the next item in the list. Each record of the heap is a (vertex, key) pair, and the key is the lowcost value at the time the record was added. Before the code runs, all lowcost values must be set to INF, lowcost[0] to 0 and all in_tree values to 0.

  • Line 2. The start vertex 0 is put into the heap with key 0.
  • Lines 3–4. While the heap is not empty, the record with the smallest key is taken. heap_pop_min returns the root, moves the last record to the root and sifts it down: O(log m), where m is the number of records in the heap.
  • Line 5. If the vertex taken is already in the tree, the record is stale and is skipped. A stale record arises like this: when the lowcost value of a vertex decreases, the old record is not deleted from the heap; a second record with the new key is added. The record with the smaller key comes out first and the vertex enters the tree. When the old record comes out later, the vertex is already marked.
  • Line 6. The vertex is taken into the tree. The edge by which it entered is (closest[u], u) and its cost is lowcost[u].
  • Lines 7–13. For each neighbor in the list of u, the update of the array version is performed. If the neighbor is outside the tree and the edge (u, neighbor) is cheaper than the recorded connection, lowcost and closest are updated and a heap record with the new key is added. The list walk is the familiar pattern for linked lists, for (p = graph[u]; p; p = p->link); the loop ends when p becomes NULL.

The slides do not give the inside of the heap operations. With a binary min-heap built on an array, they can be written as follows:

typedef struct { int vertex, key; } entry;
typedef struct {
    entry *a;          /* a[1..size]: root a[1] */
    int size, capacity;
} heap;

int heap_empty(const heap *H) { return H->size == 0; }

void heap_push(heap *H, int vertex, int key)
{
    int i = ++H->size;                     /* capacity >= 2e + 1 */
    while (i > 1 && H->a[i / 2].key > key) {
        H->a[i] = H->a[i / 2];              /* move the parent down */
        i /= 2;
    }
    H->a[i].vertex = vertex;  H->a[i].key = key;
}

int heap_pop_min(heap *H)
{
    int root = H->a[1].vertex;
    entry last = H->a[H->size--];
    int i = 1, c = 2;
    while (c <= H->size) {
        if (c < H->size && H->a[c + 1].key < H->a[c].key) c++;
        if (last.key <= H->a[c].key) break;
        H->a[i] = H->a[c];                  /* move the smaller child up */
        i = c;  c *= 2;
    }
    H->a[i] = last;
    return root;
}

The records are in the range a[1..size]; the parent of a[i] is a[i/2] and its children are a[2i] and a[2i+1]. heap_push puts the new record at the end of the array and moves it up as long as its key is smaller than its parent's; instead of swapping, it moves the parent down and shifts the hole up. heap_pop_min saves the root, takes the last record into a temporary variable and sifts it down from the root until it is no larger than the smaller child. The heap array is allocated with malloc for 2e + 2 records. Each adjacency item can cause at most one insertion; there are 2e items in the lists in total, and with the initial record 2e + 1 records must fit. a[0] is not used. The array is released with free when the job is done; the 2e items of the adjacency list must also be freed one by one.

Table 17.7: Trace of Prim with a heap on the seven-village graph. The heap column shows the records after lines 7–13 finish, in key order, in the form “vertex:key”.
TakenStateRecords addedHeap
—start0:00:0
0:0enters the tree5:10, 1:285:10, 1:28
5:10enters the tree4:254:25, 1:28
4:25enters the tree3:22, 6:243:22, 6:24, 1:28
3:22enters the tree2:12, 6:182:12, 6:18, 6:24, 1:28
2:12enters the tree1:161:16, 6:18, 6:24, 1:28
1:16enters the tree6:146:14, 6:18, 6:24, 1:28
6:14enters the tree—6:18, 6:24, 1:28
6:18stale, skipped—6:24, 1:28
6:24stale, skipped—1:28
1:28stale, skipped—empty

The order in which vertices enter the tree is the same as in the array version: 0, 5, 4, 3, 2, 1, 6. In total 10 records were added and 10 records were taken; three were stale. Three records were created for 6 (24, 18, 14), because the lowcost value of 6 decreased three times. The program gave these numbers and the total of 99 exactly. The counting malloc/free wrapper counted 19 allocations (18 list items and the heap array) and 19 frees.

Cost. Each adjacency item makes at most one insertion; at most 2e + 1 records enter the heap and as many come out. Since there are at most 2e + 1 records in the heap, each operation takes O(log e), which is O(log n). Walking the adjacency lists costs O(n + e) in total. The total is O((n + e) log n), which is O(e log n) in a connected graph. Memory is O(n + e).

Instead of leaving stale records, the key of the record in the heap can be decreased in place. This operation is called decrease-key. For this, the position of each vertex in the heap array must be kept in a separate array. The heap then holds at most n records, but the asymptotic bound does not change. A Fibonacci heap does decrease-key in amortized O(1) and brings the bound down to O(e + n log n). This bound is important theoretically; in practice the constants of the structure are large and a binary heap is often faster.

Table 17.8: Prim implementations and Kruskal.
ImplementationTimeWhere it fits
Prim, arrays (lowcost, closest)O(n²)dense graph (e ≈ n²)
Prim, binary heap + adjacency listO(e log n)sparse graph
Prim, Fibonacci heapO(e + n log n)theoretical
KruskalO(e log e)sparse graph, edge list ready

To see what the bounds in the table mean in practice, the three implementations were run on random weighted graphs. Table 17.9 gives the times. Times vary with the machine, the compiler and the random graph; what matters here are the ratios.

Table 17.9: Times measured on random connected graphs (seconds; single measurement, zig cc -O2, varies by machine). In all four rows the cost found by the three algorithms is the same.
neGraphKruskal (qsort)Prim, arraysPrim, heap
20008000sparse0,0010,0170,002
20001.999.000dense0,420,0190,040
500020.000sparse0,0040,1060,003
50006.248.750dense1,470,1140,109

On sparse graphs, Kruskal and Prim with a heap finish in a few milliseconds; Prim with arrays is 8 to 35 times slower than they are. When the size goes from 2000 to 5000, the time of Prim with arrays grew about six times; this is close to the expectation (5000/2000)² ≈ 6.3. On dense graphs the table turns around. Prim with arrays is unaffected by the number of edges and is among the fastest. Almost all of Kruskal's time goes to sorting millions of edges, although the tree is completed within the first ten thousand edges. On a dense graph Prim with a heap only catches up with the array version. A heap operation is far more expensive than looking at a cell in a matrix, and in a dense graph the number of edges is close to the number of cells.

17.5Other algorithms and comparisons

17.5.1Sollin (Borůvka) and reverse-delete

The Czech engineer Otakar Borůvka solved the minimum spanning tree problem in 1926 while designing the electric grid of Moravia. This is the first known algorithm for the problem; since Sollin proposed the same method again in the 1960s, it is known by both names. The algorithm works in rounds. At the start every vertex is a separate component. In each round every component picks the cheapest edge leaving it; all the chosen edges are added at the same time and the components merge.

281016141222182524015624328101614122218252401562432810161412221825240156243
Figure 17.11: Sollin (Borůvka) on the seven-village graph. Left: the start, seven components. Middle: round 1: (0,5), (1,6), (2,3), (3,4) are chosen, three components remain. Right: round 2: (4,5) and (1,2) are chosen, one component remains. Total 99.

In the first round, 0 and 5 share the same cheapest edge: (0,5) = 10. For 1 and 6 it is (1,6) = 14, for 2 and 3 it is (2,3) = 12. The edges of 4 are 22, 24 and 25; the cheapest is (3,4). If two components choose the same edge, the edge is added once. At the end of the round {0,5}, {1,6} and {2,3,4} remain. In the second round the edges leaving {0,5} are (0,1) 28 and (4,5) 25; the cheapest is (4,5). The cheapest for {1,6} is (1,2) 16. The cheapest for {2,3,4} is also (1,2). When the two chosen edges are added, a single component remains.

In every round each component merges with another component; the number of components at least halves. One can get from n components to one in at most lg n rounds. Each round looks at all the edges once: O(e). The total is O(e log n). Since the choices within a round are independent of one another, the work can be divided among many processors; the algorithm is suited to parallelization. If there are ties in the weights, a consistent selection rule among edges of the same weight (for example the endpoint with the smaller number) is needed; otherwise a cycle can form in a round.

Reverse-delete is the reverse of Kruskal's. It starts with all the edges and tries edges in decreasing order of cost. If deleting an edge does not disconnect the graph, the edge is deleted; if it does, the edge is kept. In the seven-village graph (0,1) 28 is deleted; (4,5) 25 is kept, because if it were deleted {0,5} would be cut off. (4,6) 24 and (3,6) 18 are deleted; each of the rest is a bridge and is kept. The remaining six edges are again the tree of cost 99. The method rests on the cycle property: every edge deleted is the heaviest edge of some cycle.

All four algorithms rest on the same cut and cycle properties. If the weights are distinct, the minimum spanning tree is unique, so all of them find the same tree.

17.5.2The minimum spanning tree and the shortest path tree

The minimum spanning tree resembles another structure that is often confused with it: the shortest path tree. When the shortest paths from a source vertex to every vertex are combined, a tree results. Both are spanning trees, but they minimize different things.

28101614122218252401562432810161412221825240156243MST (total 99)shortest path tree from 0 (total 105)
Figure 17.12: The minimum spanning tree of the seven-village graph (left, total 99) and the shortest path tree from 0 (right, total 105).
  • The minimum spanning tree minimizes the total edge cost. It has no root; it does not matter from which vertex one looks. Going from 0 to 1 in the tree follows the path 0-5-4-3-2-1 and costs 10 + 25 + 22 + 12 + 16 = 85. The direct edge (0,1), however, is 28.
  • The shortest path tree minimizes the distance of each vertex from the source one by one. Starting from 0, the distance to 1 is 28, to 2 it is 44, to 3 it is 56, to 4 it is 35, to 5 it is 10 and to 6 it is 42. The edges of the tree are (0,1), (0,5), (1,2), (1,6), (2,3), (5,4), and its total cost is 105; this is larger than 99.

Which tree is needed depends on the question. If the total cost of laying cable to the villages is asked, the minimum spanning tree is sought; if the quickest travel from the center to each village is asked, the shortest path tree is sought. Dijkstra's algorithm, which finds the shortest path tree, is very similar to Prim's: it also grows a single tree and in every round picks the vertex with the smallest key. The only difference is the definition of the key. In Prim's the key is the cost of the single edge connecting the vertex to the tree; in Dijkstra's it is the total length of the path from the source to that vertex.

17.5.3Kruskal or Prim?

Table 17.10: Comparison of Kruskal and Prim.
KruskalPrim
Growing structureforest (disjoint clusters merge)a single tree (TV)
Selection criterionthe cheapest among all edgesthe cheapest edge leaving TV
Cycle checkunion-find requirednot needed (v ∉ TV)
Data structuresorted array or min-heap + setslowcost[] array or min-heap
TimeO(e log e)O(n²) or O(e log n)
Where it is goodsparse graph, edge listdense graph, cost matrix
Disconnected graphgives a minimum spanning forestcovers only the component of the start vertex

The choice is determined by the density of the graph and the representation at hand. If the edges come as a list from a file and the graph is sparse, Kruskal is the most natural choice: the list is sorted as it is. If the graph is given as a cost matrix and is dense, Prim with arrays is both short and fast. On a sparse graph held with adjacency lists, Prim with a heap and Kruskal give close results. The difference in the last row is also important. Kruskal does not stop on a disconnected graph; it tries all the edges and finds the minimum spanning tree of each component, that is, a forest. Prim stops when it finishes the component of the start vertex; it has to be started again for the other components.

17.5.4An approach to problem solving

The story of Kruskal and Prim teaches a method as well. An engineer who meets a new problem first asks: How has this problem been solved before? Which data structures have been proposed in the literature? How does the world solve this, and how should I? The instructor also opposes the comfort of “we have mastered algorithms”. These algorithms are still being worked on today. Knowing which structure to use where while solving a problem is the real gain of a data structures course.

The slides express this attitude with a saying about mastery. The saying lists the stages of following the path: looking at the master, following the master, walking with the master, seeing like the master and finally becoming the master. That is, first the solution in the literature is learned and applied; the original solution comes after that. A student who codes Kruskal by keeping lists has skipped the first stage. A student who sees how sets and the heap fit this problem has moved on to the later stages.

17.6Exam-style question

The coding of Kruskal is given as homework; the following question is of the kind that can be asked in exams. For the graph with six vertices in Figure 17.13, three things are required:

  1. Find the minimum spanning tree with Kruskal and write an “add” or “cycle” decision for each edge.
  2. Start Prim from A and write the order of the chosen edges.
  3. Give the final state of the parent[] array of union-find working with weighted union.
436527189ABCDEF
Figure 17.13: The graph of the exam question. Edges: (A,B) 4, (B,C) 6, (A,D) 3, (B,D) 5, (B,E) 2, (C,E) 7, (C,F) 1, (D,E) 8, (E,F) 9.

Kruskal. The edges are sorted: (C,F) 1, (B,E) 2, (A,D) 3, (A,B) 4, (B,D) 5, (B,C) 6, (C,E) 7, (D,E) 8, (E,F) 9. The vertices A..F are numbered 0..5 and, for each edge, unite(parent, find(parent, u), find(parent, v)) is called. Table 17.11 gives the decisions and the parent array.

Table 17.11: Kruskal on the exam question and parent[A..F].
EdgewRootsDecisionparent[] (A B C D E F)
———start−1 −1 −1 −1 −1 −1
(C,F)1C, Fadd−1 −1 −2 −1 −1 2
(B,E)2B, Eadd−1 −2 −2 −1 1 2
(A,D)3A, Dadd−2 −2 −2 0 1 2
(A,B)4A, Badd−4 0 −2 0 1 2
(B,D)5A, Acycleunchanged
(B,C)6A, Cadd−6 0 0 0 1 2

When the fifth edge is chosen, n − 1 = 5 is reached and the algorithm stops; (C,E), (D,E), (E,F) are not looked at. The tree is {(C,F), (B,E), (A,D), (A,B), (B,C)}, with cost 1 + 2 + 3 + 4 + 6 = 16. (B,D) forms a cycle, because B and D are already connected through A. For sets of equal size the first parameter stays the root: in (A,B), A and B both have 2 elements, and A stays the root. In (B,C), the set of A has 4 and that of C has 2 elements; C goes under A. The final array is [−6, 0, 0, 0, 1, 2]: A is the root of the set of six elements; the parent of E is B and the parent of F is C.

Prim (from A). The edges of A are (A,B) 4 and (A,D) 3: (A,D) is chosen. TV = {A, D}; the candidates are (A,B) 4, (D,B) 5, (D,E) 8: (A,B) is chosen. TV = {A, B, D}; the candidates are (B,E) 2, (B,C) 6, (D,E) 8: (B,E) is chosen. TV = {A, B, D, E}; the candidates are (B,C) 6, (E,C) 7, (E,F) 9: (B,C) is chosen. In the last round (C,F) 1 is chosen. The order is (A,D) 3 → (A,B) 4 → (B,E) 2 → (B,C) 6 → (C,F) 1, with total 16. The tree is the same as Kruskal's; since the weights are distinct, it cannot be otherwise. The noteworthy point is that Prim leaves the cheapest edge (C,F) for last: until C enters the tree, this edge is not a candidate.

All values were verified with a test driver. The graph has 55 spanning trees, and this is the only one with cost 16.

17.7Homework: coding Kruskal with data structures

For next week the instructor asks everyone to code Kruskal's algorithm as described in class. The expected program uses a min-heap and union-find. Its input is a list of edges; its output is the edges of the tree and the total cost. The requirements of the homework are:

  • The edge structure is of the form edge {u, v, w}. The heap is built bottom-up from the edge array (O(e)).
  • find must use path compression and unite the weighting rule.
  • If the graph is not connected (|T| < n − 1), the program must print “no minimum spanning tree”.
  • On the seven-village example it must produce output showing that it finds 99 and that (3,6) and (4,6) are rejected.

A checklist to look at before submission is also given. One must stop when t = n − 1, not take from the heap e times. A NULL check must be made after every malloc call, and every block allocated must be released with free at the end of the program. If there are edges of equal weight, the minimum spanning tree may not be unique; the programs of different students may find different trees, but the total cost is the same in all.

The parts given in this chapter contain all the building blocks of the homework: the edge structure and unite, find with path compression, the sift-down logic (the heap_pop_min in Prim with a heap) and the main loop. The real work of the homework is to combine them around a heap that uses the edge weight as the key.

17.8Complexity summary

Table 17.12: Costs of the methods for spanning trees and minimum spanning trees.
MethodStructureTimeExplanation
Trying all subsets—C(e, n−1) × O(n)exponential; not practical
Kruskal, bad codinglists + searchO(e · n)correct but not coded this way
Kruskalsorting or min-heap + union-findO(e log e)forest grows, clusters merge
Primarrays (lowcost, closest)O(n²)dense graph
Primbinary heap + adjacency listO(e log n)sparse graph
Sollin (Borůvka)component labelsO(e log n)at most lg n rounds; parallel
DFS/BFS spanning treestack / queueO(n + e)unweighted; any spanning tree

The O(n) factor in the first row is the cycle check of each choice. Even in a small graph like the seven villages, 84 choices are tried; in a graph with 30 vertices and 60 edges, C(60, 29) exceeds 1017. DFS and BFS in the last row find any spanning tree because they do not look at the weights. If all the edges have equal weight, every spanning tree is minimum and is found in linear time.

17.9Common mistakes

  1. Checking for a cycle in Kruskal's algorithm by asking “have both endpoints been chosen before?”. The two endpoints can be in different clusters. In the seven-village example (1,2) gets caught by this wrong rule, although it is an edge of the MST. The correct check is find(u) != find(v).
  2. Not removing from the candidate set in Prim's algorithm the edges with both endpoints in TV. (0,1) is a candidate for five rounds, and in the sixth round both its endpoints are in the tree. If this edge is chosen, a cycle forms. In the array version this mistake is forgetting the condition !in_tree[v] in the update loop; in the heap version it is not skipping stale records.
  3. Confusing the minimum spanning tree with the shortest path tree. The MST minimizes the total cost, the shortest path tree minimizes the individual distances. In the seven-village example the distance from 0 to 1 is 85 in the MST and 28 in the shortest path tree; the totals are 99 and 105.
  4. Forgetting the |T| < n − 1 check on a disconnected graph. Kruskal stops silently when the edges run out and is left with a forest. In Prim's, if cheapest returning −1 is not checked, in_tree[-1] is written; this is a write outside the array.
  5. Uniting non-root vertices in union-find. unite expects two roots. find is called first, and then the roots found are united.
  6. Using INT_MAX for infinity and getting overflow in sums. Even if the comparison is safe, the addition overflows and leads to undefined behavior. A constant larger than the largest possible sum but not overflowing is chosen.

17.10Exercises

  1. In the seven-village example, if the cost of the edge (3,6) were 11 instead of 18, what would the minimum spanning tree and its cost be?

    Solution

    The sorted edges: (0,5) 10, (3,6) 11, (2,3) 12, (1,6) 14, (1,2) 16, (3,4) 22, (4,6) 24, (4,5) 25, (0,1) 28. Kruskal: add (0,5), add (3,6), add (2,3), add (1,6), (1,2) is a cycle (1 and 2 are connected through 6 and 3), add (3,4), (4,6) is a cycle, add (4,5). The tree is {(0,5), (3,6), (2,3), (1,6), (3,4), (4,5)}, cost 10 + 11 + 12 + 14 + 22 + 25 = 94. The edge (3,6), now cheaper, has entered the tree, and the most expensive edge on the same cycle, (1,2), has dropped out. In the code output the final parent array is [3, 3, 3, −7, 3, 0, 3].

  2. Under what condition can Kruskal and Prim give different trees on the same graph?

    Solution

    Only if there are edges of equal weight. If the weights are distinct, the minimum spanning tree is unique and every correct algorithm finds it. With ties the two algorithms can make different choices among equal edges. For example, in a triangle all of whose edges are 1, Kruskal takes the first two edges in the sorted order. Prim takes two edges at the start vertex, and these may be different. The total cost is still the same.

  3. On the eight-vertex example graph (Figure 17.1), write the edges of the DFS and BFS spanning trees starting from 7.

    Solution

    With sorted adjacency lists, DFS(7): (7,3), (3,1), (1,0), (0,2), (2,5), (2,6), (1,4). Since the neighbors of 5, 2 and 7, are marked, the search moves to 2 and from there to 6; finally it returns to 1 and takes 4. BFS(7): (7,3), (7,4), (7,5), (7,6), (3,1), (5,2), (1,0). Both trees have seven edges.

  4. How many spanning trees does K4 have? How many are paths and how many are stars?

    Solution

    16 (44−2). Stars are determined by the choice of the center: 4. Paths are orderings of the four vertices, and reading in reverse gives the same path: 4!/2 = 12. 12 + 4 = 16.

  5. If the edge weights are integers between 1 and 10, how does the sorting step of Kruskal drop to O(e)?

    Solution

    Instead of a comparison-based sort, counting sort or bucket sort is used. A bucket is opened for each weight, the edges are distributed into the buckets by weight, and the buckets are read in order. The cost is O(e + 10) = O(e). The total time of Kruskal then comes down to the union-find operations.

  6. Why is the O(n²) version of Prim bad on a sparse graph?

    Solution

    In every round it scans n vertices, regardless of the number of edges. On a graph with e ≈ n, the version with a heap takes O(e log n) = O(n log n); O(n²) is much larger than that. On a random graph with 5000 vertices and 20,000 edges, the measured times are 0.106 and 0.003 seconds.

17.11Summary

  • A spanning tree is the subgraph of a connected graph that connects all its vertices with n − 1 edges and no cycle. DFS and BFS each produce a spanning tree; they split the edges into tree edges and nontree edges.
  • Of the properties connectivity, acyclicity and n − 1 edges, any two imply the third. Adding an edge to a tree forms a single cycle, and deleting an edge from a tree splits it in two.
  • The number of spanning trees grows quickly: nn−2 in Kn. Trying them all is impractical; testing isomorphism is also a hard problem in its own right.
  • A minimum spanning tree is a spanning tree with the smallest total weight. The greedy choice gives the right result; the justification is the cut property. If the weights are distinct, the tree is unique.
  • Kruskal tries edges in increasing order of cost, catches cycles with union-find and stops when n − 1 edges have been chosen: O(e log e). The intermediate states are forests.
  • Union-find is a parent array; at a root it holds the negative of the set size. The weighting rule keeps the height at O(log n), and path compression brings the cost per operation down to a constant in practice.
  • Prim grows a single tree by the cheapest edge and needs no cycle check. It takes O(n²) with the lowcost/closest arrays and O(e log n) with adjacency lists and a heap.
  • Same idea, different structure: Kruskal, which takes O(e · n) with list search, drops to O(e log e) with sets.
  • Kruskal or Prim with a heap is chosen on a sparse graph, and Prim with arrays on a dense one. Sollin (Borůvka) works in rounds and is suited to parallelization.
  • The minimum spanning tree minimizes the total cost, the shortest path tree minimizes the distances from the source; the two are different trees.

17.12Key terms

  • spanning tree
  • minimum spanning tree
  • forest
  • isomorphic
  • complete graph
  • weighted graph
  • connected component
  • cycle
  • greedy method
  • Kruskal's algorithm
  • Prim's algorithm
  • Sollin's algorithm
  • disjoint sets
  • find
  • union
  • weighting rule
  • path compression
  • inverse Ackermann function
  • min-heap
  • priority queue
  • bottom-up heap construction
  • adjacency list
  • depth-first search
  • breadth-first search
  • shortest path
  • counting sort

17.13Test Yourself

  1. How many edges does every spanning tree of a connected graph with 10 vertices and 15 edges have? How many edges does DFS leave out of the tree on this graph?

    Answer

    A spanning tree has n − 1 = 9 edges. The remaining 15 − 9 = 6 edges are nontree edges; this number is independent of the type of traversal and of the start vertex.

  2. How many spanning trees does K5 have? How many of them are stars?

    Answer

    By Cayley's formula, 53 = 125. The center of the star can be chosen in five ways: 5 stars.

  3. On the seven-village graph, which edges does Kruskal discard because they form cycles? Which edge does it never look at?

    Answer

    (3,6) 18 and (4,6) 24 form cycles: both have endpoints in the same cluster at that moment. (0,1) 28 is never looked at, because when (4,5) 25 is chosen the six edges are complete.

  4. parent = [−3, 0, 0, −2, 3] is given. What does find(parent, 2) return? If unite(parent, 0, 3) is then called, what does the array become?

    Answer

    parent[2] = 0, parent[0] = −3 < 0: the root is 0. In the union, since parent[0] = −3 <= parent[3] = −2, 0 stays the root: parent[0] = −5, parent[3] = 0. The array becomes [−5, 0, 0, 0, 3]; the parent of 4 is still 3.

  5. If Prim is started from 3 on the seven-village graph, in what order are the edges chosen? Does the cost change?

    Answer

    (3,2) 12, (2,1) 16, (1,6) 14, (3,4) 22, (4,5) 25, (5,0) 10. The cost is again 99; since the weights are distinct the tree is unique, and only the order of selection changes.

  6. If the line if (in_tree[u]) continue; is deleted in Prim with a heap, what happens on the seven-village graph?

    Answer

    Stale records are processed too. When the records 6:18, 6:24 and 1:28 come out, 6 and 1 are “taken into the tree” again and their neighbors are scanned again. Since all the neighbors are marked, lowcost and closest are not corrupted. But if the number of vertices entering the tree or the total is counted in this line, vertices are counted more than once; line 5 guarantees that each vertex is processed exactly once.

  7. A road network with 1000 vertices and 3000 edges and a complete graph with 1000 vertices and about 500,000 edges are given. Which Prim implementation should be chosen for each?

    Answer

    The road network is sparse: Prim with a heap takes about e log n ≈ 3000 · 10 = 30,000 steps and Prim with arrays n² = 106; the heap is chosen. The complete graph is dense: the heap version does about 5 · 105 · 10 = 5 · 106 heap work, while the array version stays at 106; Prim with arrays is chosen.

  8. In a graph whose edge weights are all distinct, can the heaviest edge be in the minimum spanning tree?

    Answer

    It can, but only if that edge is not on any cycle, that is, if deleting it disconnects the graph. For example, if a vertex is connected by a single edge, that edge is in every spanning tree however expensive it is. If the edge is on a cycle, by the cycle property it cannot be in the tree.

17.14Further reading

  • E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Section 6.3. The Kruskal and Prim pseudocode and the seven-village example in this chapter follow its presentation; Sollin's algorithm is also described in the same section.
  • T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapters 19 and 21. The amortized analysis of disjoint-set forests, the proof of the inverse Ackermann bound and the general proof of the cut property under the name “safe edge” are there.
  • R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3rd ed., Chapter 20. C implementations of Prim, Kruskal and Borůvka are given together with experimental comparisons on large random graphs.

17.15References

  1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Silicon Press, 2008. Section 6.3, Minimum Cost Spanning Trees.
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. Chapter 19, Data Structures for Disjoint Sets; Chapter 21, Minimum Spanning Trees.
  3. R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3rd ed., Addison-Wesley, 2002. Chapter 20, Minimum Spanning Trees.

Related pages: Chapter 17 slides · © Sercan Külcü. All rights reserved.