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 10.7.1 Kruskal’s Algorithm, Complexity: worst-case: O( | E | log | E | )-time
Kruskal's is faster than Prim's if | E | << | V |²
[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 10.7.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 10.7.2 Prim’s Algorithm, Complexity: O(|V|²)-time
[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 10.7.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.

Algorithm 10.7.3 Dijkstra’s Algorithm, Complexity: O(|V|²) -time
[To determine the shortest path in a nontrivial connected weighted (p, q) graph G.]
Input: G [a connected simple graph with a positive weight for every edge], ∞ [a number greater than the sum of the weights of all the edges in the graph], w(u, v) [the weight of edge {u, v}], a [the starting vertex], z [the ending vertex].

1. Initialize T to have no vertices other than a. Let V(T) be the set of vertices of T, and let E(T) be the set of edges of T ¬ v.
2. Let L(a) = 0, and for all vertices in G except a, let L(u) = ∞. [The number L(x) is called the label of x.]
   
3. Initialize v to equal a and F to be {a}. [The symbol v is used to denote the vertex most recently added to T.]
4.  while (z ɇ V(T))
   
   1. F = (F - {v}) U {vertices that are adjacent to v and are not in V(t)} [The set F is called the fringe. Each time a vertex is added to T, it is removed from the fringe and the vertices adjacent to it are added to the fringe if they are not already in the fringe or the tree T.]
      
   2. For each vertex u that is adjacent to v and is not in V(T),
      if L(v) + w(v, u) < L(u) then
                                            L(u) = L(v) + w(v, u)
                                            D(u) = v
      [Note that adding v to T does not affect the labels of any vertices in the fringe F except those adjacent to v. Also, when L(u) is changed to a smaller value, the notation D(u) is introduced to keep track of which vertex in T gave rise to the smaller value.]
   3. Find a vertex x in F with the smallest lavbel.
      Add vertex x to V(T), and add edge {D(x), x} to E(T).
      v = x [This statement sets up the notation for the next iteration fo the loop.]
      
   end while

Output: L(z) [a nonnegative integer, the length of the shrotest path from a to z.]
http://mathworld.wolfram.com/DijkstrasAlgorithm.html