algorithmgraphminimum-spanning-treeundirected-graphspanning-tree

How to find the MST of a Graph in |V| Time given a spanning tree plus another edge

I'm wondering how to go about solving this problem.

I'm given a graph G = (V,E). This is a connected undirected weighted graph.
The graph consists of a spanning tree and one additional edge.
How would I come up with an algorithm that would compute the MST of the graph in n = |V| time complexity.
I was thinking of Kruskal's Algorithm but it wouldn't meet the time complexity requirement.

Solution

  • A spanning tree plus one edge makes exactly one cycle. Find the cycle using depth-first search, and then remove its heaviest edge.