kruskal and prims algorithm _

ok

1. Minimum cost spanning tree Adjacency Matrix of a graph Kruskal Algorithm Prim’s Algorithm

2. Graph Graph is a data structure that consists of following two components: 1 .  A finite set of vertices also called as nodes. 2.  A finite set of ordered pair of the form (u, v) called as edge . Following is an example of an undirected graph with 5 vertices

3. Graph representation Adjacency Matrix : It is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be A dj [V][V], Adj [ i ][j] = 1 => indicates that there is an edge from vertex i to vertex j . Adj [ i ][j] = => indicates that there is no edge from vertex i to vertex j . The adjacency matrix for the above example graph is  

4. Minimum Spanning Tree   Here G =(V,E) V ={ a, b, c, d, e } E ={ (a, b) , ( a, c) , ( b ,e) , ( d, e) , ( c, d ) }

5. Minimum Spanning Tree   So Sum of edge’s weight of all spanning trees T1,T2,T3 and T4 is calculated .And minimum cost spanning tree (MCST ) is the one whose sum is minimum.

6. Applications of Minimum Cost Spanning Tree Spanning trees are widely used in designing an efficient network. For example, to design a network in which a group of differently located individuals wish to be connected together in a telephone network . This problem can be converted into a graph problem in which nodes are telephones The goal is to pick enough of these edges that the gives less maintenance cost An answer to this question is to find MCST 2. Designing of efficient routing algorithm . Suppose we want to find a airline routes The vertices of the graph would represent cities, and the edges would represent routes between the cities . Obviously, when we travel more, the more it will cost. So MCST can be applied to optimize airline routes

7. Algorithms for finding MCST The vertices of the graph would represent cities, and the edges would represent routes between the cities. Obviously , when we travel more, the more it will cost. So MCST can be applied to optimize airline routes

8. Kruskal Algorithm for finding MCST The vertices of the graph would represent cities, and the edges would represent routes between the cities. Obviously, when we travel more, the more it will cost. So MCST can be applied to optimize airline routes

9. Kruskal Algorithm for finding MCST The vertices of the graph would represent cities, and the edges would represent routes between the cities. Obviously, when we travel more, the more it will cost. So MCST can be applied to optimize airline routes

10. Kruskal Agorithm steps Step 1 : Sort all the edges in increasing order of weights Step2 : The function MAKE_SET(v), make a new set {v} for all vertices of G. For a graph with n vertices , it makes n components of disjoint set such as {1},{2},… and so on. Step 3 : Consider each edge (u, v) ε E of minimum weight and add the set A, if and only if it joins two nodes of different components/Sets . FIND_SET() function is used to check whether 2nodes belong to deifferent or same set. It returns a same integer value, if u and v belongs to same components (In this case adding ( u,v ) to A creates a cycle),otherwise it returns a different integer value) Step 4 : If an edge added to A then the two components containing its end points are merged into a single component. Step 5 : Finally the algorithm stops, when there is just a single component.

11. Example Consider the following graph to find MCST using Kruskal Algorithm. ed to optimize airline routes

12. Example

13. Example Total Cost of Spanning tree, T = 2+3+5+4+5+4=23

14. Analysis ‘ Considering |E| as number of edges=a |V| as number of vertices=n Initialize  A : O(1) First  for  loop: O(| V |) as|V |  MAKE-SET  operations Sort  E : O(| E|   lg  | E| ) Second  for  loop: O(| E| )  as |E| FIND-SETs  and  UNIONs Total Complexity=O(1)+O(|V|)+O(|E|)+O(|E| lg |E|) =O(|V|+|E|)+O(|E| lg |E|) Minimum Number of edges E=n-1 Maximum Number of edges E=n(n-1)/2 Consider when E is minimum i.e n Complexity=O(n+n-1)+O(n lg n)= O(2n+n lg n)= O(n lg n) =O( |V| lg |V|) Consider when E is maximum i.e n(n-1)/2 Complexity=O( n+n (n-1)/2)+O(n(n-1)/2 lg n(n-1)/2) = O(|E|+|E| lg n 2 )= O(|E|+2|E | lg n) =O( |E| lg |V|)

15. Prim’s Algorithm

16. Prim’s Pseudocode

17. Prim’s Steps

18. Example Apply PRIM’s algorithm on the following graph to find minimum-cost-spanning – tree (MCST)

19. Example Total Cost of the minimum spanning tree = 2+3+5+4+5+4 = 23

20. Analysis

21. Thank YOU [email protected]