The Algorithm Design Manual Second Edition

6.1.2

Kruskal’s Algorithm

Kruskal’s algorithm is an alternate approach to finding minimum spanning trees

that proves more efficient on sparse graphs. Like Prim’s, Kruskal’s algorithm is

greedy. Unlike Prim’s, it does not start with a particular vertex.

Kruskal’s algorithm builds up connected components of vertices, culminating in

the minimum spanning tree. Initially, each vertex forms its own separate component

in the tree-to-be. The algorithm repeatedly considers the lightest remaining edge

and tests whether its two endpoints lie within the same connected component. If

so, this edge will be discarded, because adding it would create a cycle in the tree-

to-be. If the endpoints are in different components, we insert the edge and merge

the two components into one. Since each connected component is always a tree, we

need never explicitly test for cycles.

Kruskal-MST(G)

Put the edges in a priority queue ordered by weight.

count = 0

while (count < n

− 1) do

get next edge (v, w)

if (component (v)

= component(w))

add to T

kruskal

merge component(v) and component(w)

---

6 . 1

M I N I M U M S P A N N I N G T R E E S

197

y

v1

v2

(a)

(b)

x

y

s

x

Figure 6.4: Where Kruskal’s algorithm goes bad? No, because d(v

1

, v

2

)

≥ d(x, y)

This algorithm adds n

− 1 edges without creating a cycle, so it clearly creates a

spanning tree for any connected graph. But why must this be a minimum spanning

tree? Suppose it wasn’t. As with the correctness proof of Prim’s algorithm, there

must be some graph on which it fails. In particular, there must a single edge (x, y)

whose insertion first prevented the tree T

kruskal

from being a minimum spanning

tree T

min

. Inserting this edge (x, y) into T

min

will create a cycle with the path

from x to y. Since x and y were in different components at the time of inserting

(x, y), at least one edge (say (v

1

, v

2

)) on this path would have been evaluated by

Kruskal’s algorithm later than (x, y). But this means that w(v

1

, v

2

)

≥ w(x, y), so

exchanging the two edges yields a tree of weight at most T

min

. Therefore, we could

not have made a fatal mistake in selecting (x, y), and the correctness follows.

What is the time complexity of Kruskal’s algorithm? Sorting the m edges takes

O(m lg m) time. The for loop makes m iterations, each testing the connectivity

of two trees plus an edge. In the most simple-minded approach, this can be im-

plemented by breadth-first or depth-first search in a sparse graph with at most n

edges and n vertices, thus yielding an O(mn) algorithm.

However, a faster implementation results if we can implement the component

test in faster than O(n) time. In fact, a clever data structure called union-find, can

support such queries in O(lg n) time. Union-find is discussed in the next section.

With this data structure, Kruskal’s algorithm runs in O(m lg m) time, which is

faster than Prim’s for sparse graphs. Observe again the impact that the right data

structure can have when implementing a straightforward algorithm.