Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 20. Минимальные остовные деревья.
|
|
|
| РИСУНОК 20.12. АЛГОРИТМ КРУСКАЛА ПОСТРОЕНИЯ ДЕРЕВА MST Пусть задан список ребер графа в произвольной форме (левый список ребер). Первый шаг алгоритма Крускала заключается в их сортировке по их весам (правый список ребер). Затем мы производим просмотр ребер этого списка в порядке возрастания их весов, добавляя в дерево MST ребра, которые не создают в нем циклов. Сначала мы добавляем 5-3(самое короткое ребро), далее ребро 7-6 (слева), затем 0-2 (справа вверху) и 0-7 (справа, вторая диаграмма сверху). Ребро 0-1 со следующим по величине весом создает цикл и не принимается во внимание. Ребра, которые мы не включаем в дерево MST, показаны в отсортированном списке серым цветом. Затем мы добавляем ребро 4-3 (справа, третья диаграмма сверху). Далее мы отвергаем ребро 5-4, поскольку оно образует цикл, затем мы добавляем 7-4 (диаграмма справа внизу). Как только дерево MST будет готово, любое ребро с большим, чем у каждого ребра этого дерева весом, образует цикл и в силу этого обстоятельства игнорируется (алгоритм останавливается, когда в дерево MST будут включены V —\ ребер). В отсортированном списке эти ребра помечены звездочками. |
Часть 5. Алгоритмы на графах
Алгоритм Крускала прост в реализации, если для его построения используются базовые алгоритмические инструментальные средства, которые мы рассматривали в данной книге. В самом деле, мы можем использовать любую сортировку из описанных в части 3 для упорядочения ребер по весу и любой из алгоритмов решения задачи связности, рассмотренных в главе 1, для удаления тех из них, которые образуют циклы. Программа 20.8 представляет собой соответствующую реализацию функции построения дерева MST для АТД графа, которая в функциональном плане эквивалентна другим реализациям MST, рассмотренным в данной главе. Эта реализация не зависит от представления графа: она вызывает клиентскую программу GRAPH с целью получения вектора, в котором содержатся ребра графа, а затем на основе этого вектора строит дерево MST.
Обратите внимание на тот факт, что существуют два способа окончания работы алгоритма Крускала. Если мы найдем V- 1 ребер, то мы уже построили остовное дерево и можем остановиться. Если мы проверим все вершины и не найдем при этом V— 1 древесных ребер, это означает, что мы обнаружили, что граф не является связным, точно так же, как это делалось в главе 1.
Анализ времени выполнения алгоритма не представляет трудностей, ибо мы знаем время выполнения составляющих его операций АТД.
Программа 20.8. Алгоритм Крускала, обеспечивающий
построение дерева MST_______________________________
Эта реализация использует разработанные нами сортирующий АТД из главы 6 и АТД объединения-поиска из главы 4 для отыскания дерева MST, рассматривая ребра в порядке возрастания их весов и отбрасывая те ребра, которые образуют циклы, до тех пор, пока не будут обнаружены V-1 вершин, которые составляют остовное дерево.
Здесь не показан интерфейсный класс EdgePtr, который заключает в себе указатели на ребра, благодаря чему функция sort может сравнивать их, используя для этой цели перегрузку операции < в соответствии с изложенным в разделе 6.8, а также версия программы 20.2 с третьим аргументом спецификатора шаблона.
template < class Graph, class Edge, class EdgePtr>