(a) Suppose we decrease the weight of one of the edges in G that is not among the edges in T. Suggest an algorithm in plain English that determines whether T is still a minimum spanning tree, and if it is not, calculates a minimum spanning tree of G. Explain the running time of your algorithm. (Note: Your algorithm should be faster than Prim’s and Kruskal’s)
Data Structures and
You are given a weighted undirected graph G = (V,E), where E and V denote set of edges and vertices, and a minimum spanning tree T of that graph G. Answer the following questions about G and T on minimum spanning trees.
(a) Suppose we decrease the weight of one of the edges in G that is not among the edges in T. Suggest an algorithm in plain English that determines whether T is still a minimum spanning tree, and if it is not, calculates a minimum spanning tree of G. Explain the running time of your algorithm. (Note: Your algorithm should be faster than Prim’s and Kruskal’s)
(b) Consider the following algorithm running on G = (V,E). Would it calculate a valid MST of G? If yes, explain your reasoning in plain English, if no, provide a counter example graph that the algorithm will fail producing an MST. Also, what is the running time of the algorithm in the previous question. Show your analysis.
![1 MSTcandidate (G)
2
E
sort G.E in decreasing order of edge weights
3
E
4
for i from 1 to |E| do
{E[i]} is a connected graph
{E[i]}
5
if T -
T
-
7
end if
8
end for
9
return T](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F8e85e096-6423-4a35-815c-6db40b8d92fd%2Fe488067b-1221-4337-9f7e-123b230459f7%2Fph77u66_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
