Kruskal Algorithm

1. Kruskal Algorithm KRUSKAL(V,E,W) A ← Φ For each vertex v Є G[v] Do MAKESET[v] sort E into nondecreasing order of weight w Do if FINDSET [u]≠FINDSET[v] A ← A U {(U,V)} UNION(U,V) Return (A)

2. h g f b d c e a i Given: G is a connected undirected weighted graph 8 3 10 6 1 5 4 14 2 3 9 7 11 8

3. First sort the edges according to nondecreasing order of their weight

4. (h,g) - weight 1 (c,f) - weight 7 ( c,i) - weight 2 (b,c) - weight 8 (i,h) - weight 3 (c,d) - weight 8 ( i,g) - weight 3 (d,e) - weight 9 (a,b) - weight 4 (e,f) -weight 10 (a,h) - weight 5 (d,f) - weight 11 (g,f) - weight 6 (b,h) weight 14 h g f b d c e a i 8 3 10 6 1 5 4 14 2 3 9 7 11 8

5. (h,g): Select h g f b d c e a i 1

6. (c,i): Select h g f b d c e a i 1 2

7. Select (i,h): h g f b d c e a i 1 2 3

8. Reject h g f b d c e a i 2 3 3 1 (i,g):

9. Select h g f b d c e a i 4 2 3 1 ( a,b ):

10. Select h g f b d c e a i 4 5 1 3 2 (a,h):

11. (g,f): h g f b d c e a i 2 5 3 1 6 4 Select

12. Reject h g f b d c e a i 4 5 2 3 1 7 6 (c,f):

13. Select h g f b d c e a i 4 5 3 2 1 6 8 (c,d):

14. Reject h g f b d c e a i 4 5 3 1 8 2 6 8 (b,c):

15. Select h g f b d c e a i 4 5 2 3 1 6 8 9 (d,e):

16. Reject h g f b d c e a i 4 5 2 3 1 8 6 9 10 (e,f):

17. Reject h g f b d c e a i 4 5 3 2 1 6 8 11 9 (d,f):

18. Reject h g f b d c e a i 4 5 14 2 3 1 6 8 9 (b,h):

19. Minimum Spanning Tree Total weight(MST)=1+2+3+4+5+6+8+9=38 h g f b d c e a i 4 5 2 3 1 6 8 9