Prim's algorithm

Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it will only find a minimum spanning tree for one of the connected components.

It works as follows:

• create a tree containing a single vertex, chosen arbitrarily from the graph
• create a set containing all the edges in the graph
• loop until every edge in the set connects two vertices in the tree
  • remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree
  • add that edge to the tree