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

Question

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

Answer 1

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

1. Край в MST, и ты уменьшаешь значение края:
   Текущий MST все еще MST

2. Край не находится в MST, и вы уменьшаете значение ребра:
   Добавьте это ребро в MST.Теперь у вас ровно 1 цикл.
   На основе свойства цикла в MST вам нужно найти и удалить ребро с наибольшим значением, которое есть в этом цикле.Вы можете сделать это, используя DFS или BFS.Сложность O (n).

3. Край в MST, и вы увеличиваете его значение ребра:
   Удалите этот край из MST.Теперь у вас есть 2 подключенных компонента, которые должны быть подключены.Вы можете рассчитать оба компонента в O (n) (BFS или DFS).Вам нужно найти ребро с наименьшим значением, которое соединяет эти компоненты.Итерировать по ребрам в порядке возрастания по их значению.Сложность O (n).

4. Edge отсутствует в MST, и вы увеличиваете его значение edge:
   Текущий MST по-прежнему MST

Answer 2

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

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