Нахождение минимального остовного дерева с учетом старого MST и новой вершины + ребер - PullRequest
Новая
       27

Нахождение минимального остовного дерева с учетом старого MST и новой вершины + ребер

2 голосов
/ 18 ноября 2011

В примере задачи мне дан MST T для взвешенного графа G = (V, E).Вопрос в том, что если в граф добавить новую вершину v и все ее ребра, то что такое алгоритм o (| V | log | V |) для вычисления нового MST этого нового G * = (VU v,E *).

Моя единственная идея на данный момент: 

add min( out(v) ) to T
for each edge e in out(v) do
  let u be the other vertex of e
  if there exists a lower weight path from v to u then
    remove all edges in that path from T
    add e to T

Две проблемы:

  1. Что мне делать с вершинами, которые могли быть отключены
  2. Это определенно не O (| V | log | V |)

Как я могу это сделать?

Ответы [ 2 ]

2 голосов
/ 25 февраля 2013

Вы также можете сделать это за линейное время (если число новых ребер (скажем, k) значительно меньше по сравнению с n).Мы знаем, что новый MST должен покрывать новую вершину.Поэтому необходимо добавить хотя бы одно из новых ребер.Таким образом, ребро с наименьшим значением должно быть добавлено к MST (вы можете доказать это);может случиться так, что изменится более одного нового края.Так что сортируйте новые ребра в порядке возрастания. Добавьте первое на график;теперь у нас новый цикл.Выполняя обход графика, найдите цикл и удалите ребро с максимальным значением из этого цикла.Теперь добавьте другой новый край и повторите процедуру.

Сложность (n + m) умножается на количество вновь добавленных ребер (примерно линейно).

0 голосов
/ 29 января 2012

В конечном итоге вы знаете, что ваш MST будет среди ребер уже в этом MST, и добавлены новые ребра

Так что добавив все новые ребра, вы получите график,Сделайте любой нормальный алгоритм MST (Борувка, Крускал, Примс) по этому вопросу, и у вас будет свое решение.

Поскольку ребра в этом = = (V-2) Первоначально (V-1) добавил = 2V-1, алгоритмы достигнут требуемого времени.

...