**MST(G)**

1 T <-- Æ

2 **for** each vertex *v _{i},
*Î V[G]

3

3 E

5

6

7 extract the minimum-weight edge (

8 assume without loss of generality that

9

10

11 V

12 E

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 V_{i} is the set of edges between the pair of points
(u,v) that needs to be connected and
the heap keys E_{i} 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(E_{i})

- Find
the root x with the minimum key in the root list of E
_{i}, and remove x from the root list of E_{i} - E
_{j}ß MAKE-BINOMINAL-HEAP() - Reverse
the order of the linked list od x’s children, and set head[E
_{j}] to point to the head of the resulting list. - H ß
BINOMIAL-HEAP-UNION(E
_{i}, E_{j})

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 E_{j}

E_{i}

The linked list of x’s children is reversed, giving another
binomial heap E_{j}

The result of uniting E_{i and }E_{j}

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