We must all hang together, gentlemen,or else we shall most assuredly hang separately.
— Benjamin Franklin, at the signing of the
Declaration of Independence (July �, ���6)
I remember seeking advice from someone—who could it have been?—about
whether this work was worth submitting for publication; the reasoning it uses is sovery simple.. . . Fortunately he advised me to go ahead, and many years passed.
before another of my publications became as well-known as this very simple one.
— Joseph Kruskal, describing his shortest-spanning-subtree algorithm (����)Clean ALL the things!
— Allie Brosh, “This is Why I’ll Never be an Adult”,
Hyperbole and a Half, June ��, ����.

�
Minimum Spanning Trees
Suppose we are given a connected, undirected, weighted graph. This is agraph G = (V, E) together with a function w: E ! R that assigns a real weightw(e) to each edge e, which may be positive, negative, or zero. This chapter
describes several algorithms to find the minimum spanning tree of G, that is,
the spanning tree T that minimizes the functionX
w(T ) :=w(e).
e2T

See Figure . for an example.

�.�

Distinct Edge Weights

An annoying subtlety in the problem statement is that weighted graphs canhave more than one spanning tree with the same minimum weight; in particular,
if every edge in G has weight 1, then every spanning tree of G is a minimum����. M������ S������� T����

8

5
10
2

18

3

12

30

16

14
4

26

Figure �.�. A weighted graph and its minimum spanning tree.

