Prim's algorithm

Description

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected 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. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Algorithm

The algorithm may informally be described as performing the following steps:

  1. Select any vertex to be the first of the tree T.
  2. Consider which edge connects vertices in T to vertices outside T. Pick the edge with the minimum weight (if there are more than one, then choose any). Add this edge and vertex to T.
  3. Repeat step 2 until T contains every vertex of the graph.