Minimum Spanning Trees (MST)

 

Consider a graph G = (V,E), such that each edge (u,v) Í E has a weight, w(u,v), associated with it. A MST is a subset T Í E that connects all of the vertices and whose total weight w(T) = ĺ w(u,v) is minimized.

 

We will consider three algorithms to construct a MST for an undirected connected graph:

1.     Prim

2.     Kruskal                 -- all three use the greedy approach

3.     Boruvka

 

Growing a spanning tree:

 

n     select a vertex v as an initial “partial tree”

n     add edges, one at a time such that each edge adds a new vertex to the partial tree

 

-- by making the condition be adding a new vertex, ensures that a cycle is not formed

 

O (n –1) steps

 

We describe the greedy method for finding a minimum spanning tree as an edge-coloring process.* Initially, all edges are uncolored.  Color one edge at a time, either blue (accepted) or red (rejected).  To color edges, the method uses two rules that maintain the following.

 

Color Invariant:    There is a minimum spanning tree containing all of the blue edges and none of the red ones.

 

We can apply the coloring rules at any time, in arbitrary order, until all edges are colored.

 

Blue Rule:   Select a cut that no blue edges cross.  Among the uncolored edges crossing the cut, select one of munimum weight and color it blue.

Red Rule:    Select a simple cycle containing no red edges.  Among  edges on the cycle, select one of maximum weight and color it red.

 

Prim’s Algorithm:

          Prim’s algorithm starts with an arbitrary root vertex r, and applies the following step n-1 stems:

         

Coloring step (Prim): Let T be the blue tree containing r.  Select a minimum-weight edge incident to T and color it blue.

 

Kruskal’s Algorithm:

          Kruskal’s algorithm builds a forest of blue trees into a single blue MST.  Initially, each vertex is a separate blue tree.  Apply the following step to the edges in nondecreasing order by weight:

 

Coloring step (Kruskal): If the current edge e has both ends in the same blue tree, then color it red; otherwise color it blue.

 

Boruvka’s Algorithm:

          Boruvka’s algorithm also builds a forest of blue trees into a single blue MST.  Initially, each vertex is a separate blue tree.  Apply the following step until there is only one blue tree:

 

Coloring step (Boruvka): For each blue tree T, select a minimum-cost edge incident to T.  Color all selected edges blue.

 

*R. E. Tarjan (1983).  Data Structures and Network Algorithms, CBMS-NSF Regional Conference in Applied Mathematics, SIAM, Philadelphia.

 

 

 

A cut in a graph G = (V,E) is a partition of its vertices into S and S’ = V – S.

 

An edge crosses a cut if it has one endpoint in S and the other in S’.