Solution to the chapter 21 problem

The following algorithm will solve the problem:

• Check to see if the new edge can directly replace an existing edge. If it can, pull out the old edge and put in the new only if the new one is cheaper than the old edge.
• If the new edge was not in the spanning tree it must cause a cycle somewhere in the graph. Find the most expensive edge in that cycle. If it is more expensive that the new one, remove it and put in the new edge.

Here is an iterative algorithm to find the most expensive edge in the cycle:

• Let u and v be the two vertices the new edge connects.
• Run a version of BFS starting from u using only the old edges. Stop as soon as v enters the queue. Also, replace the logic in BFS that sets d values to instead set the d value of each vertex equal to the weight of the edge that goes to that vertex.
• Go to v and follow the predecessor pointers back to u. Each time you cross an edge on that path note its weight.

If the most expensive edge on that path has a weight greater than that of the new edge, remove that expensive edge and put the new edge into the graph.

Homework assignment

As an alternative to the iterative algorithm using BFS and a search that runs from v back to u we can also solve this problem by modifying DFS.

Modify the DFS algorithm to find the most expensive edge on the path from u to v and return that edge to you.

Implement this algorithm in C++ and use it to solve the chapter 21 problem.