Ask
Login
0
4.3kviews
Find the minimum spanning tree of the following graph using kruskals algorithm
written 7.2 years ago by gravatar for teamques10 teamques10 ★ 64k •   modified 7.2 years ago

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

Marks: 10M

Year: May 2016
analysis of algorithms
ADD COMMENT EDIT
1 Answer
0
296views
written 7.2 years ago by gravatar for teamques10 teamques10 ★ 64k

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.