
related topics 
{math, number, function} 
{line, north, south} 
{rate, high, increase} 
{math, energy, light} 
{style, bgcolor, rowspan} 

In computer science, Prim's algorithm is an algorithm that finds a minimum spanning tree for a connected 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. Prim's algorithm is an example of a greedy algorithm. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim–Jarník algorithm.
Contents
Description
The only spanning tree of the empty graph (with an empty vertex set) is again the empty graph. The following description assumes that this special case is handled separately.
The algorithm continuously increases the size of a tree, one edge at a time, starting with a tree consisting of a single vertex, until it spans all vertices.
 Input: A nonempty connected weighted graph with vertices V and edges E (the weights can be negative).
 Initialize: V_{new} = {x}, where x is an arbitrary node (starting point) from V, E_{new} = {}
 Repeat until V_{new} = V:
 Choose an edge (u, v) with minimal weight such that u is in V_{new} and v is not (if there are multiple edges with the same weight, any of them may be picked)
 Add v to V_{new}, and (u, v) to E_{new}
 Output: V_{new} and E_{new} describe a minimal spanning tree
Time complexity
A simple implementation using an adjacency matrix graph representation and searching an array of weights to find the minimum weight edge to add requires O(V^{2}) running time. Using a simple binary heap data structure and an adjacency list representation, Prim's algorithm can 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).
Full article ▸


related documents 
Paracompact space 
Fixed point combinator 
Multiplicative function 
Riemann mapping theorem 
Commutator subgroup 
Outer product 
Compactification (mathematics) 
Recursive descent parser 
Augmented Backus–Naur Form 
Open set 
Existential quantification 
Depthfirst search 
Jules Richard 
Base (topology) 
Gram–Schmidt process 
Generalized mean 
Poisson process 
Pigeonhole principle 
Definable real number 
Rank (linear algebra) 
Trie 
ML (programming language) 
Octal 
Boolean ring 
MerkleHellman 
Riesz representation theorem 
2 (number) 
Chain rule 
Delegation pattern 
Legendre polynomials 
