Prim's Algorithm for Minimum Spanning Tree | Graph Theory #13

hey guys in the last video we have seen what is a spanning tree and a minimum spanning tree today we are going to see an algorithm for finding out the minimum spanning tree the name of the algorithm is Prince algorithm so this is the graph and we want to find out the minimum spanning tree from this graph so these are the steps for this algorithm so let's start the first step is remove loops and parallel edges and while removing loops and paddle edges you have to keep the minimum width ages okay so I will explain it here what does it mean so first is use so where is the loop in this graph see this is the loop so this age starts at E and ends at E so this is the loop so we will remove this loop we will directly remove this loop okay yes so for removing the loop you should not consider any weight or any cost okay you have to directly remove that loop age right now the parallel ages so here you have to consider the weight now for the parallel age here see CD there are two edges they are parallel to each other because they start from the same vertex and yield and the same one takes okay so which age should be keep so we will keep the minimum weight or minimum cost okay so what is the minimum cost out of these two since is the minimum cost so we will keep this and you will delete this age which is having more cost because it was having cost nine so nine is more than six so I deleted this age okay so the first step is over now now let's go for second step so in the second here see we are going to add edges for the spanning P so the second step says that while adding new age so when we are adding new age select age with minimum weight out of what out of the ages from already visited one basis okay so these are the visited vertices we will write it in this set and these are the ages from the visited vertices means the edges which are incident on the visited vertices so suppose there is a vertex I okay so this is the vertex and these are the ages from this vertex so the edges which are connected to this vertex they are called as the edges incident on that were this edges incident on that vertex or they are called as ages from that vertex okay so it is written here out of the edges from already visited witnesses so we will write the safety and you will write those edges here as we go further in this algorithm okay and also why I am doing this a cycle should not be formed so no cycle is allowed while adding the edges okay so you should keep doing this till you reach to n minus 1 edges means suppose n is equal to here they are 10 monetizes okay here there are element Isis so in this you have to take n minus 1 means 10 minus 1 inch is so nine edges so while converting this graph into a minimum spanning tree you have to take nine edges and you have to stop when you add the nine th after adding the ninth stop this algorithm now let's start with the second step okay now the first age or the first age so see for the first age you can choose any word X so the first word text you can choose so I choose one takes L as the first vertex and the first edge will be from vertex a okay so see the visited vertex is a no so what are the edges incident on vertex a so see for vertex L the Inge's incident are a B and a C a B and a C so he'll be comma easy these are the edges incident from vertex a what are the weights one and seven okay these are the weights now you have to select edge with minimum weight from these edges okay minimum weight from these edges so what is minimum a B is minimum so I will take H AV so I take H AV okay the weight is one right so as H AV is taken now be adds to the visited what Isis said because now a B makes vertex B as the visited vertex okay so it is added and it's a B is cancelled from this set because it is now added to the spanning tree right so this is for the first age so this is the first iteration now let's go for second age take an age okay so see now again we will go by adding new age select age with minimum weight out of the ages from already visited vertices okay so what are the already visited offenses a and B right so right all the edges incident on a and B in this sit but you can see here we have already little edges incident on a we have already written them here so we have to add the edges from vertex B so from vertex B C the first stage is be a but it is already written in the C so no need to take again now second it is BC then B b and b e so bc b b and b e right now right the waits for d c5 b ds3 and ve is full so five three four okay so these are the edges and their weights now the current set is this now from this set you have to choose the minimum so choose what is the minimum read is the minimum so add that is this belief at that age what is the mid weight is three right so because of HB D now D becomes the visited vertex B is added to this state and we will be concerned because it is added to the spanning tree right so these are very simple steps you just have to follow the steps now let's go for the third age so the third is now you have to write ages from the visited vertices so now visited vertices are a B and D so ideally you have to write all the edges from a BD in this set but we have already written the ages from a and B we have already written down here so we have to just add the edges incident on D what are the additions in return d bc then de BH + DG so b c d e bj + d h there is also another age that is B be but this BB is already added to this set that is this hvd see its beauty it's same as h DV because this is an undirected graph so that it is already added so we don't add this age okay we add all other edges so let's add so DC de the edge and DJ right right the weights now one for DC de is to D H is mine and DJ is three now from this world set now what is the minimum width that is DC the width one so add that so we added DC so what it takes C is added what is the weight that is one so as vertex C is added it is written in the visited monetizes state and HP c is cancelled because it is added to the spelling bee now let's go for the fourth age so write all the changes from this visited vertices he'll be B and C but if it is already done so on we add the new ages from vertex C so from vertex C yes from vertex C all the edges are already there in the set so no need to add any edge here just choose the minimum from this set okay so what is the minimum D E is the minimum right so ad that is the spanning tree so de is minimum what's the weight weight is - okay that is added to the spanning tree so E is added to the visited one Isis set and de will be deleted from here because de is added to the spanning tree now let's go for the fifth age now for the fifth is you have to write all the edges incident on a VDC but up to a VDC all the edges are returned years just add pages for e so it just incident on e our CEO eh EF and eh these are the two edges Edie and V's also there but they are already visited so we don't need to write them here okay sorry EF and EH right EF and eh what are the weights 1 & 4 1 & 4 okay so now what is the minimum in this set EF is the minimum so add that to the spanning tree so I add EF weight is 1 ok so I added EF to the spanning tree so this edge is deleted and F is added to the visited one at exit this is the visited one fix it f is added to that st. I will write this F here because I need space for this graph shall we write that in the next line okay so this steak is over now let's move for the sixth angel now for the sixth age again and the edges incident on F to this state so one of the edges incident on F F G okay this is the age and if E is also there but it is already visited means it is already in the same so no need to write it again so only FG is there FG so now F G so mate is 2 now let us see what is the minimum yes FG is the minimum so I added what's the great weight is 2 so G is added to the visited what Isis said and M G will be deleted from here okay now let us go for say month age now for say month age edges incident on G is added so G this is added to the city I will write it here gh is added what's the weight weight is so from this state what is the minimum now see seven five four nine three three is the minimum so DJ is the minimum in this state so we have to add a DJ here it is okay so DJ so I add G what's the mid weight is three so DJ is the minimum currently in this state so see this step proves that the minimum is not necessarily from the currently visited holidays see the currently visited over at x1 G but this time the minimum is not from the currently visited vertex this is from previously visited Oh antics okay some people may misunderstand that it is always from the currently visited wanna text but it is not so okay now as G is added you have to add jail to the visited wat SS sit and DJ will be deleted okay so let's go for L is known now for the in it is C and a just incident on J so for j j k okay that is the rage what is the weight for JK with is for now currently in the state chain which one is minimum seven five four nine four eight foot okay so four is the minimum so you can take any of the three ages I will take ve so where is ve see this is ve so I choose B but now here is another condition that is no cycle is allowed so I cannot take be okay that is why I cannot take me so I have to skip be e and go for next four that is the next minimum so eh now E Jake yes eat we can take es because it does not form a cycle so this is clear now if a cycle is formed then it is not alone so we have to skip that edge and we have to take the next minimum so eh is added so I delete this and H is added to the visited one is this it now let's go for the nine tails so for the nine th C incident edges on edge let's add them see there are four edges incident but out of those four edges this three are already processed in this set they are already processed only one edge is remaining that is H key so we added so HK saimin now what is the minimum currently C seven five four nine eight four seven so again ve is minimum but it forms a cycle so we should skip it and go for next minimum that is JT so c JK yes that does not form a cycle so I can take that so the weight is for now and JK is taken you have to adhere to the visited what Isis said okay and JK will be deleted means it is indicated as it is processed so let's go for the tenth H yes so this pain is greater than nine means n is greater than n minus 1 here because n is 10 so 10 minus 1 is 9 so here we stop as 9 ages are over in this spanning tree here we stop so this is the minimum spanning tree for this graph so this is the way prims algorithm finds out the minimum spanning means the important step is this select page with minimum weight out of the edges from already visited vertices and don't form the cycle anywhere hey friends please subscribe to my channel as I post algorithm videos everyday and if you want a video on any particular topic then please mention in the comment below thank you

Channel: Vivekanand Khyade - Algorithm Every Day

Views: 76,936

Keywords: Prim's algorithm for minimum spanning tree, spanning tree, data structures, weigth cost of edges, code, program, computer science

Id: QyJ8gOss-Y8

Length: 18min 29sec (1109 seconds)

Published: Fri Mar 15 2019