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
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%">

Wersja z 07:49, 28 lut 2008

Osobiste