Kruskal’s algorithm

The purpose of making this presentation is to explain Kruskal's Algorithm in a simple and attractive way. However, the content of this presentation is taken from more than one resources and merged at one place for the better understanding of students. It also contains an example which will definitely help students to understand it more quickly.

1. BENAZIR BHUTTO SHAHEED UNVERSITY Department of Computer Science Under the guidance of: Sir Ali Aurangzeb

2. Kruskal’s Algorithm Presented by: Abdul moIz KHATRI 3 rd SEMESTER – Batch 6 th BECHALORS OF COMPUTER SCIENCE Presentation on:

3. JOSEPH KRUSKAL Joseph Kruskal was an  American  Mathematician ,  Statistician and C omputer Scientist. He was born in January 29, 1928. He was a student at the University of Chicago earning a Bachelor of Science in Mathematics in the year of 1948 and a Master of Science in Mathematics in the following year 1949 . After his time at the University of Chicago, Kruskal attended Princeton University , where he completed his Ph.D.  in Mathematics in the year of 1954. In Statistics , Kruskal's most influential work is his seminal contribution to the formulation of  Multidimensional Scaling . In Computer Science , his best known work is  Kruskal's Algorithm  for computing the  Minimal Spanning Tree  (MST) of a weighted graph . He died in September 19, 2010.

4. WHAT IS AN Algorithm? An Algorithm is a step-by-step procedure to solve a given problem.

5. An Algorithm is a step-by-step procedure to solve a given problem. Answer the simple question. How will you log into your Facebook account? You may answer: Using Desktop Laptop Tablet Smart Phone etc… Correct..! But if I say to write an algorithm to log into your Facebook account. Go to www.Facebook.com . Enter Email & Password. Click on Login button. All you have to do is to write the correct steps in correct sequence. WHAT IS AN Algorithm?

6. KRUSKAL’s ALGORITHM

7. Kruskal's Algorithm is an Algorithm for Computing the Minimal Spanning Tree (MST) of a Weighted Graph. KRUSKAL’s ALGORITHM A  Minimal Spanning Tree  is a Spanning Tree of a connected, undirected graph which connects all the vertices together with the Minimal total weightage for its edges and it always have V- 1 Edges. A B C D 1 3 2

8. Kruskal's Algorithm is an Algorithm for Computing the Minimal Spanning Tree (MST) of a Weighted Graph. KRUSKAL’s ALGORITHM   A weighted graph is a graph whose vertices or edges have been assigned weights. A B C D 1 3 2 2 5

9. LETS SEE A GRAPH…! A B C D 1 3 2 2 5 Vertices Edge Weight of an Edge

10. HOW to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm? We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . Remember….

11. A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . We have 5 edges. So our edge table will have 5 columns . Create the edge table . ( An edge table will have name of all the edges along with their weight in ascending order ) Edge Weight STEPS to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm

12. Edge Weight

13. A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . Edge Weight Now look at the graph and fill the 1st column with the edge of minimum weight. In this case edge BC is of least weight so we will select it . BC 1 Now look at the graph again and find the edge of next minimum weight . In this case edge AB and AC are having the minimum weight so we will select them both . Note! In case we have two or more edges with same weight then we can write them in any order in the edge table . AB 2 AC 2

14. A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . Edge Weight BC 1 Now look at the graph again and find the edge of next minimum weight . In this case edge AB and AC are having the minimum weight so we will select them both . Note! In case we have two or more edges with same weight then we can write them in any order in the edge table . AB 2 AC 2

15. A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . Edge Weight BC 1 AB 2 AC 2 Now look at the graph again and find the edge of next minimum edge. In this case edge DC has the minimum weight so we will select it. DC 2 Now look at the graph again and find the edge of next minimum edge . In this case edge BD has the minimum weight so we will select it . BD 5

16. Steps to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm. A B C D 1 3 2 2 5 Create the edge table. (An edge table will have name of all the edges along with their weight in ascending order ) We have 5 edges so our edge table will have 5 columns. Now look at the graph and fill the 1st column with the edge of minimum weight. In this case edge BC is of least weight so we will select it. Now look at the graph again and find the edge of next minimum weight. In this case edge AB and AC are having the minimum weight so we will select them both. Note! In case we have two or more edges with same weight them we can write them in any order in the edge table. Now look at the graph again and find the edge of next minimum edge. In this case edge DC has the minimum weight so we will select it. Now look at the graph again and find the edge of next minimum edge. In this case edge BD has the minimum weight so we will select it.

17. A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . TIME to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm Edge Weight BC 1 AB 2 AC 2 DC 2 BD 5 Note! Our graph has 4 vertices. So , our MST will have 3 edges .

18. We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . TIME to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm Edge Weight BC 1 AB 2 AC 2 DC 2 BD 5 1 is the smallest weight. So we will select edge BC. B C 1 A B C D 1 3 2 2 5

19. A 2 A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . TIME to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm Edge Weight BC 1 AB 2 AC 2 DC 2 BD 5 2 is the next smallest weight and edge AB does not form a circuit with the previously selected edges. So we will select it. B C 1

20. A 2 A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . TIME to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm Edge Weight BC 1 AB 2 AC 2 DC 2 BD 5 2 is the smallest weight. But if we select edge AC then it will form a circuit. So we are going to reject edge AC. B C 1

21. D 3 A 2 A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . TIME to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm Edge Weight BC 1 AB 2 AC 2 DC 2 BD 5 3 is the next smallest weight and edge DC does not form a circuit with the previously selected edges. So we will select it. B C 1

22. D 3 A 2 A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . TIME to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm Edge Weight BC 1 AB 2 AC 2 DC 2 BD 5 3 is the next smallest weight and edge DC does not form a circuit with the previously selected edges. So we will select it. B C 1

23. D 3 A 2 A B C D 1 3 2 2 5 We will always start from the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges . TIME to find Minimal Spanning Tree (MST) by using Kruskal’s Algorithm Edge Weight BC 1 AB 2 AC 2 DC 2 BD 5 B C 1 Since we have got the 3 edges. So we will stop here.

24. THEREFORE, OUR REQUIRED MINIMUM SPANNING TREE IS D 3 A 2 B C 1

25. Minimal Spanning tree Kruskal's Algorithm is an Algorithm for Computing the Minimal Spanning Tree (MST) of a Weighted Graph.  A minimum spanning tree is a Spanning Tree of a connected, undirected graph. It connects all the vertices together with the Minimal total weightage for its edges . Time to find the Minimum Spanning Tree. Note! Our graph has 4 vertices so, our MST will have 3 edges. To find the Minimum Spanning Tree 1 is the smallest weight so we will select edge BC. 2 is the next smallest weight and edge AB does not form a circuit with the previously selected edges. So we will select it. 2 is the smallest weight. But if we select edge AC then it will form a circuit. So we are going to reject edge AC. 3 is the next smallest weight and edge DC does not form a circuit with the previously selected edges. So we will select it . Since we have got the 3 edges so we will stop here. Therefore, our required Minimum Spanning Tree is A B C D 1 3 2 2 5