Prim's algorithm

---

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.

• 1 Description
• 2 Time complexity
• 3 Example
• 4 Proof of correctness
• 5 References
• 6 External links

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: 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²) 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 ▸