Быстродействующие реализации метода Крускала построения минимального остова графа

Аннотация

Задача построения минимального остова взвешенного графа относится к числу фундаментальных. Применение минимального остова графа обычно связывают с выполнением оптимальной по стоимости (весу) коммуникации узлов дискретных систем. Два базовых метода построения минимального остова графа были известны до появления современных компьютеров. Основным направлением совершенствования методов стало уменьшение вычислительной сложности. Этому способствовали изобретения в области вычислительных структур. В предыдущей работе авторов дан подробный анализ наиболее совершенной реализации метода Прима. В конкурирующем методе Крускала велика вычислительная сложность первого этапа — этапа упорядочения ребер графа по возрастанию веса. Она и определяет общую сложность. В настоящей статье исследован эффект построения специальных структур данных для первого этапа метода. Изменен статус метода Крускала, который становится быстрее метода Прима. В трех предлагаемых реализациях метода Крускала использована идея частичного упорядочения набора ребер. В первой из них взята слабая пирамида. Число сравнений ребер при ее построении минимально. Среднее число ребер, извлекаемых из пирамиды для построения остова, L ≈ V (0,333 log2 V + 0,45); логарифм двоичный. Среднее время построения остова стало меньше, но лучшим по-прежнему является метод Прима. Так называемая d-арная пирамида прежде не использовалась в методе Крускала. В специальной ее реализации сокращено не только среднее число основных действий, но и число вспомогательных. Вычислительная сложность построения пирамиды оказалась наименьшей при d > 4. В формуле средних затрат времени построения остова первое слагаемое соответствует построению пирамиды, второе — извлечению из нее L ребер, третье — проверке и включению ребер в остов, машинозависимые коэффициенты определяются экспериментально. Эта реализация быстрее метода Прима за исключением графов малой плотности. На первом этапе новой реализации метода Крускала для быстрого упорядочения ребер возможно использование системы цепных списков (стеков). За один просмотр описания графа строятся списки ребер. Каждый список включает ребра равного веса. Списки используются в порядке возрастания веса ребер, пока не будет построен остов. Эта реализация значительно быстрее метода Прима. Испытания новых реализаций метода проведены на графах, случайных (псевдослучайных) по составу и весу ребер. В статье также представлены коды реализаций.