Kruskal’s Algorithm

This is an example of Kruskal’s Algorithm.

1. Welcome to my presentation S yed Maniruzzaman-Pabel ID: 142-15-4186

2. Kruskal’s Algorithm…. Trace Kruskal's algorithm in finding a minimum-cost spanning tree for the undirected, weighted graph given below

3. A B C D E F G H 10 15 12 2 4 3 4 6 5 3 7 2 Fig: Kruskal’s Algorithm…. Vertex Edge 16 17 Here weights are: 10,12,15,2,4,3,4,6,5,3,7,2,16,17 A B C D E G H 10 2 4 3 2 16 F 3 fig: Final Graph After sorting in ascending : 2,2,3,3,4,4,5,6,7,10,12,15,16,17

4. After sorting in ascending: 2,2,3,3,4,4,5,6,7,10,12,15,16,17 Choice Weight A,D 2 E,G 2 A,B 3 F,G 3 A,E 4 A,C 10 B,H 16 Total 40 A B C D E F G H 10 2 3 4 3 2 Edge Fig: Final Graph Vertex 16 So total weight is 40

5. Thank you everybody….