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.
Oto przykład:
Dany jest spójny graf nieskierowany:

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

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.

Komentarze