Динамическое минимальное остовное дерево
Я хочу создать динамическое минимальное остовное дерево. У меня есть существующее дерево MS над n вершинами, и я добавляю еще одну вершину и ребра ко всем существующим вершинам из этой новой вершины. Как я могу эффективно обновить MST для нового графика? O(n) будет оптимальным. Могу ли я также сделать операцию удаления вершины эффективной?
2 ответа
O(n log n) используя алгоритм Крускала. Основная идея заключается в том, что любые ребра, не используемые в исходном MST, также не будут использоваться в новом MST. Так что просто сортируйте n новые края O(n log n), объединить этот отсортированный список со списком ребер старого MST (который вы сохранили в порядке сортировки, верно?) O(n), а затем снова запустите алгоритм Крускала для полученного отсортированного списка ребер O(n)-ish,
Эта проблема может быть решена с помощью упорядочения с учетом местоположения. Пожалуйста, обратитесь к этому документу. Они обсуждают стоимость формирования динамического минимального остовного дерева и то, что оно дает приближение (1+ эпсилон) к наиболее оптимальному решению.