#algorithm #graph #graph-theory #minimum-spanning-tree
#алгоритм #График #теория графов #минимальное связующее дерево
Вопрос:
Как мы находим MST (Minimum Spanning Tree) после добавления нового узла или изменения расстояния путей?
Мне нужна помощь, чтобы решить это. Кто-нибудь может мне помочь?
Спасибо.
Ответ №1:
При добавлении новых ребер:
Вам нужно будет выполнить обход графика, для этого проще всего использовать DFS, с одной из сторон измененного / нового ребра. Если вы можете вернуться к узлу, на котором были раньше, у вас есть цикл.
В этом цикле вам нужно будет удалить наибольшее ребро. Вы снова получите дерево, и это дерево с минимальным охватом.
Если вы меняете веса ребер, вам нужно будет:
- Разделите график на 2 компонента, A и B, временно удалив новое ребро.
- Если новое ребро имеет меньший вес, чем раньше, вы можете вставить его обратно. В противном случае:
- Выполните итерацию по ребрам, которые вы обработали ранее, и проверьте, соединяют ли они A с B.
- Выберите наименьшее ребро из них и соедините компоненты, используя это ребро.
Опять же, вы получаете новое минимальное связующее дерево.
В целом, это O(V E) , умноженное на небольшой коэффициент обратного Аккермана.
Комментарии:
1. Что гарантирует, что это новое дерево (при добавлении новых ребер) по-прежнему является минимальным связующим деревом?
2. Есть ли какой-либо линейный способ добавить узел (со сколькими ребрами он может)?