MST-related algorithm

Question

Given an undirected and connected graph G(V,E) with weight function w:E->R, an edge e(u,v) belongs to E. Which algorithm that runs in linear run-time complexity can assure if there's a minimal spanning tree that contains the edge e?

Answer 1

Perform depth-first search starting from u and ignoring any edge with weight equal to weight of given edge or heavier. If DFS completes without visiting v, this means there is no cycle where given edge is the heaviest edge, therefore given edge is contained in some minimal spanning tree.

Answer 2

This is asking you to implement Prim's Minimum Spanning Tree twice.

• The first time run the algorithm as normal. Make a note of the weight of the mst.

• The second time, instead of starting with an empty tree as Prim's algorithm normally does, start with the nodes u and v already on the tree -- which is the same as having edge e(u,v). Then continue building the mst.

• at the end if the second mst is the same weight as the first mst, then edge e(u,v) can be in a mst. If not, there is a lighter mst.

By the way, 2*O(n) is still O(n)