Prim's algorithm

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.

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.