Algorytm Krasnala pozwala wyznaczyć minimalne drzewo rozpinające.
Jest to przykład algorytmu zachłannego, czyli wykonuje jakieś zagadnienie na pałę.
Czasem coś takiego daje rzeczywiście dobry wynik
Ale pokazywać nie będę z 3 powodów:
-nie trzea znać dowodu, aby przepchać zadanie H
-dowód nie jest bardzo potrzebny
-nie chce mi się i nie umiem(nie pamiętam) <== główny powód.
Do rzeczy. Mamy graf nieskierowany, z krawędziami ważonymi.
Po pierwsze sortujemy krawędzie wg. wag rosnąco.
Przyda nam się struktura zbiorów rozłącznych. W ten sposób będziemy sprawdzać, czy połączenie wierzchołków krawędzią
przyniesie nam jakieś korzyści. Załóżmy że jeśli 2 wierzchołki należą do tego samego zbioru, to są ze sobą połączone(krawędzią lub krawędziami), czyli istnieje droga od jednego do drugiego. Jeżeli krawędź połączy 2 zbiory wierzchołków to stają się one jednym zbiorem. jeżeli krawędź połączy 2 wierzchołki, które już są w tym samym zbiorze to jest ona nie potrzebna.
Ogólny algorytm:
1. sortujemy krawędzie wg. wag rosnąco
2. dla każdej krawędzi(od najmniejszej): // niech krawędź będzie z wierzchołka x do y
jeżeli naleza_do_tego_samego_zbioru(x,y) to odrzucamy krawędź
jeżeli nie to:
3. łączymy 2 zbiory: zbiór z wierzchołkiem x ze zbiorem z wierzchołkiem y, i zaznaczamy krawędź jako "potrzebną"
Graf złożony z wierzchołków i "potrzebnych" krawędzi to dokładnie najmniejsze drzewo rozpinające.
Najlepiej zaimplementować to z użyciem struktury zbiorów rozłącznych. opisana jest tutaj
