In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected 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. 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 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959. Therefore, it is also sometimes called the Jarník's algorithm, Prim–Jarník algorithm, Prim–Dijkstra algorithm
or the DJP algorithm.

Other well-known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. 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 each connected component of the graph, it can also be used to find the minimum spanning forest. In terms of their asymptotic time complexity, these three algorithms are equally fast for sparse graphs, but slower than other more sophisticated algorithms.
However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.

Description 
The algorithm may informally be described as performing the following steps:

In more detail, it may be implemented following the pseudocode below.

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 in Q that all have equal weights, and the algorithm will automatically start a new tree in F when it completes a spanning tree of each connected component of the input graph. The algorithm may be modified to start with any particular vertex s by setting C[s] to be a number smaller than the other values of C (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 set Q is implemented: as a simple linked list or array of vertices, or as a more complicated priority queue data structure. This choice leads to differences in the time complexity of the algorithm. In general, a priority queue will be quicker at finding the vertex v with minimum cost, but will entail more expensive updates when the value of C[w] changes.

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|2) running time. However, this running time can be greatly improved further 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 Y1 be a minimum spanning tree of graph P. If Y1=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 Y1, 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 Y1 is a spanning tree of graph P, there is a path in tree Y1 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

Let tree Y2 be the graph obtained by removing edge f from and adding edge e to tree Y1.  It is easy to show that tree Y2 is connected, has the same number of edges as tree Y1, and the total weights of its edges is not larger than that of tree Y1, 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 smaller 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.

This algorithm can generally be implemented on distributed machines as well as on shared memory machines. The running time is , assuming that the reduce and broadcast operations can be performed in . 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.

See also 
Dijkstra's algorithm, a very similar algorithm for the shortest path problem
Greedoids offer a general way to understand the correctness of Prim's algorithm

References

External links 
 Prim's Algorithm progress on randomly distributed points

Graph algorithms
Spanning tree
Articles containing proofs
Articles containing video clips
Greedy algorithms
Articles with example pseudocode
프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 의 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우()에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 까지 떨어진다.

개요 
프림 알고리즘은 아래의 순서대로 작동한다:
 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
 그래프의 모든 변이 들어 있는 집합을 만든다.
 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.
알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다.

설명 
이 알고리즘은 한 꼭짓점에서 시작한다. 트리가 모든 꼭짓점을 포함할 때까지 계속된다.
 입력: 연결된 각 변에 가중치가 주어진 그래프 
 초기화: 로 놓는다. x는 V에 있는 임의의 꼭짓점이다. 로 놓는다.
  가 될 때까지 다음을 계속 수행한다:
 로부터 최소의 가중치를 갖는 변 (u,v)를 뽑아낸다. 단, 이때 u는 에 속해야 하고 v는 에 속하지 말아야 한다. (같은 가중치를 갖는 여러 개의 변이 존재할 경우에는, 임의의 것을 고른다.)
 v를 에 추가한다.(u,v)를 에 추가한다.
 결과: 알고리즘이 종료됐을 때 만들어진 트리 가 결과가 된다. 이것은 최소 비용 신장트리가 된다.

시간 복잡도 

인접 행렬과 최소 비용값들이 들어가 있는 배열 내에서 최소 비용값을 찾는 검색을 사용할 경우, 시간 복잡도는 가 된다. 이진 힙 자료 구조와 인접 리스트 표현을 사용한다면, 프림 알고리즘은  내에 수행된다는 것이 증명될 수 있다. 여기서 는 변의 개수이고, 는 꼭짓점의 개수이다. 약간 복잡한 자료 구조인 피보나치 힙을 사용한다면 로 시간 복잡도가 감소할 수 있다. 이 경우, 그래프가 조밀하여 가 일 땐, 상당히 빨라진다.

예제

정확성 증명 
프림 알고리즘으로 얻은 그래프가 신장트리임을 보이는 것과 최소비용임을 보이는 두 단계로 나눈다.

