Предположим, что все веса ребер в графе являются целыми числами в диапазоне от 1 до |V|. Как быстро вы сможете заставить работать алгоритм Прима? Что, если веса ребер представляют собой целые числа в диапазоне от 1 до W для некоторой константы W?
Думаю, поскольку алгоритм Прима основан на реализации min-heap, знание весов ребер не поможет ускорить процедуру. Это правильно?
С этим ограничением вы можете реализовать кучу, которая использует O(V) / O(W) пространства соответственно, но имеет O(1) операций вставки и O(1) извлечения-мин. На самом деле вы можете получить O(1) за все операции, необходимые для алгоритма Прима. Поскольку временная сложность кучи влияет на сложность основного алгоритма, вы можете добиться большего успеха, чем универсальная реализация по умолчанию.
Я думаю, что основная идея решения этой проблемы заключается в том, чтобы помнить, что W является константой, поэтому, если вы представляете свою приоритетную очередь как некоторую структуру, размер которой ограничен W, весь список на каждой итерации не изменит временную сложность вашего алгоритма...
Например, если вы представляете свою приоритетную очередь в виде массива T с W + 1 позициями, имеющего связанный список вершин в каждой позиции, так что T[i ] — это список со всеми вершинами, имеющими приоритет, равный i, и использующий T[W + 1] для хранения вершин с приоритетом, равным бесконечности, вы возьмет
O(V) для построения очереди с приоритетом (просто вставьте все вершины в список T[W+1])
O(W), чтобы извлечь минимальный элемент (просто перемещайтесь по T в поисках первой непустой позиции)
O(1) для уменьшения ключа (если вершина v имела ключ, равный i, и он был обновлен до j , просто удалите v из списка T[i] и вставьте в первую позицию списка T[j]).
Таким образом, это даст вам сложность O(VW + E) вместо O(V logV + E).
(Конечно, это не сработает, если диапазон будет от 1 до V, потому что V^2 + E больше, чем V \logV + E).
Псевдокод для реализации Prim с небинарной кучей можно найти в Cormen, Introduction to Algorithms, 3rd edition.
Зная диапазон от 1 до k, мы можем создать массив размером k и пройтись по списку, добавляя ребра к соответствующему весу. Это, по характеру его хранения, означает, что ребра сортируются по весу. Это будет O(n+m) времени.
Опираясь на псевдокод алгоритма Прима в Cormen, мы можем проанализировать его сложность и получить результат O(nlog{n} + mlog{n}) = O((n+m)log{n}) времени (Cormen, стр. 636). В частности, шаг 7 и шаг 11 вносят элемент log{n}, который повторяется в цикле n и m. Цикл n log{n} происходит из операции EXTRACT-MIN, а цикл m log{n} - из операции "неявного DECREASE-KEY". Оба могут быть заменены нашим массивом веса ребер, циклом O (k). Таким образом, с нашим модифицированным алгоритмом Прима у нас будет алгоритм O (nk + mk) = O (k (n + m)).
