Kruskal Algorithm for minimum spanning..

Graph algorithm

1. KRUSKAL ALGORITHM B y G r o u p 12

2. Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which we can traverse every vertex of the graph. It follows the greedy approach that finds an optimum solution at every stage instead of focusing on a global optimum. # About Kruskal’s Algorithm

3. Spanning tree - A spanning tree is the subgraph of an undirected connected graph. Minimum Spanning tree - Minimum spanning tree can be defined as the spanning tree in which the sum of the weights of the edge is minimum. The weight of the spanning tree is the sum of the weights g i v e n t o t h e e d g e s o f t h e s p a nn i n g t ree . Some Basic Terms Before Starting:

4. In Kruskal's algorithm, we start from edges with the lowest weight and keep adding the edges until the goal is reached. The steps to implement Kruskal's algorithm are listed as f ollo w s - First, sort all the edges from low weight to high. Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to be added creates a c y c l e , t h e n r e j e c t t h e e d g e . C o n t i nu e t o a d d t h e e d g e s un t i l w e r e a c h a ll v e r t i c e s , and a minimum spanning tree is created. E x a m p l e o f K r u s k a l ’ s A l g o r i t h m How Does Kruskal’s Algorithm works? L e t ’ s l oo k a t h o w K r u s k a l ’ s a pp r o a c h f un c t i o n s u s i n g a n e x a m p l e . U s i n g a n e x a m p l e , i t w i ll b e e a s i e r t o c o m p r e h e n d K r u s k a l ’ s algorithm. L e t ’ s a ss u m e a w e i g h t e d g r a p h i s –

5. 1. ) Table after organizing the edges in the ascending order a cc o r d i n g t o t h e i r w e i g h t s : - Edge AB DE BC CD AE AC AD Weight 1 2 3 4 5 7 10

6. P h a s e 1 – J o i n t h e e d g e P Q h a v i n g t h e w e i g h t 1 t o t h e MST. P h a s e 2 – J o i n t h e e d g e S T h a v i n g t h e w e i g h t 2 t o t h e M S T . A l s o , p o i n t t o b e noted that this is not making any cycle.

7. P h a s e 3 – A dd t h e e d g e QR having the weight 3 t o t h e M S T P h a s e 4 – S e l e c t t h e e d g e R S h a v i n g t h e w e i g h t 4 t o t h e M S T ; a l s o , y o u w i ll n o t i c e t h a t i t i s n o t composing the cycle

8. Phase 5 – Now, we will select the edge PT having the weight 5. Adding this edge will form the cycle, so we will dump it. Phase 6 – Pick the edge PR having the weight 7. Adding this edge w i ll f o r m t h e c y c l e , s o w e w i ll d u m p i t . Phase 7 – Pick the edge PS having the weight 10. Adding this edge w i ll f o r m t h e c y c l e , s o w e w i ll d u m p i t .

9. T o t a l v a l u e o f M S T i s = P Q + S T + Q R + R S = 1 + 2 + 3 + 4 = 1 . I n t h e a b o v e t r ee , t h e nu m b e r o f e d g e s now equals the number of vertices m i nu s o n e . A s a r e s u l t , t h e a l g o r i t h m h a s r e a c h e d i t s c o n c l u s i o n . T h e f i n a l m i n i m u m s p a nn i n g t r e e o b t a i n e d f r o m t h e g i v e n w e i g h t e d graph by using Kruskal's algorithm

10. T H E A PP L I C A T I O N S O F K R U S K A L ’ S ALGORITHM The technique by Kruskal can be used to build out electrical wiring across cities. I t ’ s p o ss i b l e t o o p er a t e i t t o s e t up L A N c o nn e c t i o n s .

11. Group Members: Shashwat Mishra 23BAI10448 Dev Marwah 23BAI10310 Dhanni Watti 23BCY10343 Prateek Chhabra 23BAI10169 Rajrup Roy Choudhury 23BAI10213 Aryan Desai 23BAI10179

12. THANK YOU