Реализация алгоритма Крускала

А теперь воспользуемся структурой данных Union-Find для реализации алгоритма Крускала. Сначала нужно отсортировать ребра по стоимости; эта операция вы- полняется за время 0(m log m). Так как каждая пара узлов соединяется максимум одним ребром, m < n2, а следовательно, общее время выполнения также равно 0(m log n).

После операции сортировки структура данных Union-Find используется для хранения информации о компонентах связности (V, T) при добавлении ребер. При рассмотрении каждого ребра e = (v, w) мы вычисляем Find(и) и Find(v) и проверяем результаты на равенство, чтобы узнать, принадлежат ли v и w разным компонентам. Если алгоритм решает включить ребро e в дерево T, операция Union(Find(и), Find(v)) объединяет две компоненты.

В процессе выполнения алгоритма Крускала выполняются не более 2m опера- ций Find и n - 1 операций Union. Используя либо (4.23) для реализации Union-Find на базе массива, либо (4.24) для реализации с указателями, можно заключить, что общее время реализации равно 0(m log n). (Хотя возможны и более эффективные реализации структуры Union-Find, они не улучшат время выполнения алгоритма Крускала, который содержит неизбежный фактор 0(m log n) из-за исходной сор- тировки ребер по стоимости.)

Подведем итог:

(4.25) Алгоритм Крускала может быть реализован для графа с n узлами и m ре- брами со временем выполнения 0(m log n).

4.7.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Реализация алгоритма Крускала:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ УДАЧИ
  3. АЛГОРИТМ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Глава 6. Реализация права
  13. 4.2. Реализация
  14. 4. Реализация прав по ипотеке
  15. 3.3. Дальнейшая реализация проекта
  16. РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ
  17. 10. Реализация заложенного имущества
  18. Механизм реализации личности