Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which
* form a tree that includes every vertex
* has the minimum sum of weights among all the trees that can be formed from the graph
How Prim's algorithm works
It falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of finding a global optimum.
We start from one vertex and keep adding edges with the lowest weight until we reach our goal.
The steps for implementing Prim's algorithm are as follows :
* Initialize the minimum spanning tree with a vertex chosen at random.
* Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
* Keep repeating step 2 until we get a minimum spanning tree
