Prim's algorithm

Time complexity

The time complexity of Prim's algorithm depends on the data structures used for the graph and for ordering the edges by weight, which can be done using a priority queue. The following table shows the typical choices:

A simple implementation of Prim's, using an adjacency matrix or an adjacency list graph representation and linearly searching an array of weights to find the minimum weight edge to add, requires O(|V|²) running time. However, this running time can be greatly improved by using heaps to implement finding minimum weight edges in the algorithm's inner loop.

A first improved version uses a heap to store all edges of the input graph, ordered by their weight. This leads to an O(|E| log |E|) worst-case running time. But storing vertices instead of edges can improve it still further. The heap should order the vertices by the smallest edge-weight that connects them to any vertex in the partially constructed minimum spanning tree (MST) (or infinity if no such edge exists). Every time a vertex v is chosen and added to the MST, a decrease-key operation is performed on all vertices w outside the partial MST such that v is connected to w, setting the key to the minimum of its previous value and the edge cost of (v,w).

Using a simple binary heap data structure, Prim's algorithm can now be shown to run in time O(|E| log |V|) where |E| is the number of edges and |V| is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(|E| + |V| log |V|), which is asymptotically faster when the graph is dense enough that |E| is ω(|V|), and linear time when |E| is at least |V| log |V|. For graphs of even greater density (having at least |V|^c edges for some c > 1), Prim's algorithm can be made to run in linear time even more simply, by using a d-ary heap in place of a Fibonacci heap.

Proof of correctness

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 tree Y are connected.

Let Y₁ be a minimum spanning tree of graph P. If Y₁=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of tree Y that is not in tree Y₁, and V be the set of vertices connected by the edges added before edge e. Then one endpoint of edge e is in set V and the other is not. Since tree Y₁ is a spanning tree of graph P, there is a path in tree Y₁ joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in set V to one that is not in set V. Now, at the iteration when edge e was added to tree Y, edge f could also have been added and it would be added instead of edge e if its weight was less than e, and since edge f was not added, we conclude that

${\displaystyle w(f)\ge w(e).}$

Let tree Y₂ be the graph obtained by removing edge f from and adding edge e to tree Y₁. It is easy to show that tree Y₂ is connected, has the same number of edges as tree Y₁, and the total weights of its edges is not larger than that of tree Y₁, therefore it is also a minimum spanning tree of graph P and it contains edge e and all the edges added before it during the construction of set V. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph P that is identical to tree Y. This shows Y is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a larger subset X, which we assume to be the minimum.

Parallel algorithm

The main loop of Prim's algorithm is inherently sequential and thus not parallelizable. However, the inner loop, which determines the next edge of minimum weight that does not form a cycle, can be parallelized by dividing the vertices and edges between the available processors. The following pseudocode demonstrates this.

1. Assign each processor ${\displaystyle P_i}$ a set ${\displaystyle V_i}$ of consecutive vertices of length ${\displaystyle \frac{|V|}{|P|}}$.
2. Create C, E, F, and Q as in the sequential algorithm and divide C, E, as well as the graph between all processors such that each processor holds the incoming edges to its set of vertices. Let ${\displaystyle C_i}$, ${\displaystyle E_i}$ denote the parts of C, E stored on processor ${\displaystyle P_i}$.
3. Repeat the following steps until Q is empty:
   1. On every processor: find the vertex ${\displaystyle v_i}$ having the minimum value in ${\displaystyle C_i}$[${\displaystyle v_i}$] (local solution).
   2. Min-reduce the local solutions to find the vertex v having the minimum possible value of C[v] (global solution).
   3. Broadcast the selected node to every processor.
   4. Add v to F and, if E[v] is not the special flag value, also add E[v] to F.
   5. On every processor: update ${\displaystyle C_i}$ and ${\displaystyle E_i}$ as in the sequential algorithm.
4. Return F

This algorithm can generally be implemented on distributed machines as well as on shared memory machines. The running time is ${\displaystyle O(\frac{|V{|}^2}{|P|})+O(|V|\log |P|)}$, assuming that the reduce and broadcast operations can be performed in ${\displaystyle O(\log |P|)}$. A variant of Prim's algorithm for shared memory machines, in which Prim's sequential algorithm is being run in parallel, starting from different vertices, has also been explored. It should, however, be noted that more sophisticated algorithms exist to solve the distributed minimum spanning tree problem in a more efficient manner.