Question

C. Construct Minimum Spanning Tree and calculate the cost MST: Ctrl) b) By Kurskal's Algorithm. B 30 12 30 F 28 8 7 10 20 20 11 1 A с E K G 8 5 29 H 30 8 30 D

Answer 1

Date Page Sobution KRUSKAL ALGORITHM sost all edges in man - decreasing order of weight SOURCE DESTINATION WEIGHT 5 7 Fomo o K 8 8 8 F H G. E lo А IL 12 20 G F B E K G 20 K 20 X 29 H A LG D 18 30 x 30 IX 30 D B X 30 B include de add it Pick edge E-H, no cycle is formed, E SH st Pick edge Kaf, no cycle is formed, include it F 71 K E 5 *H

fick edge K-M, no cycle ů posmed, include it F. L SK 7. E 5 & lick edge b-H, no cycle ů formed, include it ER IK 8 # 8 D. Pick edge F-G, ma cycle include it is formed 8 7 K G 5 en Pick edge A-E, no cycle is formed, include it F 8 E G 7 Ik 8 H A 10 D

Data Page pück edge Gacy mo eyele is formed, include it F 8 7 10 G C 5 8 H & D Pick edge F~B, no cycle is formed include et B 112 f 8 + lo Ik A ē MST formed using KAUSKAS ALGORITHM 5 H DO

Please note that the algorithm stopped after this step and we got the MST, since number of edges in a MST = Number of vertices-1. In this case number of vertices was 9 and edges were 8 in the final answer. If we would have continued the algorithm further for the rest of the edges, cycle would've formed and each edge would have been discarded anyways.

Cost of the MST is equals to the sum of all the edges in the MST i.e. 10+5+8+8+7+8+12+11= 69.

Please give an upvote if you liked my solution. Thank you :)