|
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 |
|