Main Page | See live article | Alphabetical index

# Prim's algorithm

Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted 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. The algorithm was conceived by computer scientist Robert Prim in 1957.

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

Prim's algorithm can be shown to run in time which is O (m + n log n) where m is the number of edges and n is the number of vertices.

## Proof

Let P be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Prim's algorithm is a tree, because the edge and vertex added to Y are connected to other vertices and edges of Y and at no iteration is a circuit created since each edge added connects two vertices in two disconnected sets. Also, Y includes all vertices from P because Y is a tree with n vertices, same as P. Therefore, Y is a spanning tree for P.

Let Y1 be any minimal spanning tree for P. If Y = Y1, then the proof is complete. If not, there is an edge in Y that is not in Y1. Let e be the first edge that was added when Y was constructed. Let V be the set of vertices of Y - e. Then one endpoint of e is in Y and another is not. Since Y1 is a spanning tree of P, there is a path in Y1 joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in V to one that is not in V. Now, at the iteration when e was added to Y, f could also have been added and it would be added instead of e if its weight was less than e. Since f was not added, we conclude that w(f) >= w(e).

Let Y2 be the tree obtained by removing f and adding e from Y1. It shows that Y2 is a tree that is more common with Y than with Y1. If Y2 equals Y, QED. If not, we can find a tree, Y3 with one more edge in common with Y than Y2 and so forth. Continuing this way produces a tree that is more in common with Y than with the preceding tree. Since there are finite number of edges in Y, the sequence is finite, so there will eventually be a tree, Yh, which is identical to Y. This shows Y is a minimal spanning tree.

Other algorithms for this problem include Kruskal's algorithm, and Boruvka's algorithm.