Make your own free website on Tripod.com

Problem 19.2: Minimum-spanning tree algorithm using binomial heaps.

MST(G)
1 T <--
2 for each vertex vi, V[G]
3 do  Vi <-- {vi}
3     Ei <-- {(vi, v) E[G]}
5 while there is more than one set Vi
6 do choose any set Vi
7    extract the minimum-weight edge (u, v) from Ei
8    assume without loss of generality that u Vi and v Vj
9    if i  j
10    then T <-- T {(u, v)}
11    Vi <-- Vi Vj, destroying Vj
12    Ei <-- Ei Ej

Describe how to implement this algorithm using binomial heaps to manage the vertex and edge sets. Do you need to change the representation of a binomial heap? Do you need to add operations beyond the mergeable-heap operation? Give the running time of your implementation.

Answer:

This answer is based on the sample answer from Professor Ross McConnell, Colorado State University:

The property of Minimum Spanning Tree: There are a number of n points, which are connected together by n 1 connectors, the desired result is that we have to use the least number of connectors to connect all the points. To model the problem let give the undirected graph G = (V,E), where V is the set of points, E the set of possible interconnections between the pair of points and for each edge (u,v) E, we have a weight w(u,v) specifying the cost to connect u and v. We wish to find an acyclic subset T E that connects all of the vertices and whose total weight

w(T) = w(u,v) is minimized

(u,v)T

To construct the data structure of this problem we assume that the heap Vi is the set of edges between the pair of points (u,v) that needs to be connected and the heap keys Ei are their weights (the cost of connecting the points)

Using binomial heaps extract the node with minimum key. The procedure below is used to extract the node with the minimum key from the binomial heap V and returns a pointer to the extracted node.

BINOMIAL-HEAP-EXTRACT-MIN(Ei)

  1. Find the root x with the minimum key in the root list of Ei, and remove x from the root list of Ei
  2. Ej MAKE-BINOMINAL-HEAP()
  3. Reverse the order of the linked list od xs children, and set head[Ej] to point to the head of the resulting list.
  4. H BINOMIAL-HEAP-UNION(Ei, Ej)

Return x
let demonstrate the above procedure by graphic

 

 

 

 

 

 

 

 

 

 

 

 

 


x

 

 

 

 

 

 

 

 

 

 


The root x with the minimum key is removed from the root list of V

 

Head Ej

 


Oval: 26Oval: 23Oval: 16Oval: 12Ei

Oval: 25
 

 

 

 

 

 


The linked list of xs children is reversed, giving another binomial heap Ej

 

The result of uniting Ei and Ej

 

 

 

 

 

 

 

 

 

 

 


The BINOMIAL-HEAP-EXTRACT-MIN runs in O(lg n) time, due each function in this procedure takes O(lg n).