This question is related to Minimum Spanning Trees (MSTs), I\'m not sure of the

Question

This question is related to Minimum Spanning Trees (MSTs), I'm not sure of the algorithm...

Given an undirected graph G = (V, E) with a cost c_e on each edge e E. You wish to find a minimum cost spanning tree. However you are told that a set S C V cannot be used as internal vertices in the tree. Give a polynomial time algorithm that either outputs a spanning tree T of minimum cost subject to the constraint that each vertex in S must be a leaf in T, or determines that no such feasible spanning tree exists.

Explanation / Answer

This below analys of MST will helps you to understand the find the cost of MST..

The below MST algorithm will be find the minimum cost of Spanning tree.
This below algorithm is prims algorithm is used to find the Cost of Minimum Spanning Tree..

Prims Algorithm:

E is the set of all edges in G
S = {1}
T is empty (T will store edges of a MST)
while S not equal V do
   pick e = (v, w) belongs E such that
       v S and w V S
       e has minimum cost
   T = T e
   S = S w
return the set T

Analysis of MST optimal algorithm:
Number of iterations = O(n), where n is number of vertices
Picking e is O(m) where m is the number of edges
Total time O(nm)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.