Prim's Algorithm

prims algorithm for minimum spanning tree now before we go into the steps of prims algorithm let's first understand what is a minimum spanning tree so given a graph a minimum spanning tree is going to be a sub graph such that all the vertices in the original graph exist in this sub graph the sub graph is connected and that there are no cycles in the sub graph so essentially we are going to construct a tree out of the vertices and edges in the graph such that we cover all the vertices why do we call it minimum spanning tree because the edges we include we want the summation of the widths of those edges to be minimum so with this in mind let's take a look at an example so this is going to be the graph that we want to construct the minimum spanning tree for so let's see what prims algorithm is going to do the first step in prims algorithm is going to be to choose an arbitrary start vertex let's say I'm going to start at a now in prims algorithm what we are going to do is we are going to keep including into our MST connected edges so let's see what are the connected edges to a we have one edge here we have another edge and we have another edge now which of these edges will I choose I'm going to choose the minimum of these edges so I'm going to choose the edge which has two now that I have included B in my graph what are the connected edges the edges connected to B are these now I will want to include that shaded edge which is of minimum distance so I am going to include this edge which has a distance of 1 now that I have included D I'm going to see what are the connected edges I can get from that now given these shaded edges I am going to select the edge which has not yet been selected and has the minimum distance that is going to be due now that I have included D I am going to see what are the connected edges to e now out of these shaded edges I want to pick that edge which has not yet been included and is the minimum distance I see that I have a edge which is 3 here but the question arises can I add this edge the answer is no why can I not add the edge of 3 because in our minimum spanning tree we do not want any cycles so if we add the edge of 3 here then we will be getting a cycle between B D and E so we cannot add this 3 so apart from this 3 what is the minimum edge we can see that we have a 4 here I'm going to include this 4 now let's see what are the edges that we can get connected to G now out of these edges which is the minimum edge we can see that we have an edge of distance one so I'm going to insert that now we can see that out of these edges which have not yet been included which is the minimum edge we have an edge of four over here but can we include that edge no why because it forms a cycle so this four cannot be included after that we can see we have a five here can we include this five no because that will create a cycle between a B G and F so we cannot include this now we go to six can we include the six yes because it doesn't form a cycle and with that we have included all the vertices in our sub graph so in min prims algorithm we choose an arbitrary start vertex then we keep included including connected edges provided that it does not form a cycle and this connected edge should be the minimum so this is how prims algorithm to find the minimum spanning tree of a graph is going to work we can say that the weight of this spanning tree is going to be six plus four plus two plus two plus one plus one which is going to be 16 with that we come to the end of the working of prims algorithm

Channel: Lalitha Natraj

Views: 141,284

Rating: 4.907258 out of 5

Keywords:

Id: 5M7bOXrn54A

Length: 7min 18sec (438 seconds)

Published: Mon May 13 2019