График (положительный вес) с MST Если какое-то ребро, e изменено на новое значение, то лучший способ обновить MST без его полной переделки. Я думаю, что это можно сделать в линейном времени. Кроме того, мне кажется, что мне нужен другой алгоритм, основанный на том, является ли 1) e уже частью MST и 2) является ли новый край, e больше или меньше исходногоОбновление минимального связующего дерева с модификацией края
Мое решение O (n) основан на предположении, что перед тем, как вы начнете изменять границы, вы должны найти MST (не указывается с графиком). Для этого вы можете использовать алгоритм Kruskal, который работает в O (n log n), а в качестве побочного эффекта создается отсортированный список ребер. В его стоимости преобладает сортировка, поэтому, когда вы изменяете вес края, вы можете удалить его из отсортированного списка в O (log n) и вставить его обратно с новым значением, также в O (log n) и, наконец, вызвать Kruskal алгоритм снова, который теперь работает в линейном времени, потому что ребра сортируются.
Это линейное решение по вашему желанию, но похоже, что это можно сделать быстрее.
Есть 4 случая:
Край находится в MST и вы уменьшая значение края:
Текущий MST по-прежнему MST
Край не в MST и вы убывающий значение кромки:
Добавьте этот край к MST. Теперь у вас ровно 1 цикл.
На основе cycle property в MST вам необходимо найти и удалить край с максимальным значением, которое находится в этом цикле. Вы можете сделать это с помощью dfs или bfs. Сложность O (n).
Край в MST, и вы увеличивая его значение края:
Снимите этот край от MST. Теперь у вас есть 2 подключенных компонента, которые должны быть подключены. Вы можете рассчитать оба компонента в O (n) (bfs или dfs). Вам нужно найти край с наименьшим значением, который соединяет эти компоненты. Итерируйте по краям в порядке возрастания по их значению. Сложность O (n).
Край не в MST и вы увеличивая его значение края:
Текущий MST по-прежнему MST
CASE 3. IS NOT O (N). для повторения по краям в порядке возрастания. нам нужно их сортировать. существуют O (n^2) ребра. даже если мы берем отсортированные ребра, которые мы вычислили во время создания mst, все равно придется пройти через эти (все в худшем случае) края. –
Это может быть O (n). 1. Удалите край, вес которого был увеличен, и следите за двумя узлами, которые были связаны этим ребром 2. Запустите bfs/dfs, начиная с этих двух узлов, которые теперь находятся в двух непересекающихся множествах. Вы должны каким-то образом хэшировать посещенные вершины, чтобы вы могли получить к ним доступ в O (1). Я бы создал два hashtables, по одному для каждого непересекающегося множества. 3. Проденьте все ребра в E-E ', где G = (V, E) и MST = (V, E'). Если любое ребро содержит 1 узел из каждой хэш-таблицы, оно соединяет два непересекающихся множества. Ведите переменную min, чтобы определить, к какому ребру подключены два набора и имеет самый низкий вес. O (E) – Olshansk
Olshansk, O (E) - O (n^2), как указал Ашиш.Насколько я могу судить, для удаления требуется O (n^2), потому что для каждого ребра (предположим, что отсортировано уже в списке) нам нужно найти наименьшее ребро, которое соединяет два связующих дерева. Это может занять до O (n^2), если единственным связанным с ними ребром является также край с самым высоким значением. –
Unfortunetly в Крускала алгоритма вам нужно союзной найти который не O (1) ;/ –