Algorytm Kruskala
Z RNO-Wiki
m |
|||
| Linia 3: | Linia 3: | ||
Algorytm działa w czasie <var>m log(m) + n log<sup>*</sup> n</var>. | Algorytm działa w czasie <var>m log(m) + n log<sup>*</sup> n</var>. | ||
| + | Pierwszy składnik bierze się stąd, że algorytm sortuje wszystkie krawędzie według ich wag, a następnie dodaje do drzewa MST, które na początku jest zbiorem pustym kolejne krawędzie, zaczynając od najtańszych. Oczywiście algorytm pomija krawędzie, których dodanie utworzy cykl spośród krawędzi już wcześniej dodanych. Aby wykryć czy dodana krawędź tworzy cykl z dodanymi wcześniej, będziemy używać struktury [[UNION-FIND]] do łączenia zbiorów rozłącznych. | ||
<table width="100%"> | <table width="100%"> | ||
