A greedy algorithm for finding a minimum spanning tree that grows a single tree outward from a starting vertex, at each step adding the cheapest edge that connects the growing tree to a vertex not yet included.
Facts
Time ComplexityO(|E| log |V|) with a binary heap 1 Credited ToVojtěch Jarník (1930), rediscovered by Robert C. Prim (1957) 1 Classification
Design Technique Connections
Sources
1. Wikipedia, Prim's algorithm
Lead section
The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later rediscovered and republished by Joseph Kruskal in 1956, Robert C. Prim in 1957, and Edsger W. Dijkstra in 1959.
Time complexity
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.
entity record, description (design-technique)
A greedy algorithm for finding a minimum spanning tree that grows a single tree outward from a starting vertex, at each step adding the cheapest edge that connects the growing tree to a vertex not yet included.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.