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

Prim's algorithmenter image description here

1 Answer
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.

  • Directly start with selecting any random vertex.

  • Here, we select Vertex 1 at first.

Prim's Algorithm

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.

Please log in to add an answer.