При добавлении новых ребер:
Вам потребуется выполнить обход графика, для этого проще всего использовать DFS с одной из сторон модифицированного / нового ребра.Если вы можете вернуться к узлу, на котором вы были раньше, у вас есть цикл.
В этом цикле вам нужно будет удалить наибольшее ребро.Вы снова получите дерево, и оно будет минимальным.
Если вы меняете веса ребер, вам необходимо:
- Отключитьпостроите график на 2 компонента, A и B, временно удалив новое ребро.
- Если новое ребро имеет меньший вес, чем раньше, вы можете вернуть его обратно. В противном случае:
- Итерировать поребра, которые вы обрабатывали ранее, и проверьте, соединяют ли они А с B.
- Выберите наименьшее ребро из них и соедините компоненты, используя это ребро.
Опять вы получитеновое минимальное остовное дерево.
В целом это O(V+E), умноженное на небольшой коэффициент обратного Аккермана.