ff78d4ec

Алгоритм Краскала


  1. Упорядочить все ребра графа по возрастанию их весов.
  2. Применить алгоритм КомпСвяз-Итер (см. пункт "Подсчет количества компонент связности").

Замечание: Выполнение алгоритма Краскала можно завершить сразу же, как только в каркас будет добавлено (N-1)-е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).



Содержание раздела