Алгоритма Краскала.
Определение
Алгоритм Краскала — это алгоритм для нахождения минимального остовного дерева (MST) во взвешенном связном графе. В отличие от алгоритма Прима, который оперирует с вершинами, алгоритм Краскала оперирует с ребрами графа. Он начинает с самого маленького ребра и постепенно добавляет ребра с наименьшими весами, при условии что они не образуют циклы, пока не будет построено дерево, содержащее все вершины исходного графа.
- Инициализация: Создайте набор всех ребер графа.
- Сортировка ребер: Отсортируйте все ребра графа в порядке возрастания весов.
- Итерация по ребрам: Переберите отсортированные ребра.
Для каждой из вершин создаётся её единичное подмножество. При рассмотрении ребра, берём номера вершин (соответственно их подмножеств), выбираем номер минимального подмножества из этих 2, заносим вторую.
Аналогичную операцию проводим, если ребро соединяет не просто 2 единичных подмножества, а уже более крупные подмножества, состоящие из нескольких вершин. (сливаем, номер берем минимальный)
Ребро образует цикл, если соединяет 2 вершины, которые уже принадлежат одному подмножеству, такие ребра пропускаем.
- Повторение: алгоритм повторяется пока все вершины не будут принадлежать одному подмножеству
- Завершение: Когда MST содержит все вершины из исходного графа, алгоритм завершается.
