Chapter 15
Least Cost Spanning Trees

15.1 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.

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

15.2 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|).

15.3 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 |)

15.4 Demo Applets and Resources

• Prim’s algorithms
• applet for Kruskal’s algorithm
• Kruskal’s algorithm
• Kruskal’s and Prim’s algorithms
• Info about the union-find algorithm

15.5 Assignment #7 (due We, Nov 10)

Write a (real) program that reads the edges of a directed graph, internally stores the graph using the adjacency list approach, and then prints

1. The list of nodes, and the list of nodes that are adjacent to each of these node.
2. An adjacency matrix of the graph.
3. A topologically sorted list of the nodes of the graph, if the graph is acyclic.

   A list of nodes is said to be topologically sorted, if node ‘A’ precedes node ‘B’ in the listing whenever there exists an edge from node ‘A’ to node ‘B’.

   The lists of nodes ‘A,B,C’ and ‘A,C,B’ are the only topologically sorted lists for the the following graph. The list ‘B,A,C’ is an example of one which is not topologically ordered.

   

   Hint: Assume an indegree field in each node.

Your program should be well documented, and accept files of pairs of integers for input. Each pair represents an edge.

Submit a printout of the program, of an input file, and of the corresponding output.