Find whether a minimum spanning tree contains an edge in linear time?
I have the following problem on my homework:
Give an O(n+m) algorithm to find that whether an edge e would be a part of the MST of a graph
(We are allowed to get help from others on this assignment, so this isn't cheating.)
I think that I could do a BFS and find if this edge is a edge between two layers and if so whether this edge was the smallest across those layers. But what could I say when this edge is not a tree edge of the BFS tree?
Answer
As a hint, if an edge is not the heaviest edge in any cycle that contains it, there is some MST that contains that edge. To see this, consider any MST. If the MST already contains the edge, great! We're done. If not, then add the edge into the MST. This creates a cycle in the graph. Now, find the heaviest edge in that cycle and remove it from the graph. Everything is now still connected (because if two nodes used to be connected by a path that went across that edge, now they can be connected by just going around the cycle the other way). Moreover, since the cost of the edge was deleted wasn't any smaller than the cost of the edge in question (because the edge isn't the heaviest edge in the cycle), the cost of this tree can't be any greater than before. Since we started with an MST, we must therefore end with an MST.
Using this property, see if you can find whether the edge is the heaviest edge on any cycle in linear time.