Introduction

Добро пожаловать в серию Алгоритмы на графах! Минимальное остовное дерево (MST) соединяет все вершины взвешенного графа с использованием минимально возможного общего веса ребер и без циклов.

Алгоритм Краскала строит MST жадным способом: он сортирует ребра от самых дешевых до самых дорогих и добавляет каждое из них, пока оно не создает цикл. Хитрость для быстрого обнаружения циклов заключается в структуре данных под названием система непересекающихся множеств (union-find) (также известная как disjoint-set).

Граф является неориентированным и взвешенным, заданным как n (вершины от 0 до n - 1) и edges, плоский массив троек [u0, v0, w0, ...] для неориентированного ребра u - v весом w.

Давайте начнем!