spanning tree, with weight V 1. This ambiguity complicates the developmentof our algorithms; everything would be much simpler if we could simply assume
that minimum spanning trees are unique.
Fortunately, there is an easy condition that implies the uniqueness we want.
Lemma �.�. If all edge weights in a connected graph G are distinct, then G hasa unique minimum spanning tree.
Proof: Let G be an arbitrary connected graph with two minimum spanning
trees T and T 0 ; we need to prove that some pair of edges in G have the same
weight. The proof is essentially a greedy exchange argument.
Each of our spanning trees must contain an edge that the other tree omits.
Let e be a minimum-weight edge in T \ T 0 , and let e0 be a minimum-weightedge in T 0 \ T (breaking ties arbitrarily). Without loss of generality, supposew(e)  w(e0 ).
The subgraph T 0 [ {e} contains exactly one cycle C, which passes throughthe edge e. Let e00 be any edge of this cycle that is not in T . At least one suchedge must exist, because T is a tree. (We may or may not have e00 = e0 .) Because
e 2 T , we immediately have e00 6= e and therefore e00 2 T 0 \ T . It follows thatw(e00 ) w(e0 ) w(e).
Now consider the spanning tree T 00 = T 0 + e e00 . (This new tree T 00 might
be equal to T .) We immediately have w(T 00 ) = w(T 0 ) + w(e) w(e00 )  w(T 0 ).
But T 0 is a minimum spanning tree, so we must have w(T 00 ) = w(T 0 ); in otherwords, T 00 is also a minimum spanning tree. We conclude that w(e) = w(e00 ),which completes the proof.
É
If we already have an algorithm that assumes distinct edge weights, we canstill run it on graphs where some edges have equal weights, as long as we havea consistent method for breaking ties. One such method uses the following
The converse of this lemma is false; a connected graph with repeated edge weights can still
have a unique minimum spanning tree. As a trivial example, suppose G is a tree!

��8

�.�. The Only Minimum Spanning Tree Algorithm

algorithm in place of simple weight comparisons. S
Etakes as input
four integers i, j, k, l, representing four (not necessarily distinct) vertices, anddecides which of the two edges (i, j) and (k, l) has “smaller” weight. (Because
the input graph undirected, the pairs (i, j) and ( j, i) represent the same edge.)SE(i, j, k, l)if w(i, j) < w(k, l)if w(i, j) > w(k, l)
if min(i, j) < min(k, l)
if min(i, j) > min(k, l)
if max(i, j) < max(k, l)hhif max(i,j) > max(k,l) ii

then return (i, j)then return (k, l)then return (i, j)then return (k, l)then return (i, j)
return (k, l)

In light of Lemma . and this tie-breaking rule, we will safely assume forthe rest of this chapter that edge weights are always distinct, and therefore
minimum spanning trees are always unique. In particular, we can freely discuss
the minimum spanning tree with no confusion.

�.�

The Only Minimum Spanning Tree Algorithm

There are many algorithms to compute minimum spanning trees, but almost allof them are instances of the following generic strategy. The situation is similar
to graph traversal, where several different algorithms are all variants of thegeneric traversal algorithm whatever-first search.
The generic minimum spanning tree algorithm maintains an acyclic subgraph F of the input graph G, which we will call the intermediate spanning forest.
At all times, F satisfies the following invariant:
F is a subgraph of the minimum spanning tree of G.
Initially, F consists of V one-vertex trees. The generic algorithm connects trees
in F by adding certain edges between them. When the algorithm halts, F
consists of a single spanning tree; our invariant implies that this must be theminimum spanning tree of G. Obviously, we have to be careful about whichedges we add to the evolving forest, because not every edge is in the minimum
spanning tree.
At any stage of its evolution, the intermediate spanning forest F induces
two special types of edges in the rest of the graph.
• An edge is useless if it is not an edge of F , but both its endpoints are in thesame component of F .
• An edge is safe if it is the minimum-weight edge with exactly one endpoint
in some component of F .
����. M������ S������� T����

The same edge could be safe for two different components of F . Some edges of
G \ F are neither safe nor useless; we call these edges undecided.
All minimum spanning tree algorithms are based on two simple observations.
The first observation was proved by Robert Prim in(although it is implicit
in several earlier algorithms), and the second is immediate.
Lemma �.� (Prim). The minimum spanning tree of G contains every safe edge.
Proof: In fact we prove the following stronger statement: For any subset S ofthe vertices of G, the minimum spanning tree of G contains the minimum-weightedge with exactly one endpoint in S. Like the previous lemma, we prove thisclaim using a greedy exchange argument.
Let S be an arbitrary subset of vertices of G, and let e be the lightest edge
with exactly one endpoint in S. (Our assumption that all edge weights are
distinct implies that e is unique.) Let T be an arbitrary spanning tree that does
not contain e; we need to prove that T is not the minimum spanning tree of G.
Because T is connected, it contains a path from one endpoint of e to theother. Because this path starts at a vertex of S and ends at a vertex not in S, it
must contain at least one edge with exactly one endpoint in S; let e0 be any suchedge. Because T is acyclic, removing e0 from T yields a spanning forest withexactly two components, one containing each endpoint of e. Thus, adding e
to this forest gives us a new spanning tree T 0 = T e0 + e. The definition of e
implies w(e0 ) > w(e), which implies that T 0 has smaller total weight than T .
Thus, T is not the minimum spanning tree of G, which completes the proof. Éeeʹ

Figure �.�. Every safe edge is in the minimum spanning tree. Black vertices are in the subset S .

Lemma �.�. The minimum spanning tree contains no useless edge.
Proof: Adding any useless edge to F would introduce a cycle.

É

Our generic minimum spanning tree algorithm repeatedly adds safe edges
to the evolving forest F . If F is not yet connected, there must be at least one
safe edge, because the input graph G is connected. Thus, no matter which safe
edges we add in each iteration, our generic algorithm eventually connects F .
By induction, Lemma . implies that the resulting tree is in fact the minimum
�6��.�. Borůvka’s Algorithm

spanning tree. Whenever we add new edges to F , some undecided edges may
become safe, and other undecided edges may become useless. (Once an edge
becomes useless, it stays useless forever.) To fully specify a particular algorithm,
we must describe which safe edge(s) to add in each iteration, and how to findthose edges.

�.�Borůvka’s Algorithm

The oldest and arguably simplest minimum spanning tree algorithm was discovered by the Czech mathematician Otakar Bor vka in, about a year after
Jind ich Saxel asked him how to construct an electrical network connecting
several cities using the least amount of wire. The algorithm was rediscovered by
Gustav Choquet in, rediscovered again by a team of Polish mathematicians
led by Józef ukaszewicz in, and rediscovered again by George Sollin in. Although Sollin never published his rediscovery, it was carefully describedand credited in one of the first textbooks on graph algorithms; as a result, thisalgorithm is sometimes called “Sollin’s algorithm”.
The Bor vka / Choquet / Florek- ukaziewicz-Perkal-Steinhaus-Zubrzycki /Prim / Sollin / Brosh algorithm can be summarized in one line:: Add ALL the safe edges and recurse.

B

8

5
10
2

18

3

12

30

18

12
14

14
4

16

26

26

Figure �.�. Borůvka’s algorithm run on the example graph. Thick red edges are in F ; dashed edges areuseless. Arrows point along each component’s safe edge. The algorithm ends after just two iterations.

Here is Bor vka’s algorithm in more detail. The algorithm calls the C
A L
algorithm from Chapter (on page) to count the components
of F and label each vertex v with an integer comp(v) indicating its component.
Saxel was an employee of the West Moravian Power Company, described by Bor vka as“very talented and hard-working”, who was later executed by the Nazis as a person of Jewish
descent.
Go read everything in Hyperbole and a Half . And then go buy the book. And an extra copy
for your cat. What’s that? You don’t have a cat? What kind of a monster are you? Go get a cat,and then buy it an extra copy of Hyperbole and a Half.

�6��. M������ S������� T����B(V, E):F = (V, ?)count CA L
(F )while count > 1
A A S
E(E, F, count)
count CA L
(F )return F

It remains only to describe how to identify and add all the safe edges to F .
Suppose F has more than one component, since otherwise we’re already done.
The following subroutine computes an array safe[1 .. V ] of safe edges, wheresafe[i] is the minimum-weight edge with one endpoint in the ith componentof F , by a brute force examination of every edge in G. For each edge uv, if uand v are in the same component, then uv is either useless or already an edge
in F . Otherwise, we compare the weight of uv to the weights of safe[comp(u)]and safe[comp(v)] and update the array entries if necessary. Once we haveidentified all the safe edges, we add each edge safe[i] to F .
AA SE(E, F, count):
for i
1 to countsafe[i] Nfor each edge uv 2 E
if comp(u) 6= comp(v)if safe[comp(u)] = Nor w(uv) < w(safe[comp(u)])
safe[comp(u)] uv
if safe[comp(v)] = Nor w(uv) < w(safe[comp(v)])
safe[comp(v)] uv
for i
1 to count
add safe[i] to F

Each call to C
A L
runs in O(V ) time, because the forest F has
at most V 1 edges. AddAllSafeEdges runs in O(V + E) time, because we spend
constant time on each vertex, each edge of G, and each component of F . Because
the input graph is connected, we have V  E + 1. It follows that each iterationof the while loop of B
takes O(E) time.
Each iteration reduces the number of components of F by at least a factorof two—in the worst case, the components of F coalesce in pairs. Because F
initially has V components, the while loop iterates at most O(log V ) times. We
conclude that the overall running time of Bor vka’s algorithm is O(E log V).

This is the MST Algorithm You Want
Despite its relatively obscure origin, early Western algorithms researchers were
aware of Bor vka’s algorithm, but dismissed it as being “too complicated”.
�6��.�. Jarník’s (“Prim’s”) Algorithm

As a result, despite its simplicity and efficiency, most algorithms and data
structures textbooks unfortunately do not even mention Bor vka’s algorithm.
This omission is a serious mistake; Bor vka’s algorithm has several distinct
advantages over other classical MST algorithms.
• Bor vka’s algorithm often runs faster than its O(E log V ) worst-case running
time. The number of components in F can drop by significantly more than afactor of 2 in a single iteration, reducing the number of iterations below the
worst-case dlog2 V e.

• A slight reformulation of Bor vka’s algorithm (actually closer to Bor vka’s
original presentation) actually runs in O(E) time for a broad class ofinteresting graphs, including graphs that can be drawn in the plane withoutedge crossings. In contrast, the time analysis for the other two algorithms
applies to all graphs.
• Bor vka’s algorithm allows for significant parallelism; in each iteration,
each component of F can be handled in a separate independent thread.
This implicit parallelism allows for even faster performance on multicore or
distributed systems. In contrast, the other two classical MST algorithms are
intrinsically serial.
• Several more recent minimum-spanning-tree algorithms are faster even in
the worst case than the classical algorithms described here. All of thesefaster algorithms are generalizations of Bor vka’s algorithm.
In short, if you ever need to implement a minimum-spanning-tree algorithm,
use Bor vka. On the other hand, if you want to prove things about minimum
spanning trees effectively, you really need to know the next two algorithms as
well.

�.�

Jarník’s (“Prim’s”) Algorithm

The next oldest minimum spanning tree algorithm was first described by the
Czech mathematician Vojt ch Jarník in a
letter to Bor vka; Jarník published
his discovery the following year. The algorithm was independently rediscovered
by Joseph Kruskal in, (arguably) by Robert Prim in, by Harry Loberman
and Arnold Weinberger in, and finally by Edsger Dijkstra in. Prim,Lobermand and Weinberger, and Dijkstra all (eventually) knew of and evencited Kruskal’s paper, but since Kruskal also described two other minimumspanning-tree algorithms in the same paper, this algorithm is usually called“Prim’s algorithm”, or sometimes “the Prim/Dijkstra algorithm”, even though by
Dijkstra already had another algorithm (inappropriately) named after him.
In Jarník’s algorithm, the intermediate forest F has only one nontrivial
component T ; all the other components are isolated vertices. Initially, T consists
�6��. M������ S������� T����

of a single arbitrary vertex of the graph. The algorithm repeats the following
step until T spans the whole graph:: Repeatedly add T ’s safe edge to T .

J

8

5

8

5

10
2
18

3

12

2
30

14
4

8

5

10

16

18

3

12

2
30

16

18

5

8

10

10
3

3
16

30

30

16

14
26

26

26

26

8

30

26

16

5

30

16

26

Figure �.�. Jarník’s algorithm run on the example graph, starting with the bottom vertex. At each stage,
thick red edges are in T , an arrow points along T ’s safe edge; and dashed edges are useless.

To implement Jarník’s algorithm, we keep all the edges adjacent to T ina priority queue. When we pull the minimum-weight edge out of the priority
queue, we first check whether both of its endpoints are in T . If not, we add theedge to T and then add the new neighboring edges to the priority queue. In
other words, Jarník’s algorithm is a variant of “best-first search”, as described at
the end of Chapter ! If we implement the underlying priority queue using astandard binary heap, Jarník’s algorithm runs in O(E log E) = O(E log V) time.
™Improving Jarník’s Algorithm

We can improve Jarník’s algorithm using a more complex priority queue data
structure called a Fibonacci heap, first described by Michael Fredman andRobert Tarjan in. Just like binary heaps, Fibonacci heaps support thestandard priority queue operations I,E
M , and D
K .
However, unlike standard binary heaps, which require O(log n) time for every
operation, Fibonacci heaps support I
and DK
in constantamortized time. The amortized cost of E
M is still O(log n).
Amortized time is an accounting trick that allows us to ignore infrequent fluctuations in
the time for a single data structure operation. A Fibonacci heap can execute any intermixed
sequence of I I
s, D DK s, and X E
M s in O(I + D + X log n) time, in theworst case. So the average I
and the average D
K each take constant time, andthe average E
M takes O(log n) time; however, some individual operations may take

�6�

�.�. Kruskal’s Algorithm

To apply this faster data structure, we keep the vertices of G in the priority
queue instead of edges, where the priority of each vertex v is either the minimumweight edge between v and the evolving tree T , or 1 if there is no such edge.
We can I
all the vertices into the priority queue at the beginning of thealgorithm; then, whenever we add a new edge to T , we may need to decrease
the priorities of some neighboring vertices.
To make the description easier, we break the algorithm into two parts.
JI
initializes the priority queue; JL
is the main algorithm.
The input consists of the vertices and edges of the graph, along with the startvertex s. For each vertex v, we maintain both its priority priority(v) and theincident edge edge(v) such that w(edge(v)) = priority(v).
J

J

J
J

I
(V, E, s):for each vertex v 2 V \ {s}if vs 2 Eedge(v)vspriority(v)
w(vs)
else
edge(v) N
priority(v) 1I(v)(V, E, s):I(V, E, s)
L(V, E, s)J

L(V, E, s):T({s}, ?)
for i
1 to |V | 1v
EM
add v and edge(v) to T
for each neighbor u of v
if u 2/ T and priority(u) > w(uv)edge(u) uv
D
K (u, w(uv))

Figure �.�. Jarník’s minimum spanning tree algorithm, ready to be used with a Fibonacci heap

The operations I
and E
M are each called O(V ) times once
for each vertex except s, and D
K is called O(E) times, at most twice
for each edge. Thus, if we use a Fibonacci heap, the improved algorithm runs inO(E + V log V) time, which is faster than Bor vka’s algorithm unless E = O(V ).
In practice, however, this improvement is rarely faster than the naive
implementation using a binary heap, unless the graph is extremely large anddense. The Fibonacci heap algorithms are quite complex, and the hidden
constants in both the running time and space are significant—not outrageous,
but certainly bigger than the hidden constant 1 in the O(log n) time bound forbinary heap operations.

�.�

Kruskal’s Algorithm

The last minimum spanning tree algorithm we’ll consider was first described by
Joseph Kruskal in, in the same paper where he rediscovered Jarnik’s algolonger in the worst case. Amortization uses statistical averaging over the sequence of operations;
there is no assumption of randomness here, either in the input data or in the algorithm.

�6��. M������ S������� T����

rithm. Kruskal was motivated by “a typewritten translation (of obscure origin)”of Bor vka’s original paper that had been “floating around” the Princeton mathdepartment. Kruskal found Bor vka’s algorithm “unnecessarily elaborate”.
The same algorithm was rediscovered in
by Harry Loberman and Arnold
Weinberger, but somehow avoided being renamed after them.
Like our earlier minimum-spanning tree algorithms, Kruskal’s algorithm hasa memorable one-line description:: Scan all edges by increasing weight; if an edge is safe, add it to F .

K

5
2

8

3
4

5
10
2

18

3

12

30

8

10

16

12

14

14
4

26
16

18

30
26

Figure �.6. Kruskal’s algorithm run on the example graph. Thick red edges are in F ; thin dashed edges
are useless.

The simplest method to scan the edges in increasing weight order is to sortthe edges by weight, in O(E log E) time, and then use a simple for-loop over thesorted edge list. As we will see shortly, this preliminary sorting dominates therunning time of the algorithm.
Because we examine the edges in order from lightest to heaviest, any edge
we examine is safe if and only if its endpoints are in different components of theforest F . Suppose we encounter an edge e that joins two components A and B
but is not safe. Then there must be a lighter edge e0 with exactly one endpoint
in A. But this is impossible, because (inductively) every previously examinededge has both endpoints in the same component of F .
Just as in Bor vka’s algorithm, each vertex of F needs to "know" which
component of F contains it. Unlike Bor vka’s algorithm, however, we do
To be fair, Bor vka’s first paper was unnecessarily elaborate, in part because it was written
for mathematicians in the formal language of (linear) algebra, rather than in the language ofgraphs. Bor vka’s followup paper, also published in
but in an electrotechnical journal, waswritten in plain language for a much broader audience, essentially in its current modern form.
Kruskal was apparently unaware of Bor vka’s second paper. Stupid Iron Curtain.

�66

�.�. Kruskal’s Algorithm

not recompute all component labels from scratch every time we add an edge.
Instead, when two components are joined by an edge, the smaller component
inherits the label of the larger component; that is, we traverse the smaller
component (via whatever-first search). This traversal requires O(1) time foreach vertex in the smaller component. Each time the component label of avertex changes, the component of F containing that vertex grows by at least afactor of 2; thus, each vertex label changes at most O(log V ) times. It follows
that the total time spent updating vertex labels is only O(V log V ).
More generally, Kruskal’s algorithm maintains a partition of the vertices of G
into disjoint subsets (in our case, the components of F ), using a data structurethat supports the following operations:(v) — Create a set containing only the vertex v.

• M

S

• F

(v) — Return an identifier unique to the set containing v.

• U(u, v) — Replace the sets containing u and v with their union. (Thisoperation decreases the number of sets.)
Here’s a complete description of Kruskal’s algorithm in terms of these operations:K(V, E):
sort E by increasing weightF(V, ?)
for each vertex v 2 V
M
S (v)
for i
1 to |E|uv
ith lightest edge in E
if F(u) 6= F(v)
U(u, v)
add uv to F
return F

After the initial sort, the algorithm performs exactly V M
S operations(one for each vertex), 2E F
operations (two for each edge), and V 1 U
operations (one for each edge in the minimum spanning tree). We just describeda disjoint-set data structure for which M
S and Frequire O(1) time,and Uruns in O(log V ) amortized time. Using this implementation, thetotal time spent maintaining the set partition is O(E + V log V ).
But recall that we already need O(E log E) = O(E log V ) time just to sort theedges. Because this is larger than the time spent maintaining the U-Fdata structure, the overall running time of Kruskal’s algorithm is O(E log V),
A different disjoint-set data structure, which uses a strategy called union-by-rank with pathcompression, performs each U
or F
in O(↵(V )) amortized time, where ↵ is the almostbut-not-quite-constant inverse Ackerman function. If you don’t feel like consulting Wikipedia, justthink of ↵(V ) as 4. Using this implementation, the total time spent maintaining the set partitionis O(E↵(V )), which is slightly faster when V is large and E is very close to V .

�6��. M������ S������� T����

exactly the same as Bor vka’s algorithm, or Jarník’s algorithm with a normal(non-Fibonacci) heap.

Exercises. Let G = (V, E) be an arbitrary connected graph with weighted edges.
(a) Prove that for any cycle in G, the minimum spanning tree of G excludes
the maximum-weight edge in that cycle.
(b) Prove or disprove: The minimum spanning tree of G includes theminimum-weight edge in every cycle in G.
. Throughout this chapter, we assumed that no two edges in the input graphhave equal weights, which implies that the minimum spanning tree is unique.
In fact, a weaker condition on the edge weights implies MST uniqueness.
(a) Describe an edge-weighted graph that has a unique minimum spanningtree, even though two edges have equal weights.
(b) Prove that an edge-weighted graph G has a unique minimum spanning
tree if and only if the following conditions hold:• For any partition of the vertices of G into two subsets, the minimumweight edge with one endpoint in each subset is unique.
• The maximum-weight edge in any cycle of G is unique.
(c) Describe and analyze an algorithm to determine whether or not a graphhas a unique minimum spanning tree.
. Most classical minimum-spanning-tree algorithms use the notions of “safe”
and “useless” edges described in the text, but there is an alternate formulation.
Let G be a weighted undirected graph, where the edge weights are distinct.
We say that an edge e is dangerous if it is the longest edge in some cycle
in G, and useful if it does not lie in any cycle in G.
(a) Prove that the minimum spanning tree of G contains every useful edge.
(b) Prove that the minimum spanning tree of G does not contain any
dangerous edge.
(c) Describe and analyze an efficient implementation of the following
algorithm, first described by Joseph Kruskal in the same
paper
where he proposed “Kruskal’s algorithm”. Examine the edges of G in
decreasing order; if an edge is dangerous, remove it from G. [Hint: It
won’t be as fast as Kruskal’s usual algorithm.]. (a) Describe and analyze an algorithm to compute the maximum-weightspanning tree of a given edge-weighted graph.
�68

Exercises(b) A feedback edge set of an undirected graph G is a subset F of the edges
such that every cycle in G contains at least one edge in F . In otherwords, removing every edge in F makes the graph G acyclic. Describe
and analyze a fast algorithm to compute the minimum-weight feedbackedge set of a given edge-weighted graph.
. Suppose we are given both an undirected graph G with weighted edges anda minimum spanning tree T of G.
(a) Describe an algorithm to update the minimum spanning tree when theweight of a single edge e is decreased.
(b) Describe an algorithm to update the minimum spanning tree when theweight of a single edge e is increased.
In both cases, the input to your algorithm is the edge e and its new weight;
your algorithms should modify T so that it is still a minimum spanning tree.
[Hint: Consider the cases e 2 T and e 62 T separately.]. (a) Describe and analyze an algorithm to find the second smallest spanning
tree of a given graph G, that is, the spanning tree of G with smallest
total weight except for the minimum spanning tree.
™

(b) Describe and analyze an efficient algorithm to compute, given a weighted
undirected graph G and an integer k, the k spanning trees of G withsmallest weight.

. A graph G = (V, E) is dense if E = ⇥(V 2 ). Describe a modification of
Jarník’s minimum-spanning tree algorithm that runs in O(V 2 ) time (independent of E) when the input graph is dense, using only elementary data
structures—in particular, without using Fibonacci heaps. This variant of
Jarník’s algorithm was first described by Edsger Dijkstra in.
. Minimum-spanning tree algorithms are often formulated using an operation
called edge contraction. To contract the edge uv, we insert a new node,
redirect any edge incident to u or v (except uv) to this new node, and thendelete u and v. After contraction, there may be multiple parallel edges
between the new node and other nodes in the graph; we remove all but thelightest edge between any two nodes.
The three classical minimum-spanning tree algorithms described in thischapter can all be expressed cleanly in terms of contraction as follows. All
three algorithms start by making a clean copy G 0 of the input graph G
and then repeatedly contract safe edges in G 0 ; the minimum spanning tree
consists of the contracted edges.
�6�

�. M������ S������� T����

8

5

8

10

30

12

5

8
3

3

2
18

5
10
3

16

18

16

30
12

16

30

12

14

14

14
4

26

4

26

4

26

Figure �.�. Contracting an edge and removing redundant parallel edges.

• B: Mark the lightest edge leaving each vertex, contract all
marked edges, and recurse.
• J: Repeatedly contract the lightest edge incident to some fixedroot vertex.
• K: Repeatedly contract the lightest edge in the graph.
(a) Describe an algorithm to execute a single pass of Bor vka’s contraction
algorithm in O(V + E) time. The input graph is represented in an
adjacency list.
(b) Consider an algorithm that first performs k passes of Bor vka’s contraction algorithm, and then runs Jarník’s algorithm (with a Fibonacci heap)on the resulting contracted graph.
i. What is the running time of this hybrid algorithm, as a function of
V , E, and k?
ii. For which value of k is this running time minimized? What is theresulting running time?
(c) Call a family of graphs nice if it has the following properties:• Contracting an edge of a nice graph yields another nice graph.
• Every nice graph with V vertices has only O(V ) edges.
For example, planar graphs—graphs that can be drawn in the plane withno crossing edges—are nice. Contracting any edge of a planar graphleaves a smaller planar graph, and Euler’s formula implies that every
planar graph with V vertices has at most 3V 6 edges.
Prove that Bor vka’s contraction algorithm computes the minimum
spanning tree of any nice graph in O(V ) time.
. Consider a path between two vertices s and t in a undirected weighted
graph G. The width of this path is the minimum weight of any edge in thepath. The bottleneck distance between s and t is the width of the widest
path from s to t. (If there are no paths from s to t, the bottleneck distanceis 1; on the other hand, the bottleneck distance from s to itself is 1.)(a) Prove that the maximum spanning tree of G contains widest paths
between every pair of vertices.

���Exercises

t
1

11
6
4

5

3
12

10
s

9

7
8

2

The bottleneck distance between s and t is 9.

(b) Describe an algorithm to solve the following problem in O(V + E) time:
Given a undirected weighted graph G, two vertices s and t, and aweight W , is the bottleneck distance between s and t at most W ?
(c) Suppose B is the bottleneck distance between s and t.
i. Prove that deleting any edge with weight less than B does not change
the bottleneck distance between s and t.
ii. Prove that contracting any edge with weight greater than B does
not change the bottleneck distance between s and t. (If contraction
creates parallel edges, delete all but the heaviest edge between eachpair of nodes.)™

(d) Describe an algorithm to compute a minimum-bottleneck path between s
and t in O(V + E) time. [Hint: Start by finding the median-weight edgein G.]. Bor vka’s algorithm can be reformulated to use a standard disjoint-set
data structure to identify safe edges, just like Kruskal’s algorithm, insteadof explicitly counting and labeling components of the evolving spanning
forest F in each iteration.
In this variant, each component of F is represented by an up-tree; eachvertex v stores a pointer parent(v) to its parent, or to v itself if v is the rootof its up-tree. The subroutine F(v) returns the root of v’s up-tree, butalso applies path compression, reassigning all parent pointers from v to theroot to point directly to the root, to speed up future F
operations. The
subroutine U
combines two up-trees into one by making one of the tworoot nodes the parent of the other.
Path compression is a form of memoization!
Normally, U
is implemented more carefully to ensure that the root of the larger orolder up-tree does not change; however, those details don’t matter here.

����. M������ S������� T����

F

U

(v):
if parent(v) = v
return v
elsev̄
F(parent(v))
parent(v)v̄return v̄

(u, v):
ū F
(u)
v̄
F
(v)
eitherparent(ū)
orparent(v̄)

v̄ūIn the modified version of Bor vka’s algorithm, in addition to the parent
pointers, the root vertex v̄ of each component of F maintains an edge safe(v̄),
which (at the end of F
SE
) is the lightest edge with one endpointin that component.
F

A

S
E
(V, E):
for each vertex v 2 V
safe(v) N
found Ffor each edge uv 2 E
ū F
(u)
v̄
F
(v)
if ū 6= v̄
if safe(ū) = Nor w(uv) < w(safe(ū))
safe(ū) uv
if safe(v̄) = Nor w(uv) < w(safe(v̄))
safe(v̄) uv
found T
return foundS
E(V, E, F ):for each vertex v 2 V
if safe(v) 6= N
xysafe(v)
if F(x) 6= F( y)
U(x, y)
add x y to F

B

(V, E):F =?
for each vertex v 2 V
parent(v)vwhile FS
E
(V, E)A S
E(V, E, F )return F

Prove that each call to F
S
E
and A SE
requires only
O(E) time. [Hint: What is the depth of the up-trees when F
SE
ends?] It follows that this variant of B
also runs in O(E log V ) time.

���