Dany jest graf ważony G(V, E, w), gdzie V - zbiór wierzchołków, E - zbiór krawędzi, w - funkcja przypisująca krawędzi Ei wagę (liczbę rzeczywistą lub całkowitą).
Minimalnym drzewem rozpinającym nazywamy drzewo rozpinające, dla którego suma wag
\[\sum_{e\in E} w(e) \]

jest najmniejsza z możliwych. Dla niektórych grafów może wskazać wiele drzew rozpinających spełniających tę własność.
Istnieją dwa bardzo szybkie alogrytmy o złożoności O(n) znajdujące dla zadanego grafu minimalne drzewo rozpinające. Są to: Istnieje jeszcze jeden algorytm do wyznaczenia minimalnego drzewa rozpinającego, który jest w praktyce połączenieniem algorytmu Prima i Kruskala, jest to:
  • algorytm Sollina
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.