Алгоритм Prim, оптимизированный для известных весов ребер?

Question

Как вы можете изменить алгоритм prim в случае, когда вы уже знаете минимальное значение любого заданного веса? Например, если граф состоит из весов ребер 0 и 1, как вы можете быстрее выполнить алгоритм prim?

Answer 1

Первая стратегия, похоже, улучшает приоритетную очередь, чтобы использовать ваши данные. Если вы знаете, что веса являются дискретными значениями, меньшими, чем некоторые C, вы можете заменить обычно используемую двоичную кучу на кучу рексикса. Таким образом, вы можете легко получить такую ​​же алгоритмическую сложность, как с гораздо более сложной задачей для кучи Фибоначчи или, возможно, даже лучше. Алгоритм Дейкстры использует те структуры и те же данные, и вот подробное объяснение того, как реализовать базисное кучи для него:

http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/spalgs/radixheap.txt

Пример кода radixheap.cpp можно найти здесь:

http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/spalgs/spalgs.html

Вы можете просто применить одну и ту же структуру данных к алгоритму Прима, поскольку этот текст объясняет алгоритм Дейкстры, чтобы получить сложность O (m + n log C), где m - ребра, n - вершины, а C - максимальный вес края. Если ваши веса кромки - это только малые целые числа, это действительно очень хорошо.

Чтобы обобщить идею кучи оснований, элементы помещаются в ведра в соответствии с их приоритетом (который должен быть целым). Диапазон значений, покрываемых ведром N, примерно равен 2^N, поэтому поиск правого ведра пропорционален журналу наибольшего возможного числа. При извлечении элемента с наименьшим приоритетом элементы иногда перераспределяются на более низкие ведра, которые амортизируются, а также работают с логарифмической сложностью.

Если вы имели в виду, что веса ребер являются произвольными числами с плавающей запятой между 0 и 1, это не позволяет оптимизировать. Очевидно, любой граф может быть преобразован путем деления всех весов по краю на максимальный вес края, делая их все между 0 и 1. Это преобразование не может привести к тому, что алгоритм Prim будет работать быстрее. Вы можете преобразовать все ребра, добавив одинаковое число ко всем из них или умножив их на одинаковое положительное число, не изменяя результат вообще.