Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Prim's Algorithm

Graph Algorithm

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 Complexity
O(|E| log |V|) with a binary heap 2
Credited To
Vojtěch Jarník (1930), rediscovered by Robert C. Prim (1957) 2
Classification
Design Technique
Greedy 1
Time Complexity
Time Complexity (category)
Linearithmic Time -- O(n log n) 1
Connections

Credited To

Edsger W. Dijkstra, Pioneers
Source Wikipedia, Prim's algorithm
Joseph Kruskal, Pioneers
Source Wikipedia, Prim's algorithm

In Field

Algorithms and Complexity Theory, Fields

Uses Design Technique

Greedy Method, Concepts

Entity-backed identity for the design-technique enum value this algorithm already carries, resolved to a computing concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The design-technique fact itself stays on the algorithm unchanged.

Sources
1. Prim's Algorithm (Wikipedia)
  • Wikipedia infobox: time complexity linearithmic
    linearithmic
  • Wikipedia: design technique greedy
    greedy
View the Source
2. 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.
  • Credited To: Edsger W. Dijkstra, Lead paragraph
    later rediscovered and republished by Joseph Kruskal in 1956, Robert C. Prim in 1957, and Edsger W. Dijkstra in 1959
  • Credited To: Joseph Kruskal, Lead paragraph
    later rediscovered and republished by Joseph Kruskal in 1956, Robert C. Prim in 1957, and Edsger W. Dijkstra in 1959
View the Source
Wikidata: Prim's Algorithm
Wikidata Q470813, class allow-list match (w-wdresolver-0926)View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.