Глава 20. Минимальные остовные деревья. Если же граф не является связным, то версия алгоритма Крускала, основанная на ча­стичной сортировке

Если же граф не является связным, то версия алгоритма Крускала, основанная на ча­стичной сортировке, не дает никаких преимуществ, поскольку в этом случае необходи­мо проводить анализ всех ребер графа. Даже в случае связного графа самое длинное ребро может оказаться в дереве MST, так что любая реализация метода Крускала должна вы­полнять анализ всех ребер. Например, граф может состоять из плотных кластеров вер­шин, при этом все они соединены между собой короткими ребрами и только одна не вхо­дящая в кластер вершина соединена с какой-либо вершиной длинным ребром. Несмотря на возможность таких нетипичных вариантов, подход с применением частичной сорти­ровки, по-видимому, достоин нашего внимания, поскольку он обещает существенный выигрыш в производительности и не требует больших дополнительных затрат, а то и не требует их вовсе.

Здесь уместна краткая историческая справка, в некотором смысле она довольно по­учительна. Крускал предложил свой алгоритм в 1956 г., однако, опять-таки, соответству­ющие реализации АТД не подвергались подробному изучению в течение многих лет. В силу этого обстоятельства, рабочие характеристики реализаций, такие как версия программы 20.8 с очередями с приоритетами, не получили надлежащей оценки вплоть до семидеся­тых годов прошлого столетия. Другим интересным историческим фактом является то, что в статье Крускала упоминалась версия алгоритма Прима (см. упражнение 20.59), а Боровика ссылался в своей статье на оба эти подхода. Эффективная реализация метода Крускала на разреженных графах предшествовала реализации метода Прима для разреженных гра­фов в силу того, что абстрактными типами данных поиска-объединения (и сортировки) стали пользоваться раньше, чем абстрактными типами данных очереди с приоритетами. По существу, прогресс в современном состоянии алгоритма Крускала, равно как и в ре­ализации алгоритма Прима, обусловлен главным образом улучшением характеристик про­изводительности АТД. С другой стороны, применимость абстракции поиска-объединения к алгоритму Крускала и применимость абстракции очереди с приоритетами к алгоритму Прима стали для многих исследователей основной мотивацией для поиска более совер­шенных реализаций упомянутых выше АТД.