Prim's Algorithm

Tags

algorithm

Is an algorithm to find a minimum spanning tree from a graph \( G \) that can work without needing to sort the data like Kruskal's algorithm.

The algorithm is:

1. Choose a starting vertex.
2. Choosing a vertex (not already connected) nearest to the starting vertex and join.
3. Choose the vertex nearest to either of the previous joined vertices and add them to the tree.
4. Repeat step 3 until all vertices are connected.

Note: ordinarily in step 3 you'd have to be careful to adding a cycle but this is actually impossible. At each iteration we're adding an edge and a new node to an existing tree. To form a cycle we'd need to add an edge between two nodes already in the tree but seeing as we're only considering edges to nodes outside of the tree, there's no way to add a cycle.