ПОЛНОСТЬЮ решенными. Итак, пусть Г; и Тj - два произвольных поддерева, полученных путем добавления ребер при построении SST. Если символ Ti использовать также для обозначения множества вершин данного поддерева, то Д, может быть определено как кратчайшее из расстояний между вершинами из Ti и вершинами из Tj, т. е.

ij--=шт [mm {с {Xi, Xj))], ij. (7.1)

Легко показать, что многократное применение нижеследующей операции приводит к построению SST графа.

Операция J: Для поддерева найти такое поддерево Tj*, чтобы А„* = min [А^,]. Пусть(Хз, Xj*) будет тем ребром, вес которого

соответствует величине Aj* в выражении (7.1). Тогда ребро {Xs,Xj*) принадлежит SST и может быть добавлено к другим ребрам частично сформированного SST.

Доказательство. Предположим, что на некотором этапе, например на к-м, ребра в построенных поддеревьях принадлежат окончательному SST, а ребро (х^, Xj*), выбранное в соответствии с приведенным выше условием, в SST не содержится. Поскольку поддерево Ts должно быть связано в конце концов согласно определению с некоторым другим поддеревом, то в SST должно существовать ребро (xi, Xj), такое, что Xi Т^, ъ Xj Т^. Удалив ребро {Xj, Xj) из SST, мы расщепим это дерево на две связные компоненты, а добавив ребро (х^. Xj*), получим новое дерево, более короткое, чем SST, что противоречит определению SST. Таким образом, ребро {Xg, Xj*) можно добавить к частично сформированному SST на к-ш этапе. Затем надо перейти к следующему этапу построения дерева. Нужно отметить, что результат не зависит от выбора поддерева Т^. Поскольку на начальном этапе (т. е. пока еще никакие ребра не выбраны) предположение о принадлежности ребер к SST автоматически выполнено, то многократное применение операции / даст в конце концов SST графа.

Многие методы, позволяющие строить SST графов, основываются на частных случаях описанной выше операции [40, 48, 41, 46, 17, 35, 26]. Первый из таких методов был предложен Кра-скалом [40].

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

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

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

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

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

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

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

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

3.2. Алгоритм Прима [48]

Этот алгоритм порождает SST посредством разрастания только одного поддерева, например Tg, содержаш;его больше одной вершины. Одиночные вершины рассматриваются как отдельные поддеревья. Поддерево Tg постепенно разрастается за счет присоединения ребер (Xi, Xj), где Xi Tg и Xj Tg] причем добавляемое ребро должно иметь наименьший вес Cij. Процесс продолжается до тех пор, пока число ребер в Tg не станет равным п - 1. Тогда поддерево Tg будет требуемым SST. Впервые такая частная форма операции / была предложена Примем [48], а эффективную технику ее реализации дали Дейкстра [17] и Кевин с Уитни [351.

Алгоритм начинает работу с присвоения каждой вершине Xj Т, пометки [aj, Р^], где a,j на каждом шаге есть ближайшая к Xf вершина из поддерева Tg, а - вес ребра (а^, Xj). На каждом шаге выполнения алгоритма вершина, например Xj*, с наименьшей пометкой Ру присоединяется к Tg посредством добавления ребра (aj*, Xj*). Поскольку к добавлена новая вершина Xj*, то, может быть, придется изменить пометки [а^, Р;] у некоторых вершин € (если, например, с (Xj, Xj*) меньше суш;ествующей пометки Bj) и после этого продолжить процесс. Такая процедура расстановки пометок очень похожа на ту, которая используется в задаче о кратчайшем пути при применении алгоритма Дейкстры (гл. 8, разд. 2.1).

Алгоритм имеет следующий вид:

Шаг 1. Пусть Tg = {х^, где Xg - произвольно выбранная вершина, и Ag = 0 (Ag является множеством ребер, входящих в SST).

Шаг 2. Для каждой вершины Xj Tg найти вершину aj 6 Tg, такую, что

с (aj, Xj) = min [с {хи Xj)\ = р^,

и приписать вершине Х] пометку [ос;, р;]. Если такой вершины aj нет, т. е. при Т (Xj) [\Tg = 0, приписать вершине Xj пометку [О, оо].