Alternative minimum-spanning-tree algorithms In this

Chapter 23, Problem 23-4

(choose chapter or problem)

Alternative minimum-spanning-tree algorithms In this problem, we give pseudocode for three different algorithms. Each one takes a connected graph and a weight function as input and returns a set of edges T . For each algorithm, either prove that T is a minimum spanning tree or prove that T is not a minimum spanning tree. Also describe the most efficient implementation of each algorithm, whether or not it computes a minimum spanning tree. a. MAYBE-MST-A.G; w/ 1 sort the edges into nonincreasing order of edge weights w 2 T D E 3 for each edge e, taken in nonincreasing order by weight 4 if T feg is a connected graph 5 T D T feg 6 return T b. MAYBE-MST-B.G; w/ 1 T D ; 2 for each edge e, taken in arbitrary order 3 if T [ feg has no cycles 4 T D T [ feg 5 return T c. MAYBE-MST-C.G; w/ 1 T D ; 2 for each edge e, taken in arbitrary order 3 T D T [ feg 4 if T has a cycle c 5 let e0 be a maximum-weight edge on c 6 T D T fe0 g 7 return T