Przygotowuję się do egzaminu końcowego z algorytmów i mam pytanie, które mam nadzieję, że możecie mi pomóc.
Biorąc pod uwagę nieukierunkowany wykres z wagami od 1 do 100, jak mogę znaleźć minimalne drzewo opinające drzewo w czasie liniowym?
Odpowiedzi:
0 dla odpowiedzi № 1Możesz użyć Algorytm Kruskala z rozłączny-zestaw i sortuj krawędzie za pomocą liczenie sortowania, ponieważ twoje ciężary są ograniczone.