1
1.5kviews
Write down Prims algorithm and solve the following problem
written 6.3 years ago by | modified 23 months ago by |
Subject: Analysis Of Algorithm
Topic: Greedy Method
Difficulty: High
ADD COMMENT
EDIT
1 Answer
written 6.3 years ago by | modified 23 months ago by |
Subject: Analysis Of Algorithm
Topic: Greedy Method
Difficulty: High
written 23 months ago by |
Step 1 -
Step 2 -
Step 3 -
Step 4 -
Let's find out the minimum cost spanning tree for the given graph using Prim's Algorithm.
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, 2) + (2, 7) + (2, 3) + (3, 4) + (4, 5) + (5, 6) $$ $$ = 30 + 14 + 16 + 12 + 22 + 25 $$ $$ = 119\ Units $$
Thus, the Minimum Cost of the Spanning Tree for the given graph is 119 Units.