Prim's Minimum Spanning Tree

Algorithm Steps

1. Pick an arbitrary start vertex.
2. Choose the minimum-weight edge with one endpoint in the growing tree.
3. Add that edge and its new vertex to the tree.
4. Repeat until all vertices are included.

Pseudocode

1procedure PRIM(G)
2  choose any start vertex; T ← {start}
3  while |T| < |V| do
4    choose minimum weight edge (u, v) with exactly one endpoint in T
5    add v to T; add (u, v) to MST
6  end while
7end procedure