Обновление минимального остовного дерева при вставке нового ребра

Question

Мне представили следующую проблему в университете:

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

1. Дайте эффективный алгоритм проверки, если T остается остовным деревом с минимальной стоимостью, с новым ребром, добавленным к G (но не к дереву T ). Сделайте ваш алгоритм запущенным во времени O (| E |). Вы можете сделать это за O (| V |) время? Обратите внимание на любые предположения о том, какая структура данных используется для представления дерева T и графика G .
2. Предположим, 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

Answer 1

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

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

1. Пусть a будет «более глубоким» узлом; поменяйте местами если нужно.
2. Переходите по родительским ссылкам с a до достижения b или r , сохраняя пройденный путь, отмечая посещенные узлы.
3. Если вы достигнете b , кратчайший путь будет таким же, как пройденный.
4. Если вы достигнете r , то также пройдите от b до корня; если вы достигнете узла, достигшего в обходе от a до r , остановитесь. Присоединяйтесь к двум, где они встречаются, и вы получите кратчайший путь в T .

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

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

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

Answer 2

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

Answer 3

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