Обновление минимального связующего дерева при вставке нового края

В университете мне была предложена следующая проблема:

Пусть G = (V, E) - (неориентированный) граф с затратами c e >= 0 на ребрах e & isin; E. Предположим, вам присвоено дерево G с минимальными затратами T в G. Теперь предположим, что к G добавлен новый край, соединяющий два узла v, t v & isin; V со стоимостью c.

  • Дайте эффективный алгоритм для тестирования, если T остается деревом с минимальными затратами с новым краем, добавленным в G (но не с деревом T). Сделайте свой алгоритм во времени O (| E |). Можете ли вы сделать это в O (| V |) раз? Обратите внимание на любые предположения о том, какая структура данных используется для представления дерева T и графа G.
  • Предположим, что T больше не является связующим деревом минимальной стоимости. Дайте алгоритм с линейным временем (время O (| E |)), чтобы обновить дерево T до нового дерева привязки минимальной стоимости.

Это решение, которое я нашел:

Let e1=(a,b) the new edge added
Find in T the shortest path from a to b (BFS)
if e1 is the most expensive edge in the cycle then T remains the MST
else T is not the MST

Кажется, что это работает, но я могу легко выполнить этот пробег в O (| V |), тогда как проблема задает время O (| E |). Я что-то пропустил?

Кстати, мы уполномочены просить о помощи у кого-нибудь, поэтому я не обманываю: D

Ответы

Ответ 1

У вас есть правильная идея, хотя вы можете сделать лучше, чем BFS для поиска кратчайшего пути, если вы правильно сохраните дерево.

Скажите, что один node r в T является корнем (вы можете выбрать любые node и BFS отсюда, чтобы создать эту структуру, если вы пометили ребра дерева в структуре графика матрицы или графства), и каждый другой node имеет родительский указатель и подсчет глубины. Чтобы найти кратчайший путь между a и b в T:

  • Пусть a - "глубже" node; при необходимости замените.
  • Пройдите по родительским ссылкам с символа a до тех пор, пока не будет достигнуто значение b или r, сохраняя пройденный путь, отмечая посещенные узлы.
  • Если вы достигнете b, кратчайший путь будет пройден.
  • Если вы достигнете r, то также переходите от b к корню; если вы достигнете node, достигнутого в обход от a до r, остановитесь. Присоединитесь к двум, где они встречаются, и у вас есть кратчайший путь в T.

Доказательство справедливости этого алгоритма остается как упражнение для читателя. Это O (| V |), как BFS, но также будет быстрее. Только несколько конфигураций MST фактически потребуют времени O (| V |) на практике. Разумеется, для генерации дерева родительской ссылки сначала следует время O (| V |), поэтому в некоторых случаях это помогает только в том случае, если вы используете алгоритм построения MST, который естественным образом создает эту структуру в процессе определения MST.

Как сказал еще один комментатор, обратите внимание, что если есть MST для графа, он связан, поэтому | V | <= | E | и, следовательно, O (| V |) < O (| E |).

Кроме того, чтобы исправить дерево в O (| V |), при необходимости, просто найдите самый длинный край цикла и удалите его, заменив его новым краем. Выполнение этого эффективно с помощью MST родительского канала также является упражнением для читателя.

Ответ 2

Я думаю, что BFS будет достаточно. И это сложность O (| V | + | E |), но в дереве | E | меньше | V | так что O (2 | V |), что O (| V |)

Ответ 3

Я считаю, что ваш шаг Find in T the shortest path from a to b - операция порядка E.