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: 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_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
Algorytm Kruskala – RNO-Wiki

Algorytm Kruskala

Z RNO-Wiki
m
m (Wycofano edycję użytkownika Quentinscott (dyskusja). Autor przywróconej wersji to Rno.)
 
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 zaczyna od pustego drzewa i zachłannie dodaje do niego kolejne krawędzie. Zachłanność polega na wybieraniu krawędzi o najmniejszych wagach. W tym celu algorytm najpierw sortuje wszystkie krawędzie po ich wagach, a następnie próbuje je dodawać do drzewa, pomijając oczywiście te krawędzie, które utworzą cykl. Do tego właśnie algorytm wykorzystuje strukturę [[UNION FIND]].
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.
+
Algorytm ma złożoność czasową <var>m log(m) + n log<sup>*</sup> n</var>.
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++.
+
Poniżej znajduje się implementacja algorytmu Kruskala w języku C++.
 
<table width="100%">
 
<table width="100%">
 
<tr>
 
<tr>
Linia 15: Linia 13:
 
using namespace std;
 
using namespace std;
 
/*
 
/*
Rafał Nowak
+
Rafał Nowak ,  www.rafalnowak.pl
2007.01.05
+
2008.02.27
 
*/
 
*/
 
int tab[7000], ile[7000]; // 7000 - to liczba wszystkich elementów
 
int tab[7000], ile[7000]; // 7000 - to liczba wszystkich elementów
  
int Find(int a) { return (tab[a]==a) ? a : (tab[a] = fa); }
+
int Find(int a) { return (tab[a]==a) ? a : (tab[a] = Find(tab[a])); }
 
bool Union(int a, int b)
 
bool Union(int a, int b)
 
{
 
{
Linia 84: Linia 82:
 
</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.
+
<strike>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.</strike>

Aktualna wersja na dzień 21:06, 21 cze 2011

Osobiste