PRIM’S AND KRUSKAL’S ALGORITHM

It is Data-Structure

1. PRIM’S AND KRUSKAL’S ALGORITHM Gauri Bharat (24) Anushka Bhave (25) Dhairyashil Desai (37) Jaydeep Desai(38)

2. Content 01 Prim’s Algorithm 02 Application of Prim’s algorithm 03 Kruskal’s algorithm 04 Application of Kruskal’s Algorithm

3. Prim’s Algorithm

4. Basic terms 01 03 02 sub-graph of an undirected and a connected graph, which includes all the vertices of the graph having a minimum possible number of edges. Spanning tree Greedy Algorithm works by making the decision that seems most promising at any moment; it never reconsiders this decision, whatever situation may arise later. Greedy algorithm spanning tree in which the sum of the weight of the edges is as minimum as possible. Minimum spanning tree

5. Steps for prim’s Algorithm Choose a vertex and find shortest edge from it Mark this edge as visited and add to spanning tree Select another non visited edge with the minimum weight Repeat the process till we get spanning tree with all vertices

6. Prims Application Network design telephone, electrical, hydraulic, TV cable, computer, road

7. Google map network

8. Cluster Analysis

9. Kruskal’s Algorithm Minimum Spanning Tree Finds a subset of the   edges  that forms a tree that includes every  vertex , where the total weight of all the edges in the tree is minimized It is a greedy algorithm in graph theory

10. Applications of Kruskal’s Algorithm Reducing data storage (amino acids) Cluster analysis Network Design salesman Problems .

11. Kruskal’s algorithm applications On your trip to Venice, you plan to visit all the important world heritage sites but are short on time. To make your itinerary work, you decide to use Kruskal’s algorithm using disjoint sets

12. Kruskals algorithm Application Cannaregio Ponte Scalzi Santa Corce Dell ‘Orto Ferrovia Piazzale Roma San Polo Dorso Duro San Marco St. Mark Basilica Castello Arsenale A B C D E F G H I J K L B,C I,J B,E C,G G,I C,D K,L E,F A,B A,C 1 1 2 2 2 2 3 4 6 6 A,D E,C J,L F,H F,G H,I I,K D,J G,H H,K 6 7 8 10 11 12 16 18 22 25

13. Remove all loops and parallel edges So for the given map, we have a parallel edge running between Madonna dell’Orto (D) to St. Mark Basilica (J), which is of length 2.4kms(2400mts). We will remove the parallel road and keep the 1.8km (1800m) length for representation

14. Differences Prims algorithm It start to build MST from any node Selects shortest edge connected to that vertex Prims algorithm is faster for dense graphs Kruskal’s algorithm It start to build the MST from minimum weighted edge in the graph Selects next shortest edge which does not create any cycle Kruskal’s algorithm is faster for sparse graphs

15. Thank you