Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Kruskal's Algorithm

Like Prim's algorithm, Kruskal's algorithm  also constructs the minimum spanning tree of a graph by adding edges to the spanning tree one-by-one. At all points during its execution the set of edges selected by Prim's algorithm forms exactly one tree. On the other hand, the set of edges selected by Kruskal's algorithm forms a forest of trees.

Kruskal's algorithm is conceptually quite simple. The edges are selected and added to the spanning tree in increasing order of their weights. An edge is added to the tree only if it does not create a cycle.

The beauty of Kruskal's algorithm is the way that potential cycles are detected. Consider an undirected graph tex2html_wrap_inline71355. We can view the set of vertices, tex2html_wrap_inline71357, as a universal set  and the set of edges, tex2html_wrap_inline71363, as the definition of an equivalence relation  over the universe tex2html_wrap_inline71357. (See Definition gif). In general, an equivalence relation partitions a universal set into a set of equivalence classes. If the graph is connected, there is only one equivalence class--all the elements of the universal set are equivalent. Therefore, a spanning tree is a minimal set of equivalences that result in a single equivalence class.

Kruskal's algorithm computes, tex2html_wrap_inline73027, a sequence of partitions  of the set of vertices tex2html_wrap_inline71357. (Partitions are discussed in Section gif). The initial partition consists of tex2html_wrap_inline71781 sets of size one:

displaymath73015

Each subsequent element of the sequence is obtained from its predecessor by joining two of the elements of the partition. Therefore, tex2html_wrap_inline73033 has the form

displaymath73016

for tex2html_wrap_inline73035.

To construct the sequence the edges in tex2html_wrap_inline71363 are considered one-by-one in increasing order of their weights. Suppose we have computed the sequence up to tex2html_wrap_inline73033 and the next edge to be considered is tex2html_wrap_inline72969. If v and w are both members of the same element of partition tex2html_wrap_inline73033, then the edge forms a cycle, and is not part of the minimum-cost spanning tree.

On the other hand, suppose v and w are members of two different elements of partition tex2html_wrap_inline73033, say tex2html_wrap_inline73055 and tex2html_wrap_inline73057 (respectively). Then tex2html_wrap_inline72969 must be an edge in the minimum-cost spanning tree. In this case, we compute tex2html_wrap_inline73061 by joining tex2html_wrap_inline73055 and tex2html_wrap_inline73057. I.e., we replace tex2html_wrap_inline73055 and tex2html_wrap_inline73057 in tex2html_wrap_inline73033 by the union tex2html_wrap_inline73073.

Figure gif illustrates how Kruskal's algorithm determines the minimum-cost spanning tree of the graph tex2html_wrap_inline72943 shown in Figure gif. The algorithm computes the following sequence of partitions:

eqnarray53724

   figure53726
Figure: Operation of Kruskal's Algorithm




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.