Алгоритм Борувки

Следующий алгоритм вычисления дерева MTS, который мы будем рассматривать, так­же принадлежит к числу самых старых. Подобно алгоритму Крускала, мы строим дере­во MTS, добавляя ребра в развернутый лес поддеревьев MTS, но делаем это поэтапно, добавляя на каждом этапе несколько ребер в дерево MTS. На каждом этапе мы отыски­ваем наиболее короткое ребро, которое соединяет каждое поддерево MTS с некоторым другим поддеревом, затем включаем каждое такое ребро в дерево MTS.

И вновь разработанный нами в главе 1 АТД поиска-объединения позволяет получить эффективную реализацию. Для рассматриваемой задачи целесообразно расширить интер­фейс этого АТД, обеспечив доступность операции find для клиентских программ. Мы будем пользоваться этой функцией для того, чтобы присвоить индекс каждому поддереву с та­ким расчетом, чтобы можно было быстро определить, к какому поддереву принадлежит заданная вершина. Обладая такой возможностью, мы способны эффективно реализовать каждую операцию, необходимую для выполнения алгоритма Борувки.

Прежде всего, мы построим вектор, индексированный именами вершин, который для каждого поддерева MTS определяет ближайшего соседа. Затем на каждом ребре графа мы выполняем следующие операции:

■ Если соединяются две вершины одного и того же дерева, результат операции от­
брасывается.

■ В противном случае выполните проверку расстояний между вершинами двух бли­
жайших соседних деревьев, которые соединяет это ребро, и обновите их, если в
этом есть необходимость.

Глава 20. Минимальные остовные деревья

После такого просмотра всех ребер графа, век­тор ближайших соседних вершин содержит инфор­мацию, которая нам нужна для соединения поддере­вьев. Для каждого индекса вершины мы выполняем операцию union с целью ее соединения с ближайшей соседней вершиной. На следующей стадии мы от­брасываем все более длинные ребра, которые соединяют другие пары вершин в уже соединенных поддеревьях MTS. Рисунки 20.14 и 20.15 служат ил­люстрацией работы выбранного нами алгоритма.

Программа 20.9 представляет собой прямую ре­ализацию алгоритма Борувки. Следующие три глав­ных фактора делают эту реализацию эффективной:

■ Стоимость каждой операции find фактически
остается постоянной.

■ Каждый этап уменьшает число поддеревьев
MTS в лесе, по меньшей мере, в два раза.

■ На каждом этапе отбрасывается значительное
количество ребер.

Трудно дать точную количественную оценку всех этих факторов, в то же время нетрудно установить следующие границы.