Алгоритм Краскала
- Упорядочить все ребра графа по возрастанию их весов.
- Применить алгоритм КомпСвяз-Итер (см. пункт "Подсчет количества компонент связности").
Замечание: Выполнение алгоритма Краскала можно завершить сразу же, как только в каркас будет добавлено (N-1)-е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).
