Exercises 23.2-8

The algorithm fails on G=(V,E), V={1,2,3,4}, E={(1,2),(1,3),(2,4),(3,4)} which weight is {1,2,3,4}. If = {1,2}, = {3,4}, the minimum spanning tree of {3,4} is edge (3,4) which is not in minimum spanning of G.

Exercises 23.2-7

Let node u be the new vertex, and E’ be the incident edges. The minimum spanning tree for G=(V+u, T+E’) is the solution. Since T+E’ is O(V), using the Prim’s algorithm with Fibonacci heap, it can be done in O(V lgV) time.

Exercises 23.2-6

Kruskal algorithm is faster, since we can use the bucket sort.

Exercises 23.2-5

If the weight is bounded by W, we can use the array to implement priority queue. Hence the EXTRACT-MIN can be done in O(W)=O(1) time. Then the total running time is O(E).

If the weight is bounded by V, this situation is complicated. Using van Emde Boas data structure, or redistributive heap may help.

Exercises 23.2-4

O(Eα(V)), since we can sort in linear time.

Exercises 23.2-3

	E=Θ(V)	E=
Binary Heap	V lgV
Fibonacci Heap	V lgV

Exercises 23.2-2

Use array to maintain the priority queue. The operation EXTRACT-MIN will be in O(n) time.

Exercises 23.2-1

If edge e is in T, then let e be the smallest edge among all edges which weights are equal to e.