트리에 관한 정리에서 n개의 꼭짓점을 가진 연결된 그래프가 n-1개의 변을 가지면 트리라고 한다. 프림 알고리즘으로 얻은 그래프 P는 n개의 꼭짓점을 연결하고 있고 n-1개의 변을 가지므로 트리이며 모든 점 n개를 가지므로 신장트리이다.

P가 최소비용임은 수학적 강귀납법을 통해 다음 명제를 증명하여 보인다.

"프림 알고리즘 각 단계에서 얻는 그래프의 간선들을 원소로하는 집합을 포함한 최소비용 신장트리가 항상 존재한다"
 프림 알고리즘 첫 단계는 간선이 없다. 그러므로 간선들의 집합은 공집합이다. 그러므로 최소비용 신장트리가 무엇이든 간선들의 집합을 포함한다.
 프림 알고리즘의 1부터 n-2 단계까지에서 얻는 그래프의 간선들을 원소로하는 집합을 포함한 최소비용 신장트리가 존재한다고 가정하자.
 n-2 단계로 얻는 그래프는 Q이고 간선들의 집합 L을 포함하는 최소비용 신장트리를 T라고 하자. Q에서 아직 연결되지 않은 마지막 꼭짓점 E를 한점으로 하는 변 e를 그리면 P를 얻는다. 그러므로 P와 T는 L을 공통으로 포함하고 E를 연결하는 변만 차이가 있다. 이때 T는 최소비용 신장트리이고 P도 가중치가 가장 낮은 e를 그려서 얻으므로 T와 P는 비용이 동일하다. 그러므로 n-1 단계에서 얻는 그래프 P의 간선 집합을 포함하는 최소비용 신장트리 P 자신이 존재한다.

의사 코드

최소-힙(Min-Heap)

초기화 
입력 한 그래프, 변의 가중치를 반환하는 함수, 초기 꼭짓점.
처음에는 각 꼭짓점은 '아직 거치지 않은 꼭짓점들의 집합'(not yet seen set)에 속한다. 초기 꼭짓점을 정한다. 모든 꼭짓점들을 최소 힙에 두어서 최소 그래프의 최소 가중치를 기준으로 최소 힙에서 꼭짓점이 제거될 수 있게 해둔다.
 for each vertex in graph
    set min_distance of vertex to ∞
    set parent of vertex to null
    set minimum_adjacency_list of vertex to empty list
    set is_in_Q of vertex to true
 set distance of initial vertex to zero
 add to minimum-heap Q all vertices in graph.

용어 설명 
 "가장 가까운 꼭짓점" 은 Q[0]이다. latest_addtion이 된다.
 "경계"는 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 뒤 v와의 거리(distance) < ∞ 인 v이다.
 "안 보임"은 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 뒤 v와의 거리(distance) = ∞ 인 v이다.
최솟값 제거 함수가 널을 반환하면 while 루프를 빠져나간다. 인접 리스트를 설정해서 "방향이 있는 그래프"가 반환되게도 할 수는 있다.
 "시간 복잡도 : 루프에 대해서는 , 제거 함수에 대해서는 "
 while latest_addition = remove minimum in Q
     set is_in_Q of latest_addition to false
     add latest_addition to (minimum_adjacency_list of (parent of latest_addition))
     add (parent of latest_addition) to (minimum_adjacency_list of latest_addition)
 "시간 복잡도 : , 꼭짓점 개수의 평균"
     for each adjacent of latest_addition
     if (is_in_Q of adjacent) and (weight-function(latest_addition, adjacent) < min_distance of adjacent)
         set parent of adjacent to latest_addition
         set min_distance of adjacent to weight-function(latest_addition, adjacent)
 "시간 복잡도 : , 힙의 높이(height of heap)"
         update adjacent in Q, order by min_distance

참고 문헌 
 V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (in Czech)
 R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
 D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
 Thomas H. Cormen, Charles E. Leiserson, 로널드 라이베스트, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 23.2: The algorithms of Kruskal and Prim, pp. 567–574.

같이 보기 
 신장트리
 크루스칼 알고리즘

외부 링크 

트리 구조
그래프 알고리즘
에츠허르 데이크스트라