Least Cost Spanning Trees

Prim’s Algorithm

At each stage, include the least cost edge whose addition to the selected edges forms a tree.

       

The approach takes O(|E| log |V |) time for a graph G = (V, E). The time requirement is driven by the algorithm used for selecting the edges to be added in each stage.

1. Assume a priority queue Q for the nodes of the graph that have not been chosen yet.
2. For the priority evaluation, assign each node in Q the least cost of adding it into V - Q (i.e., the nodes already selected for inclusion the spanning tree T).
3. Initially, the priority queue is a complete tree, and each node carries a priority value  larger than the cost of all the edges.
4. Upon removing a node u from the queue Q, and adding it into the spanning tree T, the priority value is modified for each node v in Q that is adjacent to u. The changing of the priority value of a node may require the shifting of the up or down in the tree.

The initialization of the the priority queue takes O(|V |) time. Each deletion of a node from the queue takes O(log |V |) time, and so O(|V | log |V |) time takes to empty the queue. A modification of a priority value of a node in the queue takes O(log |V |) time, and |E| such changes are needed.

Consequently, the algorithm takes O(|V |) + O(|V | log |V |) + O(|E| log |V |) = O(|E| log |V |) time.

         

Kruskal’s Algorithm

A greedy algorithm: Visit the edges in order of increasing cost. Include just those edges that don’t create cycles.

 

 

 

 

Kruskal’s algorithm requires O(|E| log |E|) time for sorting the edges, O(|E|) time to traversing them, and O(|V | log |V |) time for checking the existence of cycles (employing the union-find algorithm below). Hence, the algorithm is of time complexity O(|E| log |E|).

Union-Find Algorithm

Kruskal’s algorithm relies on a union-find algorithm for checking cycles. The “union” operation unites equivalent sets of elements, and the “find” operation determines the sets in which the elements reside.

• Components are represented by linked lists, with each element carrying the name of its component. Initially, each of the components consists of a single node.
  
• Merging of components is accomplished by moving the elements of the smaller set into the bigger one. To that end, the shorter linked list is traversed to change the name of the set recorded in the elements, and the the last element in the shorter linked list is set to point to the first element of the longer list.

  A  B
  H  I
  A  C
  D  G
  E  F
  E  H
  D  A
  C  A
• The time to merge two components is linear in the number of elements in the shorter list
• Each node can be visited at most O(log |V |) times, since each merge at least doubles the cardinality of the shorter list. Hence, the algorithm is of time complexity O(|V | log |V |)