Prim konstruiert einen minimalen Spannbaum, indem er von einem Startknoten aus wiederholt die billigste Kante zur noch nicht erreichten Knotenmenge wählt.
Er ähnelt Dijkstra, optimiert aber Baumkosten statt Pfaddistanzen.