Jak to działa?

Dla każdego wierzchołka przechowuj wartość logiczną inTree. Rozpocznij od drzewa zawierającego tylko wierzchołek 0. Granicę tworzą wszystkie krawędzie, które mają dokładnie jeden koniec w drzewie; nazywamy je krawędziami przekraczającymi.

Proces krok po kroku:

1. Spośród wszystkich krawędzi przekraczających wybierz tę o najmniejszej wadze.
2. Dodaj jej zewnętrzny koniec do drzewa i dodaj jej wagę do sumy.
3. Powtarzaj, aż drzewo będzie zawierać wszystkie n wierzchołków (wymaga to n - 1 krawędzi).

Jeśli w pewnym momencie nie ma krawędzi przekraczających, a poza drzewem nadal pozostają wierzchołki, graf jest niespójny.

Przykład z krawędziami [0,1,1, 1,2,2, 2,3,3, 0,3,4]: zaczynając od 0, wybierz 0-1(1), następnie 1-2(2), a potem 2-3(3); suma wynosi 6.