Algorytm Kruskala
Z RNO-Wiki
m |
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 | + | 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. |
| + | Sortowanie krawędzi odbywa się tylko raz. Algorytm rozpatruje bowiem 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, będziemy używać struktury [[UNION-FIND]] do łączenia zbiorów rozłącznych. | ||
| + | Poniżej znajduje się implementacja algorytmu Kruskula w języku C++. | ||
<table width="100%"> | <table width="100%"> | ||
<tr> | <tr> | ||
| Linia 80: | Linia 83: | ||
</tr> | </tr> | ||
</table> | </table> | ||
| + | |||
| + | Algorytm Kruskula ma pewną zaletę, której nie ma [[Algorytm Prima-Dijkstry]]. Otóż algorytm ten nie musi pamiętać struktury całego grafu. Jego złożoność pamięciowa zależy tylko i wyłącznie od liczby wierzchołków. Ponadto algorytm Kruskula jest algorytmem on-line. Potrafie przetwarzać krawędzie podczas ich wczytywania. | ||
