Question

Given a graph G and its MST T, we construct a new graph G' GU {e} by adding an edge e = (u, v) (suppose there is no edge between u, v in G). = Design an algorithm to find the MST of G' with running time O(n), where n is number of nodes in G.

Answer 1

To find the MST of G', we will use Kruskal's algorithm. The running time of this algorithm is O(n), where n is the number of nodes in G.

Step-by-step explanation:

To find the MST of G', we will use Kruskal's algorithm. The steps are:

1. Create an empty graph G' initially.
2. Add all the edges of MST T to G'.
3. Add the new edge e = (u, v) to G'.
4. Sort all the edges of G' in non-decreasing order of their weights.
5. Initialize an empty set S to store the connected components of G'.
6. Iterate over the sorted edges of G':
   
   • If the current edge does not create a cycle in G', add it to the MST and update S.

The running time of this algorithm is O(n), where n is the number of nodes in G. This is because we are sorting the edges of G' and iterating over them, which takes linear time.