Алгоритм Краскала
В этом алгоритме для добавления к частично сформированному дереву выбирается абсолютно кратчайшее допустимое ребро, а не просто кратчайшее ребро между одним поддеревом и другим каким-либо поддеревом (как это предполагалось в приведенной выше операции).
Так как выбранное ребро является кратчайшим между некоторым поддеревом и каким-то другим поддеревом, то правило выбора в этом алгоритме представляет собой частный случай операции.Алгоритм имеет следующий вид:
Шаг 1. Начать с вполне несвязного графа T, содержащего n вершин.
Шаг 2. Упорядочить ребра графа G в порядке неубывания их весов.
Шаг 3. Начав с первого ребра в этом списке, добавлять ребра в графе T, соблюдая условие: такое добавление не должно приводить к появлению цикла в T.
Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в T не станет равным n-1. Получившееся дерево является кратчайшим остовом графа G.
При выполнении этого алгоритма может возникнуть такая ситуация, когда очередное кратчайшее ребро, выбранное из списка, построенного на шаге 2, будет соединять две вершины одного и того же поддерева. Добавлять это ребро к T нельзя, поскольку такое добавление приводит к появлению цикла в T. Поэтому на шаге 3, прежде чем добавлять ребро к графу Т, надо проверить, является ли оно допустимым в указанном выше смысле. Такую проверку можно выполнить более эффективно (путем осуществления одного сравнения с использование процедуры расстановки пометок из раздела 3.2), абсолютно так же, как это делается на шаге 2 алгоритма из раздела 3.2.