Motywacja

Podczas gdy Kruskal sortuje wszystkie krawędzie globalnie i używa struktury union-find, Prim utrzymuje jedno rozrastające się drzewo i wielokrotnie sięga po najbliższy wierzchołek spoza niego.

Dlaczego warto poznać Prima?

• Grafy gęste: Prim z odpowiednimi strukturami jest wydajny, gdy krawędzi jest dużo.
• Własność przekroju: to praktyczna ilustracja tego, dlaczego najtańsza krawędź wychodząca z aktualnego drzewa jest zawsze bezpieczna do dodania.
• Dwa spojrzenia na ten sam problem: porównanie Prima i Kruskala pogłębia zrozumienie minimalnych drzew rozpinających.

Ponieważ wszystkie MST grafu mają te same wagi krawędzi, Prim i Kruskal zawsze podają tę samą łączną wagę.