Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match_all(): Compilation failed: group name must start with a non-digit at offset 4 in /wiki/includes/MagicWord.php on line 717

Warning: Invalid argument supplied for foreach() in /wiki/includes/MagicWord.php on line 718

Warning: preg_replace(): Compilation failed: group name must start with a non-digit at offset 4 in /wiki/includes/MagicWord.php on line 722

Warning: preg_match_all(): Compilation failed: group name must start with a non-digit at offset 4 in /wiki/includes/MagicWord.php on line 717

Warning: Invalid argument supplied for foreach() in /wiki/includes/MagicWord.php on line 718

Warning: preg_replace(): Compilation failed: group name must start with a non-digit at offset 4 in /wiki/includes/MagicWord.php on line 722

Warning: Parameter 3 to renderAdsense() expected to be a reference, value given in /wiki/includes/parser/Parser.php on line 3470

Warning: preg_match_all(): Compilation failed: group name must start with a non-digit at offset 4 in /wiki/includes/MagicWord.php on line 717

Warning: Invalid argument supplied for foreach() in /wiki/includes/MagicWord.php on line 718

Warning: preg_replace(): Compilation failed: group name must start with a non-digit at offset 4 in /wiki/includes/MagicWord.php on line 722

Warning: preg_match_all(): Compilation failed: group name must start with a non-digit at offset 4 in /wiki/includes/MagicWord.php on line 717

Warning: Invalid argument supplied for foreach() in /wiki/includes/MagicWord.php on line 718

Warning: preg_replace(): Compilation failed: group name must start with a non-digit at offset 4 in /wiki/includes/MagicWord.php on line 722

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739

Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /wiki/includes/MagicWord.php on line 739
Algorytm Kruskala – RNO-Wiki

Algorytm Kruskala

Z RNO-Wiki
m
m
Linia 1: Linia 1:
 
[[Kategoria:Algorytmy grafowe]]
 
[[Kategoria:Algorytmy grafowe]]
Algorytm Kruskula znajduje minimalne drzewo spinające w grafie z wagami na krawędziach. Wagi mogą być właściwie dowolnymi liczbami.  
+
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 Kruskula w języku C++.
+
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 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.
+
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.

Wersja z 08:00, 28 lut 2008

Osobiste