Prim's algorithm

Summary

Prim's algorithm finds a minimum spanning tree of a connected graph with weighted edges. It grows a single tree from a start vertex, adding at each step the lightest edge that joins the tree to a vertex outside it. It is a greedy algorithm, and with a binary heap it runs in time $O(m \log n)$ on $n$ vertices and $m$ edges.