University:
College
Course:
College Algebra
Academic year:

2023
Views:

17

Pages:

13
Author:

A. Priyank

Prim’s Algorithm Algorithm 1. Select an edge of graph G that has the smallest weight value and add it to the tree 2. Now select another edge from G which is not present in T but it is adjacent to a node present in T and having minimum weight value. 3. Add this new edge to tree T iff it does not form cycle 4. Repeat steps 2 and 3 till all the nodes are included in T. 2 1 6 2 4 3 5 7 3 5 5 4 1. Select an edge with minimum weight value. 1. T={1,5} weight=2 2. Remaining edges adjacent to 1 and 5 are{(1,2), (1, 3) (5, 3), (5,4)} 6 4 7 5 2. Select an edge with minimum weight value that is (1,3) T={1,3,5} weight is=4+2=6 2 1 4 43 5  3. now consider edges adjacent to 1, 3 and 5 and not present in T (1,2) (5,3) (5,4) (3,2) (3,4) 6 7 5 3 5 Select an edge of minimum weight which does not form cycle that is(3,2) T={1,3,5,2} 2 1 4 2 3 Now weight is=2+4+3=9 3 5  3. now consider edges adjacent to 1,2, 3 and 5 and not present in T (1,2) (5,3) (5,4) (3,4) 6 7 5 5 Select an edge of minimum weight which does not form cycle that is(5,4) T={1,3,5,2,4} 2 1 5 4 2 3 3 Now weight is = 2+4+3+5=14 5 4 Kruskal’s Algorithm 1. select an edge of graph G that has the smallest value and add it to tree T. 2. Now select another edge from G which is not present in T but having minimum weight value. 3. Add this new edge to T only if it does not form a cycle. 4. Repeat step 2 and 3 till all edges of G are included in T. 1 5 2 3 4 V={1,2,3,4,5} E={(1,5)(3,4)(5,4)(2,3),(1,2)(5,3)(1,3)} select an edge with minimum weight value that is(1,5) 1 2 5 2 3 T={1, 5} weight={2} 4 2 1 5 2 3 T={1, 5,3,4} weight={2+4}=6 4 4 2 1 5 2 4  T={1, 5,3,4,2} weight={2+4+3=9} 3 3 4 2 1 5 5 2 4 3 T={1, 5,3,4,2} weight={2+4+3+5=14} 3 4