Minimum Cost Spanning Tree

Let G=(V,E) be a connected graph where for all (u,v) in E there is a cost vector C[u,v].

• A graph is connected if every pair of vertices is connected by a path.

A spanning tree for G is a free tree that connects all vertices in G.

• A connected acyclic graph is also called a free tree.

The cost of the spanning tree is the sum of the cost of all edges in the tree. We usually want to find a spanning tree of minimum cost.

Example applications:

• Computer networks - vertices in the graph might represent computer installations, edges represent connections between computers. We want to allow messages from any computer to get to any other, possibly with routing thru an intermediate computer, with minimum cost in connections.

• Airline routes - vertices in the graph are cities, and edges are routes between cities. We want to service a connected set of cities, with minimum cost.

Properties of Free Trees

Property 1: A free tree with N >= 1 vertices has exactly N-1 edges.

Proof by Contradiction: Let G=(V,E) be the smallest free tree that doesn't satisfy property 1. G must have more than 1 vertex, since the only 1-vertex free tree has 0 edges, which satisfies property 1. Furthermore, there must be a vertex v with exactly 1 incident edge (v,w).

• No vertex can have 0 edges, as it wouldn't be connected, and so G would not be a free tree.
• If every vertex has at least two incident vertices, consider the path created from a vertex v, entering and leaving vertices by a different edge. Such a path will eventually form a cycle, so G isn't a free tree.

If we delete edge (v,w), we get a new tree G2 that satisfies property 1 (ow. we have a tree that is smaller than G but is a free tree, contradicting our assumption about G). Since G2 has N-1 vertices and N-2 edges, G must have N vertices and N-1 edges, contradicting our assumption about G.

Property 2: Adding an edge to a free tree introduces a cycle.

Proof: According to property 1, every free tree has N vertices and N-1 edges. If we added an edge to a free tree, we would have a connected graph with N vertices and N edges.

If the edge does not introduce a cycle, we would have a connected, acyclic graph, with N vertices and N edges, which is a free tree that violates property 1 (a contradiction).

Minimum Spanning Tree Property

Let G = (V,E) be a connected graph with a cost function on the edges.

Let U be a subset of V.

If (u,v) is an edge of lowest cost such that u is in U and v is in V-U, then there is a minimum spanning tree that includes (u,v).

Proof by contradiction:

Assume the contrary. Consider T, a MCST for G. According to property 2 of free trees, adding (u,v) to T introduces a cycle involving (u,v).

There must be another edge (u2,v2) in T such that u2 in U and v2 in V-U; otherwise there is no way for the cycle to leave vertices in U, enter vertices in V-U, and return without using (u,v) twice.

If we delete (u2,v2), we break the cycle and get a spanning tree T2. The cost of T2 is the cost of T - (u2,v2) + (u,v).

Since (u,v) is the least cost edge between vertices in U and V-U, the cost of T2 is less than or equal to the cost of T. This contradicts our assumption that a minimum cost spanning tree would not include (u,v).

Prim's algorithm to find the minimum cost spanning tree exploits this property.

Prim's Algorithm Overview

Initially, Prim's algorithm has one node in the spanning tree, and no edges.

The algorithm adds nodes to the spanning tree one at a time, in order of the edge cost to connect to the nodes already in the tree.

  
  PrimMCST( set <edge> &T)
  { set <vertex> U;
  
    /* T = set of edges in spanning tree */
    T = NULL;
    /* U = set of connected vertices so far */
    U = {1};
    while (U <> V) {
      /* Add least cost edge that adds node not in U */
      (u,v) = lowest cost edge st. u in U, v in V-U
      /* Add edge to spanning tree */
      Insert(T,u,v);
      /* Add v to set of connected vertices */
      Insert(U,v);
    }
    Print(T);
  } /* PrimMCST */
  
  

Analysis of Prim's Algorithm

Prim's algorithm is O(N^2).

The while loop is executed n-1 times, requiring O(N)

• We add one vertex to U each iteration

• We exit the loop when U = V

We can find the lowest cost edge from U to V-U in O(N) time.

• Maintain two arrays: Closest[v] and Lowcost[v].

• For v in V-U, Closest[v] is the vertex u in U closest to v.

• Lowcost[v] is the cost of (v,u).

Prim's Algorithm

  
  int C[N][N];
  PrimMCST (set <edge> *T)
  {  set <vertex> U;
     int Lowcost[N], Closest[N];
     int i,j,k;
     /* T = set of edges in spanning tree */
     /* U = set of all connected vertices */
     Insert(U,0);
     for (i = 1; i < N; i++) {
        Lowcost[i] = C[0][i]; Closest[i] = 0;
     }
     for (i = 1; i < N; i++) {
        min = Lowcost[2];  k = 2;
        for (j = 2; j < N; j++)
  	 if (Lowcost[j] < min) {
  	    min = Lowcost[j]; k = j;
  	 }
        /* Add edge to T, k to U */
        Insert(T,k,Closest[k]);
        Lowcost[k] = INFINITY;
        /* Adjust costs to enter U */
        for (j = 1; j < N; j++)
  	 if(C[k][j] < Lowcost[j] && Lowcost[j] < INFINITY) {
  	    Lowcost[j] = C[k][j]; Closest[j] = k;
        } }
     }
  } /* PrimMCST */
  
  

Kruskal's Algorithm

Prim's algorithm requires O(N^2) time. We can do better using Kruskal's algorithm if E << N^2.

Kruskal's algorithm constructs a MCST incrementally.

Initially, each node is in its own MCST, consisting of that node and no edges.

At each step in the algorithm, the two MCST's that can be connected together with the least cost are combined, adding the lowest cost edge that links a vertex in one tree with a vertex in another tree.

When there is only one MCST that includes all vertices, the algorithm terminates.

Since we must consider the edges in order of their cost, we must sort them, which requires O(E log E). Merge can be implemented in O(E log E).

Kruskal's algorithm is O(E log E), which is better than Prim's algorithm if the graph is not dense (ie, E << N^2).