Wprowadzenie

Witaj ponownie w serii Algorytmy grafowe! Minimalne drzewo rozpinające (MST) łączy wszystkie wierzchołki grafu ważonego, wykorzystując najmniejszą możliwą sumę wag krawędzi i nie zawierając cykli.

Algorytm Kruskala buduje MST zachłannie: sortuje krawędzie od najtańszej do najdroższej i dodaje każdą z nich, o ile nie tworzy ona cyklu. Szybkie wykrywanie cykli umożliwia struktura danych o nazwie union-find (znana również jako zbiór rozłączny).

Graf jest nieskierowany i ważony, podany jako n (wierzchołki od 0 do n - 1) oraz edges, płaska tablica trójek [u0, v0, w0, ...] reprezentujących nieskierowaną krawędź u - v o wadze w.

Zaczynajmy!