In computer science, Prim's algorithm is a greedy 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. 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.
Other algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. However, these other algorithms can also find minimum spanning forests of disconnected graphs, while Prim's algorithm requires the graph to be connected.
Read more about Prim's Algorithm: Time Complexity, Example Run, Proof of Correctness
Famous quotes containing the word prim:
“José’s my first non-rat romance. Not that he’s my idea of the absolute finito. He’s too prim and cautious to be my absolute ideal, Now, if I could choose from anybody alive, I wouldn’t pick José. Nehru, maybe, or Albert Schweitzer. Or Leonard Bernstein.”
—George Axelrod (b. 1922)