![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм Борувки
Следующий алгоритм вычисления дерева MTS, который мы будем рассматривать, также принадлежит к числу самых старых. Подобно алгоритму Крускала, мы строим дерево MTS, добавляя ребра в развернутый лес поддеревьев MTS, но делаем это поэтапно, добавляя на каждом этапе несколько ребер в дерево MTS. На каждом этапе мы отыскиваем наиболее короткое ребро, которое соединяет каждое поддерево MTS с некоторым другим поддеревом, затем включаем каждое такое ребро в дерево MTS. И вновь разработанный нами в главе 1 АТД поиска-объединения позволяет получить эффективную реализацию. Для рассматриваемой задачи целесообразно расширить интерфейс этого АТД, обеспечив доступность операции find для клиентских программ. Мы будем пользоваться этой функцией для того, чтобы присвоить индекс каждому поддереву с таким расчетом, чтобы можно было быстро определить, к какому поддереву принадлежит заданная вершина. Обладая такой возможностью, мы способны эффективно реализовать каждую операцию, необходимую для выполнения алгоритма Борувки. Прежде всего, мы построим вектор, индексированный именами вершин, который для каждого поддерева MTS определяет ближайшего соседа. Затем на каждом ребре графа мы выполняем следующие операции: ■ Если соединяются две вершины одного и того же дерева, результат операции от ■ В противном случае выполните проверку расстояний между вершинами двух бли Глава 20. Минимальные остовные деревья
Программа 20.9 представляет собой прямую реализацию алгоритма Борувки. Следующие три главных фактора делают эту реализацию эффективной: ■ Стоимость каждой операции find фактически ■ Каждый этап уменьшает число поддеревьев ■ На каждом этапе отбрасывается значительное Трудно дать точную количественную оценку всех этих факторов, в то же время нетрудно установить следующие границы.
|