me wk book

Question

let T be a minimum cost spanning tree of G. suppose that ewe decreased the weight of one of the edge in T.then to check modified T is MST or not how much tym will take???

O(1)

or

O(n)?????

Answer 1

O(1). No need to check at all. It will definitely remain MST of the graph G. $T$ already contains minimum possible edge weights it can have. And Now if you decrease some edge's weight which is present in MST, then It(this edge) will still be best choice for MST

Comments

ya i was also thinking same

---

If we decrese edge weight in G . Then we need O(n) time.????

---

yes ...then the question will become like detecting cycle use dfs O(v+e)

and e can be v-1 so O(v+v-1)=O(v)

---

@eyeamgj-You cannot assume e will always be v-1. It can be O(V2) in case of dense graph so complexity should be O(V+E)

---

but to construct a mst we only need v-1 edges...