Find the minimum spanning tree of the following graph using kruskals algorithm

4.9kviews

written 9.0 years ago by

teamques10 ★ 70k

• modified 9.0 years ago

Mumbai University > Computer Engineering > Sem 4 > Analysis of Algorithm

Marks: 10M

Year: May 2016

analysis of algorithms

ADD COMMENT EDIT

1 Answer

311views

written 9.0 years ago by

teamques10 ★ 70k

enter image description here

Solution:

First we select all the vertices. Then an edge with optimam weight is selected from heap, even though it is not adjacent to previously selected edge. Care should be taken for not forming circuit.

Step 1:

enter image description here

Step 2:

enter image description here

Step 3:

enter image description here

Step 4:

enter image description here

Step 5:

enter image description here

Hence, the total weight is 16.

ADD COMMENT EDIT

Please log in to add an answer.