Given the graph G below Kruskals algorithm will add those 6

Given the graph G below,

Kruskal’s algorithm will add those 6 edges first to future MST:

1) _____ 2) ______3) _____ 4) ______5) _____ 6) ______.

Prim’s algorithm will add those 6 edges first to future MST:

1) _____ 2) ______3) _____ 4) ______5) _____ 6) ______.

17 21 33 16 55 43 18 28 45 22 35 15 10 16 57 29

Solution

Krushkal\'s algorithm always uses lowest to hightest weight.
it first sort all the edge via weight.
here first 6 smallest weigth 3,6,9,10,13,14
so edges are :
1)P-X 2) Y-F 3) G-K 4)H-J 5) I-G 6) L-K

Prism\'s algorithm : it choose smallest weighted edge than make the pool of edges which are
connected to their vertices. after that choose the smallest weighted edges from that pool and so on
so first edge is :
1)P-X
here the weigth of connected edge to P and X are 22,35,16,21 so smallest is 16(X-Y)
2) X-Y
now 22,35,21,44,18,6,42 so smallest is 6(Y-F)
3) Y-F
now 22,35,21,44,18,42,28,55 so smallest is 18(Y-I)
4) Y-I
now 22,35,21,44,42,28,55,28,45 so smallest is 22(P-H)
5) P-H
now 35,21,44,42,28,55,28,45,10,15 so smallest is 10(H-J)
6) H-J

1)P-X 2) X-Y 3) Y-F 4) Y-I 5) P-H 6) H-J