Обновить минимальное связующее дерево с модификацией края

Граф (положительные веса) с MST Если какое-либо ребро, e изменено на новое значение, то какой лучший способ обновить MST, не переделав его полностью. Я думаю, что это можно сделать в линейном времени. Кроме того, кажется, что мне нужен другой алгоритм, основанный на том, является ли 1) e уже частью MST и 2) является ли новый край, e больше или меньше исходного

Ответ 1

Есть 4 случая:

Edge находится в MST и вы уменьшаете значение края:
Текущий MST по-прежнему MST
Edge не находится в MST и вы уменьшаете значение края:
Добавьте это ребро в MST. Теперь у вас ровно 1 цикл.
На основе свойство цикла в MST вам нужно найти и удалить край с самым высоким значением, которое находится в этом цикле. Вы можете сделать это с помощью dfs или bfs. Сложность O (n).
Edge находится в MST и вы увеличиваете его значение:
Удалите этот край из MST. Теперь у вас есть 2 подключенных компонента, которые должны быть подключены. Вы можете рассчитать оба компонента в O (n) (bfs или dfs). Вам нужно найти край с наименьшим значением, который соединяет эти компоненты. Итерируйте по краям в порядке возрастания по их значению. Сложность O (n).
Edge не находится в MST и вы увеличиваете его значение:
Текущий MST по-прежнему MST

Ответ 2

Решение My O (n) основано на предположении, что перед тем, как вы начнете изменять границы, вы должны найти MST (не указывается с графиком). Для этого вы можете использовать алгоритм Kruskal, который работает в O (n log n), а в качестве побочного эффекта создается отсортированный список ребер. В его стоимости преобладает сортировка, поэтому, когда вы изменяете вес края, вы можете удалить его из отсортированного списка в O (log n) и вставить его обратно с новым значением, также в O (log n) и, наконец, вызвать Kruskal алгоритм снова, который теперь работает в линейном времени, так как ребра сортируются.

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