Niech będzie dany spójny graf nieskierowany o wierzchołkach V i krawędziach E. Ponadto z każdą krawędzią będzie związana tzw. waga, określna przez funkcję w, która oznaczają długość danej krawędzi. Jeżeli znajdziemy taki podzbiór T zawarty w zbiorze krawędzi E, który łączy wszystkie wierzchołki i taki, że suma wszystkich wag krawędzi wchodzących w skład T jest możliwie najmniejszy, to znajdziemy tzw. minimalne drzewo rozpinające. Oto minimalne drzewo rozpinające dla przykładowego grafu: Suma wag dla tego drzewa wynosi 10 Jest znanych kilka algorytmów tworzące takie drzewo. Wszystkie one wykorzystują tzw. metodę "zachłanną". Do rozrastającego się drzewa dodawane są "najlepsze" krawędzie, w tym przypadku o najmniejszej wadze.

Opis algorytmu Kruskala.
Opis algorytmu Prima

Komentarze