Page 291 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Figure 14.11: Sixteen Spanning Trees of a Complete Graph on four Vertices

x x x x

Now suppose the edges of the graph have weights or lengths. The weight of a tree is just the sum
of weights of its edges. Obviously, different trees have different lengths. The problem: how to

find the minimum length spanning tree?
This problem can be solved by many different algorithms. It is the topic of some very recent
research. There are several “best” algorithms, depending on the assumptions you make:

A randomized algorithm can solve it in linear expected time.
It can be solved in linear worst case time if the weights are small integers. Otherwise, the best
solution is very close to linear but not exactly linear. The exact bound is O(m log beta(m,n)) where

the beta function has a complicated definition: the smallest i such that log(log(log(...log(n)...))) is
less than m/n, where the logs are nested i times.
These algorithms are all quite complicated, and probably not that great in practice unless you’re
looking at really huge graphs. Here we’ll go through two simple classical algorithms.

14.3.1 Kruskal’s Algorithm

We’ll start with Kruskal’s algorithm, which is easiest to understand and probably the best one for
solving problems by hand.

Kruskal’s algorithm is an algorithm in graph theory that finds a minimum spanning tree for

a connected weighted graph. This means it finds a subset of the edges that forms a tree that
includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph
is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each

connected component).
Kruskal’s algorithm is an example of a greedy algorithm. This algorithm first appeared in

Proceedings of the American Mathematical Society in 1956, and was written by Joseph Kruskal.

286 LOVELY PROFESSIONAL UNIVERSITY