Prim's Algorithm Presentation for prims algorithm (1).pptx

prims algorithm

1. Prim’s Algorithm Invented By: Vojtěch jarník

2. What is Spanning Tree? Given a connected undirected graph, a spanning tree of that graph is a sub graph that is a tree and joined all vertices. A single graph can have many spanning trees. 2

3. Minimum Spanning Tree Minimum Spanning Tree is a Spanning Tree which has minimum total cost. If we have a linked undirected graph with a weight (or cost) combine with each edge. Then the cost of spanning tree would be the sum of the cost of its edges. 3

4. 4 The idea of prim’s algorithm is Start with any vertex(say A) of the graph G(V, E), to build a tree T. Add the least cost edge to the tree T provided one of the endpoints of that edge must be in T. Add the edges until all the vertices are covered. Same here also, the cycle should not be formed on adding an edge.

5. 5 Repeat 3 until all nodes are connected. Basic Algorithm

6. EXAMPLE: Find the minimum spanning tree of given graph using Prim’s Algorithm 6

7. Solution: Step 1:  Remove all loops and parallel edges Remove all loops and parallel edges from the given graph. In case of parallel edges, keep the one which has the least cost associated and remove all others. 7

8. Conti.. Step 2: Choose any arbitrary node as root node In this case, we choose S node as the root node of Prim's spanning tree. This node is arbitrarily chosen, so any node can be the root node. In the spanning tree all the nodes of a graph are included and because it is connected then there must be at least one edge, which will join it to the rest of the tree. 8

9. Conti.. Step 3: Check outgoing edges and select the one with less cost After choosing the root node S, we see that S,A and S,C are two edges with weight 7 and 8, respectively. We choose the edge S,A as it is lesser than the other. 9

10. Conti.. Now, the tree S-7-A is treated as one node and we check for all edges going out from it. We select the one which has the lowest cost and include it in the tree. 10

11. Conti.. Step 4: After this step, S-7-A-3-C tree is formed. Now we'll again will check all the edges again. However, we will choose only the least cost edge. In this case, C-3-D is the new edge, which is less than other edges' cost 8, 6, 4, etc. 11

12. Conti.. After adding node D to the spanning tree, we now have two edges going out of it having the same cost, i.e. D-2-T and D-2-B. Thus, we can add either one. But the next step will again yield edge 2 as the least cost. Hence, we are showing a spanning tree with both edges included. 12

13. Example 2: Construct a minimum spanning tree of the graph given in the following figure by using prim's algorithm. 13

14. Solution: Step 1 : Choose a starting vertex B Step 2: Add the vertices that are adjacent to B. the edges that connecting the vertices are shown by dotted lines. 14

15. Step 3:  Choose the edge with the minimum weight among all. i.e. BD and add it to MST. Add the adjacent vertices of D i.e. C and E. 15

16. Step 4:  Choose the edge with the minimum weight among all. In this case, the edges DE and CD are such edges. Add them To MST and explore the adjacent of C i.e. E and A. 16

17. Step 5:  Choose the edge with the minimum weight i.e. CA. We can't choose CE as it would cause cycle in the graph. The graph produces in the step 4 is the minimum spanning tree of the graph shown in the above figure. The cost of MST will be calculated as; cost(MST) = 4 + 2 + 1 + 3 = 10 units. 17

18. 18 Cluster analysis Image segmentation Handwriting recognition Medical Image Processing Identify patterns in gene expression Approximation to NP hard problems Document categorization for web search Network design for telephone, electrical, hydraulic, TV cable, computer, road etc. There are many indirect applications also. Applications:

19. THANK YOU 19