Prim's Algorithm: Minimum Spanning Tree (MST)

so today I want to talk about prims algorithm it's not it's not hard it's just the same as kruskal's algorithm it's just it's a bit more tricky so this isn't some things to consider it's similar to Dijkstra's algorithm if you're familiar with that for finding the shortest path and your resulting the tree that you get your minimum spanning tree cannot contain cycles just like kruskal's algorithm it runs in Big O of a log V same as kruskal's and it can be yeah that this funny timing can be decreased to we go up a plus V log D if you use the the Fibonacci heaps to implement the minimum priority queue all right so let's let's work through an example this is the same graph that I use for cross clauses straight from Corman's book but I think the example always helps so let's work to an example and things become much more clear so you can start with the arbitrary vertex in this case we'll just start with a and then so this is how it works so a can see two vertices B and H okay and one of them has the cost of four and another one has the cost of eight and prims algorithm will select the least costly edge so in this case it's a to B so we'll select highlight this edge right here all right so now we can we go to B and B can see the vertex C and H and we also keep track of what a can see okay the more vertices you add to your tree the more edges you have to consider so now we have to consider the edge between B and C between B and H and a NH okay and we select the least amount please cost the edge between those three well just go with B and C here doesn't matter which one you chose okay you can choose this this edge here too but we'll just choose P and C so you highlight this edge so now now you can see the vertex D F and I so we have to consider the edges all of these edges so a to H be 2 H see - I see 2 F C to D all these edges you have to consider when you choose your next smallest least costly edge okay so looking through this we have 7 4 2 11 and 8 we're going to choose 2 because that's this costly edge so we're going to highlight this path right here okay and now will you we are at the vertex I so now we have to consider the edge between C and D C and F I and G I and H B and H and a and H ok there are some other methods to do this like a minimum cut I just like to stick with this method it's just easier I think so now we have to choose the least cost of the edge between 7 4 6 7 11 and 8 ok so the least costly edge here seems to be this right here the C and F because he only has the cost the edge of for the edge weight of 4 okay so we highlight this well it's a poor highlight but whatever it does the job so now go to F and we have to consider all other edges that we had previously considered and even more so now we have to consider C and D a and H B and H inh I and G F and G F and E and F and D okay so this is way that's why it's a little tricky because you have to keep track of all these edges alright so which one is the the least cost of the edge it seems like the edge right here between F and G because it only has to cost at the edge of two so we will highlight this edge right here all right so remember it can't be any cycles in the graph that you the resulting MST okay so now we go to G and we have to consider all these edges plus more okay so we have this edge right here F and E F and D D and E C in I mean sorry no not D any F and D F and E C and D I and G G and H B and H a and H but looks like this I draw here is the least-cost edge because it's only the edge cost right here is only one so we're going to choose this right here alright so now we go to H and we have to pick the least costly edge now you see if we pick we have two sevens okay this number seven seems to be the lowest out of all of them but pay attention that we can't choose this edge right here say if we choose this path this will create a cycle and we can't have any cycles in there in the prims algorithm so therefore we must choose the path between C and D like so okay now now we are at D and we have to choose the next shortest neck next least costly edge notice we can't pick this edge right here a and H with the concept of eight because that will create a cycle in the graph we can't have that so the next this costly edge to consider is nine because we have nine 14 10 11 and 8 any other would if we choose any of these two right here 76 we will create a cycle so that's out and this is out so we have nine 14 10 and 11 obviously we're going to choose nine so we take this path right here and looks like we're done because if we pick any other edge it will form a cycle and we have also reached all the vertices in this graph so it looks like we're done and that's all there is to prims algorithm just watch it over again if you it's a little tricky practice at home and you'll get it it's not that hard it's just you've got to keep track of all the vertices and edges as you move through this graph

Channel: EducateYourself

Views: 326,878

Rating: 4.830688 out of 5

Keywords: prims, prim, prim algorithm, prims algorithm, algorithm, algorithms, minimum, min, mst, minimum spanning tree, tree, spanning, span, min span tree, prims algorithms, Prim's Algorithm, computer, computer science, design algorithms, dijkstras, kruskal, kruskals algorithm, prime, shortest path algorithm, shortest, path, shortest path, EducateYourself, educateyourself, educate yourself

Id: Uj47dxYPow8

Length: 6min 14sec (374 seconds)

Published: Thu Jun 23 2016