Złożoność obliczeniowa Można udowodnić, że każdym kolejnym wywołaniu liczba wierzchołków zmaleje co najmniej dwukrotnie – zatem wywołań tych będzie co najwyżej Złożoność obliczeniowa całości zależy więc od sposobu implementacji kroków 1, 2 algorytmu. Zastosowanie w implementacji struktury zbiorów rozłącznych pozwala osiągnąć złożoność na poziomie Można zmodyfikować go tak, aby osiągnąć złożoność – algorytm działa wtedy znacznie szybciej dla grafów rzadkich; dla grafów gęstych modyfikacja nie daje dużych zysków czasowych.
Zobacz też algorytm Kruskala algorytm Prima minimalne drzewo rozpinające
Przypisy
Linki zewnętrzne
Borůvki