Prim's algorithm in 2 minutes — Review and example

this video will show you the correct way to run prims algorithm on a graph prims algorithm results in a minimum spanning tree a minimum weight connected graph with no cycles let's run prims algorithm on this graph to start create an empty list called visited we will use this list to keep track of nodes that we have touched the next step is to pick an arbitrary node we will start the algorithm from this node let's start with a in our graph first add a to the visited list next examine all vertices reachable from a they are shown in the graph with blue edges prims is a greedy algorithm so we're going to choose the smallest edge that connects to an unvisited node in this case a to be the red nodes are the start of our minimum spanning tree notice that B has been added to the visited list we now look at all nodes reachable from a and B three edges all have a weight of three pick one of these I've chosen to add AC continue in this manner each time picking the smallest edge that connects to an unvisited node notice at this point the edge be e within weight of three is the smallest edge but both vertices are already in the MST so we do not pick it instead we will choose to add F to the MST the only unvisited node remaining is G so we add this to the minimum spanning tree all the nodes are now connected in a tree note that if edge weights are distinct this minimum spanning tree will be unique you can add the edge weights to get the minimum spanning trees total edge weight the time complexity depends on the data structures you use in your algorithm the algorithm shown here is fairly easy to implement and that's it I hope this video gave you a good understanding of prims algorithm

Channel: Michael Sambol

Views: 676,488

Rating: 4.9441996 out of 5

Keywords: Prim's Algorithm, Graph Theory, Prim's, Graph Algorithms, Prims, Prim, Prim's Example

Id: cplfcGZmX7I

Length: 2min 16sec (136 seconds)

Published: Sun Oct 28 2012