algorytm.org

Algorytm Kruskala

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Kruskala
Ocena użytkowników:***** / 76
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 09 sierpnia 2005 21:56

Zrozumienie algorytmu wymaga znajomości pojęć grafu oraz minimalnego drzewa rozpinającego
Jest to algorytm oparty o metodę zachłanną.
Algorytm polega na łączeniu wielu poddrzew w jedno za pomocą krawędzi o najmniejszej wadze. W rezultacie powstałe drzewo będzie minimalne. Na początek należy posortować wszystkie krawędzie w porządku niemalejącym. Po tej czynności można przystąpić do tworzenia drzewa. Proces ten nazywa się rozrastaniem lasu drzew. Wybieramy krawędzie o najmniejszej wadze i jeśli wybrana krawędź należy do dwóch różnych drzew należy je scalić (dodać do lasu). Krawędzie wybieramy tak długo, aż wszystkie wierzchołki nie będą należały do jednego drzewa.

przykład:

Dany jest spójny graf nieskierowany:
algorytm Kruskala

Po posortowaniu krawędzi wg. wag otrzymamy:
  1. Krawędź ae=1
  2. Krawędź af=2
  3. Krawędź bc=2
  4. Krawędź be=2
  5. Krawędź de=3
  6. Krawędź ab=4
  7. Krawędź fd=6
  8. Krawędź ef=7
  9. Krawędź cd=8
algorytm Kruskala - krok 1 algorytm Kruskala - krok 2
algorytm Kruskala - krok 3 algorytm Kruskala - krok 4 algorytm Kruskala - krok 5

Wszystkie wierzchołki należą do jednego drzewa- minimalnego drzewa rozpinającego.
Suma wag krawędzi wchodzących w skład drzewa wynosi 10.
Zobacz też: Algorytm Prima.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Dawid FatygaRuby
.rb
.rb
***** / 44
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 16 sierpnia 2012 20:25
Komentarze
photo
-15 # santiago 2010-05-31 00:52
byłoby miło gdyby ktoś najpierw napisał na początku tekstu jaki jest cel zastosowania algorytmu.
Zacząłem używać tej strony jak wiki nie wiedząc za bardzo co to jest algorytm kruskala.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # patrz na początek art. 2010-06-25 11:18
Zrozumienie algorytmu wymaga znajomości pojęć grafu oraz minimalnego drzewa rozpinającego
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # fiaccik 2011-01-11 20:27
A co jeśli nie będzie połączeń de i df? Wierzchołek d połączy z drzewem, ale też doda wszystkie krawędzie po drodze.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # RadiX 2011-01-11 22:49
To jest algorytm szukania minimalnego drzewa rozpinającego. Przeczytałbyś co ten algorytm wykonuje i jak działa i sam byś do tego doszedł. Nice
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # LeLo 2011-01-13 18:00
Dzięki
Jedynie wy macie to wytłumaczone na grafach nigdzie nie mogłem znaleźć nic podobnego
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Marko 2011-12-04 12:56
dobra robota, przystępnie wytłumaczone zagadnienie, a nie niepotrzebne lanie wody tak jak na innych stronach!! dzięki
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # Student_pwr 2012-04-23 00:33
Nie polecam pisaniu programu w oparciu tylko o to, bo nie ma tutaj opisanego przypadku cyklu i jego omijania, wiec mozna sie przejechac.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # ZHTK 2012-06-12 16:23
Może podasz jakiś przyklad? Wydaje mi się że to rozwiązuje problem: "jeśli wybrana krawędź należy do dwóch różnych drzew należy je scalić" - sprawdzamy przy pomocy find-union, tak?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz