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.
Dany jest spójny graf nieskierowany:
Po posortowaniu krawędzi wg. wag otrzymamy:
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.
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:
Po posortowaniu krawędzi wg. wag otrzymamy:
- Krawędź ae=1
- Krawędź af=2
- Krawędź bc=2
- Krawędź be=2
- Krawędź de=3
- Krawędź ab=4
- Krawędź fd=6
- Krawędź ef=7
- Krawędź cd=8
Suma wag krawędzi wchodzących w skład drzewa wynosi 10.
Zobacz też: Algorytm Prima.
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Dawid Fatyga | Ruby | .rb | .rb | ***** / 45 |
Poprawiony: 16 sierpnia 2012 20:25
Zacząłem używać tej strony jak wiki nie wiedząc za bardzo co to jest algorytm kruskala.
Jedynie wy macie to wytłumaczone na grafach nigdzie nie mogłem znaleźć nic podobnego