23-4 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.

cpp MAYBE-MST-A(G, w) sort the edges into nonincreasing order of edge weights w T = E for each edge e, taken in nonincreasing order by weight if T - {e} is a connected graph T = T - {e} return T

b.

cpp MAYBE-MST-B(G, w) T = Ø for each edge e, taken in arbitrary order if T ∪ {e} has no cycles T = T ∪ {e} return T

c.

cpp MAYBE-MST-C(G, w) T = Ø for each edge e, taken in arbitrary order T = T ∪ {e} if T has a cycle c let e' be a maximum-weight edge on c T = T - {e} return T

a. This does return an $\text{MST}$. To see this, we'll show that we never remove an edge which must be part of a minimum spanning tree. If we remove $e$, then $e$ cannot be a bridge, which means that e lies on a simple cycle of the graph. Since we remove edges in nonincreasing order, the weight of every edge on the cycle must be less than or equal to that of $e$. By exercise 23.1-5, there is a minimum spanning tree on $G$ with edge $e$ removed.

To implement this, we begin by sorting the edges in $O(E \lg E)$ time. For each edge we need to check whether or not $T - {e}$ is connected, so we'll need to run a $\text{DFS}$. Each one takes $O(V + E)$, so doing this for all edges takes $O(E(V + E))$. This dominates the running time, so the total time is $O(E^2)$.

b. This doesn't return an $\text{MST}$. To see this, let $G$ be the graph on 3 vertices $a$, $b$, and $c$. Let the eges be $(a, b)$, $(b, c)$, and $(c, a)$ with weights $3, 2$, and $1$ respectively. If the algorithm examines the edges in their order listed, it will take the two heaviest edges instead of the two lightest.

An efficient implementation will use disjoint sets to keep track of connected components, as in $\text{MST-REDUCE}$ in problem 23-2. Trying to union within the same component will create a cycle. Since we make $|V|$ calls to $\text{MAKESET}$ and at most $3|E|$ calls to $\text{FIND-SET}$ and $\text{UNION}$, the runtime is $O(E\alpha(V))$.

c. This does return an $\text{MST}$. To see this, we simply quote the result from exercise 23.1-5. The only edges we remove are the edges of maximum weight on some cycle, and there always exists a minimum spanning tree which doesn't include these edges. Moreover, if we remove an edge from every cycle then the resulting graph cannot have any cycles, so it must be a tree.

To implement this, we use the approach taken in part (b), except now we also need to find the maximum weight edge on a cycle. For each edge which introduces a cycle we can perform a $\text{DFS}$ to find the cycle and max weight edge. Since the tree at that time has at most one cycle, it has at most $|V|$ edges, so we can run $\text{DFS}$ in $O(V)$. The runtime is thus $O(EV)$.