Incomputer science,Prim's algorithm is agreedy algorithm that finds aminimum spanning tree for aweightedundirected graph. This means it finds a subset of theedges that forms atree that includes everyvertex, where the total weight of all theedges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
The algorithm was developed in 1930 byCzech mathematicianVojtěch Jarník[1] and later rediscovered and republished bycomputer scientistsRobert C. Prim in 1957[2] andEdsger W. Dijkstra in 1959.[3] Therefore, it is also sometimes called theJarník's algorithm,[4]Prim–Jarník algorithm,[5]Prim–Dijkstra algorithm[6]or theDJP algorithm.[7]
Other well-known algorithms for this problem includeKruskal's algorithm andBorůvka's algorithm.[8] These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs. However, running Prim's algorithm separately for eachconnected component of the graph, it can also be used to find the minimum spanning forest.[9] In terms of their asymptotictime complexity, these three algorithms are equally fast forsparse graphs, but slower than other more sophisticated algorithms.[7][6]However, for graphs that are sufficiently dense, Prim's algorithm can be made to run inlinear time, meeting or improving the time bounds for other algorithms.[10]
The algorithm may informally be described as performing the following steps:
In more detail, it may be implemented following thepseudocode below.
function Prim(vertices, edges)isforeach vertexin verticesdo cheapestCost[vertex] ← ∞ cheapestEdge[vertex] ← null explored ← empty set unexplored ← set containing all vertices startVertex ← any element of vertices cheapestCost[startVertex] ← 0while unexploredis not emptydo // Select vertex in unexplored with minimum cost currentVertex ← vertex in unexplored with minimum cheapestCost[vertex] unexplored.remove(currentVertex) explored.add(currentVertex)foreach edge (currentVertex, neighbor)in edgesdoif neighborin unexploredand weight(currentVertex, neighbor) < cheapestCost[neighbor] THEN cheapestCost[neighbor] ← weight(currentVertex, neighbor) cheapestEdge[neighbor] ← (currentVertex, neighbor) resultEdges ← empty listforeach vertexin verticesdoif cheapestEdge[vertex] ≠ nullTHEN resultEdges.append(cheapestEdge[vertex])return resultEdges
As described above, the starting vertex for the algorithm will be chosen arbitrarily, because the first iteration of the main loop of the algorithm will have a set of vertices inQ that all have equal weights, and the algorithm will automatically start a new tree inF when it completes a spanning tree of each connected component of the input graph. The algorithm may be modified to start with any particular vertexs by settingC[s] to be a number smaller than the other values ofC (for instance, zero), and it may be modified to only find a single spanning tree rather than an entire spanning forest (matching more closely the informal description) by stopping whenever it encounters another vertex flagged as having no associated edge.
Different variations of the algorithm differ from each other in how the setQ is implemented: as a simplelinked list orarray of vertices, or as a more complicatedpriority queue data structure. This choice leads to differences in thetime complexity of the algorithm. In general, a priority queue will be quicker at finding the vertexv with minimum cost, but will entail more expensive updates when the value ofC[w] changes.
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 apriority queue. The following table shows the typical choices:
| Minimum edge weight data structure | Time complexity (total) |
|---|---|
| adjacency matrix, searching | |
| binary heap andadjacency list | |
| Fibonacci heap andadjacency list |
A simple implementation of Prim's, using anadjacency matrix or anadjacency list graph representation and linearly searching an array of weights to find the minimum weight edge to add, requiresO(|V|2) running time. However, this running time can be greatly improved by usingheaps 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 constructedminimum spanning tree (MST) (or infinity if no such edge exists). Every time a vertexv is chosen and added to the MST, a decrease-key operation is performed on all verticesw outside the partial MST such thatv is connected tow, setting the key to the minimum of its previous value and the edge cost of (v,w).
Using a simplebinary heap data structure, Prim's algorithm can now be shown to run in timeO(|E| log |V|) where |E| is the number of edges and |V| is the number of vertices. Using a more sophisticatedFibonacci heap, this can be brought down toO(|E| + |V| log |V|), which isasymptotically faster when the graph isdense enough that |E| isω(|V|), andlinear time when |E| is at least |V| log |V|. For graphs of even greater density (having at least |V|c edges for somec > 1), Prim's algorithm can be made to run in linear time even more simply, by using ad-ary heap in place of a Fibonacci heap.[10][11]
LetP be a connected, weightedgraph. 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. SinceP is connected, there will always be a path to every vertex. The outputY of Prim's algorithm is atree, because the edge and vertex added to treeY are connected.
LetY1 be a minimum spanning tree of graph P. IfY1=Y thenY is a minimum spanning tree. Otherwise, lete be the first edge added during the construction of treeY that is not in treeY1, andV be the set of vertices connected by the edges added before edgee. Then one endpoint of edgee is in setV and the other is not. Since treeY1 is a spanning tree of graphP, there is a path in treeY1 joining the two endpoints. As one travels along the path, one must encounter an edgef joining a vertex in setV to one that is not in setV. Now, at the iteration when edgee was added to treeY, edgef could also have been added and it would be added instead of edgee if its weight was less thane, and since edgef was not added, we conclude that
Let treeY2 be the graph obtained by removing edgef from and adding edgee to treeY1. It is easy to show that treeY2 is connected, has the same number of edges as treeY1, and the total weights of its edges is not larger than that of treeY1, therefore it is also a minimum spanning tree of graphP and it contains edgee and all the edges added before it during the construction of setV. Repeat the steps above and we will eventually obtain a minimum spanning tree of graphP that is identical to treeY. This showsY is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a larger subsetX, which we assume to be the minimum.
The main loop of Prim's algorithm is inherently sequential and thus notparallelizable. However, theinner 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.[12] The followingpseudocode demonstrates this.
This algorithm can generally be implemented on distributed machines[12] as well as on shared memory machines.[13] The running time is, assuming that thereduce andbroadcast operations can be performed in.[12] 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.[14] It should, however, be noted that more sophisticated algorithms exist to solve thedistributed minimum spanning tree problem in a more efficient manner.
Media related toPrim's algorithm at Wikimedia Commons