Обновление минимального остовного дерева после добавления новой вершины

Question

Предположим, что граф G имеет минимальное связующее дерево, которое уже вычислено. Как мы можем быстро обновить минимальное дерево, если мы добавим новую вершину и инцидентные ребра в G.

Мое первоначальное решение состоит в том, чтобы выбрать новое добавленное ребро с наименьшим весом, а затем добавить это ребро в уже вычисленное дерево. Но, похоже, это решение неверно. Может кто-нибудь дать мне несколько советов по этому вопросу? Спасибо

Answer 1

Добавление ребра минимального веса даст неверные результаты, потому что теперь у вас есть дополнительные ребра, и более одного ребра из них может быть частью нового MST . Смотрите изображение для примера.

Вы можете использовать алгоритм Прима. Просто примите во внимание предыдущие ребра MST и новые ребра при запуске алгоритма. Это будет работать, потому что если вы запустите Prims на всем новом графе, то также все ребра, которые он добавит, будут из старого MST или новых ребер.
Вы можете использовать любой другой MST алгоритм поиска, например Kruskal с учетом вышеупомянутых ребер.