Быстрый алгоритм для минимальных остовных деревьев при ограничении длин ребер?

Предположим, что у вас есть ориентированный граф с неотрицательными целыми длинами ребер, которые находятся в диапазоне от 0 до U - 1 включительно. Каков самый быстрый алгоритм вычисления минимального остовного дерева этого графа? Мы все еще можем использовать существующие алгоритмы минимального остовного дерева, такие как алгоритм Крускаля O (m log n)) или алгоритм Prim (O (m + n log n)). Однако для случаев, когда U мало, я думаю, что это должно быть возможно сделать намного лучше.

Существуют ли какие-либо алгоритмы, конкурирующие с более традиционными алгоритмами MST, которые могут использовать тот факт, что длины кромок ограничены в каком-то диапазоне?

Ответы

Ответ 1

Фредман-Уиллард дал алгоритм O (m + n) для целых длин ребер на ОЗУ с единичной стоимостью.

Это, возможно, не так много улучшений: без ограничения длины ребер (т.е. длины - это непрозрачный тип данных, который поддерживает только сравнения), Chazelle дал алгоритм O (m alpha (m, n) + n) alpha - обратная функция Аккермана), а Каргер-Клейн-Тарьян дал рандомизированный алгоритм O (m + n).

Я не думаю, что идея Даррена приводит к алгоритму O (m + n + U) -time. Jarnik ( "Prim" ) не использует свою очередь приоритетов монотонно, поэтому ведра могут сканироваться несколько раз; Для Kruskal требуется структура данных с непересекающимися множествами, которая не может быть O (m + n).

Ответ 2

С целыми весами по краю вы можете использовать bucketing для достижения очереди приоритетов с наихудшей сложностью O(1), но дополнительной сложности O(U).

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

По существу вы настраиваете набор сжатых связанных списков, где каждый список индексируется стоимостью (integer!), связанной с этим ведром:

struct bucket_list
{
    _cost; // array[0..N-1] holding current cost for each item

    _head; // array[0..U-1] holding index of first item in each bucket

    _next; // array[0..N-1] where _next[i] is the next item 
           // in a list for the ith item

    _prev; // array[0..N-1] where _prev[i] is the last item 
           // in a list for the ith item
};

Эта структура основана на том факте, что каждый элемент может быть только в одном списке сразу.

Основываясь на этой структуре, вы можете достичь сложности худшего случая O(1) для этих операций:

push(item, cost); // push an item onto the head of the appropriate bucket list

_pop(item, cost); // _pop an item from (anywhere!) within a bucket list

update(item, old_cost, new_cost); // move an item between buckets by combining
                                  // push and _pop

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

Конечно, если U становится очень большим, дополнительная сложность пространства и возможность разреженного распределения элементов над ведрами могут сделать такой подход непривлекательным.