Algorytmy i struktury danych · Senior · Pytanie 5 z 75
Czym różnią się algorytmy Prima i Kruskala?
- ✓Poprawna odpowiedź: Prim rozrasta jedno drzewo od wierzchołka; Kruskal łączy lasy najtańszymi krawędziami
- 2Prim szuka najkrótszych ścieżek; Kruskal drzew rozpinających
- 3Prim potrzebuje posortowanych krawędzi; Kruskal kolejki priorytetowej wierzchołków
Wyjaśnienie
Oba wyznaczają minimalne drzewo rozpinające. Prim dodaje najtańszą krawędź wychodzącą z bieżącego drzewa (kopiec krawędzi); Kruskal sortuje wszystkie krawędzie i przez union-find pomija cykle. Kruskal jest naturalny dla rzadkich list krawędzi, Prim dla gęstych grafów.