A spanning tree for a graph G is a subgraph of G that contains every vertex of G and is a tree. A weighted graph is a graph for which each edge has an associated real number weight, w(e). The sum of the weights of all the edges is the total weight of the graph, w(G). A minimal spanning tree for a weighted graph is a spanning tree that has the least possible total weight compared to all other spanning trees for the graph.

The Minimum Spanning Tree Problem is one of the best known problems in combinatorial optimization. The MST problem was originally stated by Boruvka in 1926 while considering the rural electrification of Southern Moravia in Czechoslovakia. Perhaps the most famous of the algorithmic solutions of this problem is due to Kruskal. The object of Kruskal’s algorithm is to select edges of minimum weight successively from a connected weighted graph without forming cycles, until a spanning tree has been produced. Kruskal’s algorithm is a greedy algorithm. That is it makes the best choice possible at each step, regardless of the subsequent effect of that choice. Another application of the minimum spanning tree is an approximate solution to the traveling salesman problem (recall that finding the best solution to this problem is N-P hard). Approximate TSP solution: traverse the MST twice and your tour will be within a factor of 2 of the optimal solution.

Algorithm 11.6.1 Kruskal’s Algorithm, complexity: O(q²)
[To determine a minimum spanning tree in a nontrivial connected weighted (p, q) graph G.]

1. Initialize T to have all the vertices of G and no edges.
2. Let E be the set (sorted in increasing order by weight) of all edges of G and let m = 0.
3. while (m < (p – 1) )
   1. Find an edge e in E of least weight.
   2. Delete e from E.
   3. if addition of e to the edge set of T does not produce a circuit then add e to the edge set of T and set m = m + 1
   end while

Motivation: A hurricane has knocked down all the power lines between five subdivisions each separated by roads of varying distances. Determine the roads along which to rebuild the power lines so the subdivisions are reconnected using a minimum of the available resources.

Consider the graph given by the weighted adjacency matrix M (draw this graph):

The edges of M may be sorted by weight in nondecreasing lexicographical order: E = {uv, uw, vw, xy, ux, vx, uy, vy, wx}.

Constructing the tree, the first edge from algorithm 11.6.1 is uv, then uw, next vw is rejected (why?), then xy is added, ux is then picked and added to T but this is p – 1 edges so the algorithm kicks out T and stops.

Now lets consider another algorithm attributed to Prim who described it in 1957 (Jarnik had essentially discovered it in 1930). The method of the algorithm is to replace a current tree T in a connected weighted graph G by a new tree formed by adding an edge of minimum weight that joins a vertex of T to a vertex not in T.

Algorithm 11.6.2 Prim’s Algorithm, complexity: O(p³)
[To determine a minimum spanning tree in a nontrivial connected weighted (p, q) graph G.]

1. Initialize T to have no vertices. Let v be an arbitrary vertex of G and T ¬ v.
2. Let e be an edge of minimum weight joining a vertex of T and a vertex not in T, and
   T ¬ T + e.
3. if |E(T)| = p – 1, then output T; otherwise return to Step 2.

Constructing the tree: let v be the starting vertex. The first edge from algorithm 11.6.2 is uv, then uw, followed by ux, next xy is added but this is p – 1 edges so the algorithm kicks out T and stops.