(Adapted from Problem 23-4) Below are the pseudocode for three potential algorithms to compute a minimum spanning tree. Each one takes in as arguments a connected, undirected graph G (with no self-loops) and a set of positive weights w, and returns a tree T. For each algorithm, decide whether the algorithm will always return a MST.

If it doesnt, give an input graph as a counterexample (for algorithms where edges are chosen in an arbitrary order, specify what order would cause it to fail).

If it does, explain briefly how you would implement the algorithm (what data structures/algorithms would you use to detect cycles or check connectivity), and give a reasonable upper bound on the runtime. It doesnt have to be the most efficient implementation, so long as your runtime is consistent with the implementation you give.

MAYBE_MST_A(G, w)

1 sort the edges into nonincreasing order of edge weights w

2 T = E

3 for each edge e, taken in nonincreasing order by weight

4 if T - {e} is a connected graph

5 T = T - {e}

6 return T

MAYBE_MST_B(G, w)

1 T = {}

2 for each edge e, taken in arbitrary order

3 if T {e} has no cycles

4 T = T {e}

5 return T

MAYBE_MST_C(G, w)

1 T = {}

2 for each edge e, taken in arbitrary order

3 T = T {e}

4 if T has a cycle c

5 let e be a maximum-weight edge on c

6 T = T - {e}

7 return T