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

Шаг 1. Начать с вполне несвязного графа содержащего вершин.

Шаг 2. Упорядочить ребра графа в порядке неубывания их весов.

Шаг 3. Начав с первого ребра в этом списке, добавлять ребра в графе соблюдая условие: такое добавление не должно приводить к появлению цикла в

Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в не станет равным Получившееся дерево является SST графа

В этом алгоритме для добавления к частично сформированному дереву выбирается абсолютно кратчайшее допустимое ребро, а не просто кратчайшее ребро между одним поддеревом например и другим каким-либо поддеревом (как это предполагалось в операции ). Так как выбранное ребро является, очевидно, кратчайшим между некоторым поддеревом и каким-то другим поддеревом, то правило выбора в этом алгоритме представляет собой частный случай операции Однако при выполнении этого алгоритма может возникнуть такая ситуация, когда очередное кратчайшее ребро, выбранное из списка, построенного на шаге 2, будет соединять две вершины одного и того же поддерева. Добавлять это ребро к нельзя, поскольку такое добавление приводит к появлению цикла в Поэтому на шаге 3, прежде чем добавлять ребро к графу надо проверить, является ли оно допустимым в указанном выше смысле. Такую проверку можно выполнить более эффективно (путем осуществления одного сравнения с использованием процедуры расстановки пометок, описанной в разд. 2.2.1), абсолютно так же, как это делается на втором шаге алгоритма из разд. 2.2.2.

Больше всего времени необходимо для выполнения шага 2 рассматриваемого алгоритма. Для графа с ребрами нужно выполнить порядка операций, чтобы составить полный список ребер в порядке возрастания их весов. Однако полный список, вообще говоря, не требуется, так как весьма правдоподобно, что допустимых ребер, образующих SST, будут найдены после просмотра только «верхней» части списка, содержащей ребер. Отсюда немедленно следует, что процедура сортировки, используемая на шаге 2, должна быть процедурой многократного обращения, дающей корректное расположение первых ребер в конце цикла обращения. С помощью такой процедуры [34] кратчайшее ребро находится посредством одного обращения к шагу 2, затем осуществляется проверка ребра в соответствии с шагом 3; далее происходит возвращение к шагам 2 и 3 и т. д. Процесс продолжается до тех пор, пока после некоторого числа таких проб не будут отобраны ребер, дающие (при добавлении их к графа. В конце такого процесса будут эффективно рассортированы только ребер и при этом будут выполнены операций. Остальные ребер не потребуются.

Из сказанного выше следует, что, несмотря на сделанные усовершенствования, алгоритм Краскала лучше подходит для графов с небольшим числом ребер, чем для полных графов. У полных графов для этого случая Прим [48] и Дейкстра [17] предложили алгоритмы, более эффективно использующие особенности операции