Реализация алгоритма Прима

Обсудим реализацию рассмотренных алгоритмов и попробуем получить хорошие оценки времени выполнения. Как вы увидите, алгоритмы Прима и Крускала с пра- вильным выбором структур данных могут быть реализованы с временем выпол- нения O(m log n).
В этом разделе показано, как это делается для алгоритма Прима, а обсуждение реализации алгоритма Крускала приводится в следующем разделе. Для алгоритма обратного удаления получить время выполнения, близкое к этому, непросто, поэтому этим алгоритмом мы заниматься не будем.

Хотя для алгоритма Прима доказательство правильности сильно отличалось от доказательства алгоритма Дейкстры для кратчайшего пути, реализации алго- ритмов Прима и Дейкстры почти идентичны. По аналогии с алгоритмом Дейк- стры для принятия решения о том, какой узел v добавить следующим в растущее множество S, следует хранить стоимости присоединения a(v) = mine=(м v).u^s ce для каждого узла v

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. Механизм реализации личности
  19. Статья 591. Реализация предмета залога