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