Minimum spanning tree

kruskal and prims algorithm

1. Minimum Spanning Trees 1 Presenting by:- Muhammed Ahmed MCA III rd sem.

2. Problem: Laying Telephone Wire 2 Central office

3. Wiring: Naive Approach 3 Central office Expensive!

4. Wiring: Better Approach 4 Central office Minimize the total length of wire connecting the customers

5. Minimum Spanning Tree (MST) 5 it is a tree (i.e., it is acyclic) it covers all the vertices V contains |V| - 1 edges the total cost associated with tree edges is the minimum among all possible spanning trees not necessarily unique A minimum spanning tree is a subgraph of an undirected weighted graph G , such that

6. Applications of MST Any time you want to visit all vertices in a graph at minimum cost (e.g., wire routing on printed circuit boards, sewer pipe layout, bridges routing table, road planning…) Internet content distribution it is a hot research topic Idea: publisher produces web pages, content distribution network replicates web pages to many locations so consumers can access at higher speed MST may not be good enough! content distribution on minimum cost tree may take a long time! Provides a heuristic for traveling salesman problems. The optimum traveling salesman tour is at most twice the length of the minimum spanning tree. 6

7. How Can We Generate a MST? 7 a c e d b 2 4 5 9 6 4 5 5 a c e d b 2 4 5 9 6 4 5 5

8. Prim’s Algorithm 8 Initialization a. Pick a vertex r to be the root b. Set D ( r ) = 0, parent ( r ) = null c. For all vertices v  V , v  r , set D ( v ) =  d. Insert all vertices into priority queue P , using distances as the keys a c e d b 2 4 5 9 6 4 5 5 e a b c d     Vertex Parent e -

9. Prim’s Algorithm 9 While P is not empty: 1. Select the next vertex u to add to the tree u = P.deleteMin () 2. Update the weight of each vertex w adjacent to u which is not in the tree (i.e., w  P ) If weight ( u,w ) < D ( w ) , a. parent ( w ) = u b. D ( w ) = weight ( u,w ) c. Update the priority queue to reflect new distance for w

10. Prim’s algorithm 10 a c e d b 2 4 5 9 6 4 5 5 d b c a 4 5 5  Vertex Parent e - b e c e d e The MST initially consists of the vertex e, and we update the distances and parent for its adjacent vertices Vertex Parent e - b - c - d - d b c a     e

11. Prim’s algorithm 11 a c e d b 2 4 5 9 6 4 5 5 a c b 2 4 5 Vertex Parent e - b e c d d e a d d b c a 4 5 5  Vertex Parent e - b e c e d e

12. Prim’s algorithm 12 a c e d b 2 4 5 9 6 4 5 5 c b 4 5 Vertex Parent e - b e c d d e a d a c b 2 4 5 Vertex Parent e - b e c d d e a d

13. Prim’s algorithm 13 a c e d b 2 4 5 9 6 4 5 5 b 5 Vertex Parent e - b e c d d e a d c b 4 5 Vertex Parent e - b e c d d e a d

14. Prim’s algorithm 14 Vertex Parent e - b e c d d e a d a c e d b 2 4 5 9 6 4 5 5 The final minimum spanning tree b 5 Vertex Parent e - b e c d d e a d

15. Kruskal’s algorithm 15 Initialization a. Create a set for each vertex v  V b. Initialize the set of “safe edges” A comprising the MST to the empty set c. Sort edges by increasing weight a c e d b 2 4 5 9 6 4 5 5 F = {a}, {b}, {c}, {d}, {e} A =  E = {(a,d), (c,d), (d,e), (a,c), (b,e), (c,e), (b,d), (a,b)}

16. Kruskal’s algorithm 16 For each edge ( u,v )  E in increasing order while more than one set remains: If u and v , belong to different sets U and V a. add edge ( u,v ) to the safe edge set A = A  { ( u,v )} b. merge the sets U and V F = F - U - V + ( U  V ) Return A

17. Kruskal’s algorithm 17 E = {(a,d), (c,d), (d,e), (a,c), (b,e), (c,e), (b,d), (a,b)} Forest {a}, {b}, {c}, {d}, {e} {a,d}, {b}, {c}, {e} {a,d,c}, {b}, {e} {a,d,c,e}, {b} {a,d,c,e,b} A  {(a,d)} {(a,d), (c,d)} {(a,d), (c,d), (d,e)} {(a,d), (c,d), (d,e), (b,e)} a c e d b 2 4 5 9 6 4 5 5

18. Complexity Kruskal's algorithm can be shown to run in  O ( E   log   E ) time, or equivalently,  O ( E  log  V ) time. Where  E  is the number of edges in the graph and  V  is the number of vertices. The time complexity of prim’s Algorithm is given by: T(n)=2(n-1)(n-1) є Ө (n 2 ) where n=no. of vertices. 18

19. Difference The basic difference is in which edge you choose to add next to the spanning tree in each step. In Prim's, we always keep a connected component, starting with a single vertex. we look at all edges from the current component to other vertices and find the smallest among them. we then add the neighboring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph. In Kruskal's , we do not keep one connected component but a forest. At each stage, we look at the globally smallest edge that does not create a cycle in the current forest. Such an edge has to necessarily merge two trees in the current forest into one. Since we start with N single-vertex trees, in N-1 steps, they would all have merged into one if the graph was connected. 19

20. Greedy Approach Both Prim’s and Kruskal’s algorithms are greedy algorithms . The greedy approach works for the MST problem; however, it does not work for many other problems ! 20

21. That’s All