В чём заключается алгоритм Крускала?

Алгоритм Крускала (Краскала) — это алгоритм построения минимального остовного дерева во взвешенном связном неориентированном графе. ru.wikipedia.org bigenc.ru

Суть алгоритма: в начале текущее множество рёбер устанавливается пустым. ru.wikipedia.org Затем, пока это возможно, проводится следующая операция: ru.wikipedia.org

1. Из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. ru.wikipedia.org
2. Когда таких рёбер больше нет, алгоритм завершён. ru.wikipedia.org
3. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса. ru.wikipedia.org

Алгоритм описан Джозефом Краскалом в 1956 году. ru.wikipedia.org