Algorytm Kruskala
Z RNO-Wiki
m |
m |
||
| Linia 1: | Linia 1: | ||
[[Kategoria:Algorytmy grafowe]] | [[Kategoria:Algorytmy grafowe]] | ||
| − | Algorytm | + | Algorytm Kruskala znajduje minimalne drzewo spinające w grafie z wagami na krawędziach. Wagi mogą być właściwie dowolnymi liczbami. |
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>. | ||
| Linia 7: | Linia 7: | ||
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. | 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 | + | Poniżej znajduje się implementacja algorytmu Kruskala w języku C++. |
<table width="100%"> | <table width="100%"> | ||
<tr> | <tr> | ||
| Linia 84: | Linia 84: | ||
</table> | </table> | ||
| − | Algorytm | + | Algorytm Kruskala 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 Kruskala jest algorytmem on-line. Potrafi przetwarzać krawędzie podczas ich wczytywania. |
