0
573views
Using Prim's algorithm, determine minimum cost spanning tree for the weighted graph shown below, fig. Q3(b):

Prim's algorithm

0
38views

## Prim’s Algorithm

• Prim's Algorithm is a greedy approach that is used to find the Minimum Spanning Tree (MST) from a graph.

• Let's find out the minimum cost spanning tree for the given graph using Prim's Algorithm.

• In the given graph there are no loops and parallel edges are present.

• Therefore, no need for any type of removal.

• Here, we select Vertex 1 at first.

Finally, we get all the vertices that have been included in the Minimum Spanning Tree, so stop here.

Now, calculate the Cost of the above Minimum Spanning Tree (MST)

$$Cost\ of\ Minimum\ Spanning\ Tree\ = Sum\ of\ Weights\ of\ all\ edges\ of\ the\ MST$$

$$= (1, 3) + (1, 2) + (3, 5) + (5, 6) + (5, 4) + (6, 7) + (7, 8)$$ $$= 6 + 18 + 11 + 4 + 15 + 22 + 34$$ $$= 110\ Units$$

Thus, the Minimum Cost of the Spanning Tree for the given graph is 110 Units.