Prim's algorithm

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 non-empty connected weighted graph with vertices V and edges E (the weights can be negative).
  • Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}
  • Repeat until Vnew = V:
    • Choose an edge (u, v) with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)
    • Add v to Vnew, and (u, v) to Enew
  • Output: Vnew and Enew 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(V2) 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
Depth-first 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
Merkle-Hellman
Riesz representation theorem
2 (number)
Chain rule
Delegation pattern
Legendre polynomials