Обновление Минимального связующего дерева, когда новый край вставляется
Я был представлен следующая проблема в Университете:
Позвольте G = (V, E) быть (неориентированным) графиком с затратами ce> = 0 на краях e ∈ E. Предположите предоставление стоившего за минимум связующего дерева T в G. Теперь предположите, что новый край добавляется к G, соединяя два узла v, ТВ ∈ 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
3 ответа
Я считаю, что ваш шаг Найти в T кратчайший путь от a до b является операцией порядка E.
Я думаю, что BFS было бы достаточно. И его сложность составляет O (| V | + | E |), но в дереве | E | меньше | V | так что O (2 | V |) это O (| V |)
У вас есть правильная идея, хотя вы может лучше, чем BFS, для поиска по кратчайшему пути, если вы правильно храните дерево.
Скажем, один узел r в T является корнем (вы можете выбрать любой узел и BFS оттуда, чтобы сгенерировать эту структуру, если вы отметили края дерева в матрице или смежности -list структура графа), и каждый другой узел имеет родительский указатель и счетчик глубины. Чтобы найти кратчайший путь между a и b в T :
- Пусть a будет «более глубоким» узлом; при необходимости поменяйте местами.
- Переход по родительским ссылкам из a до тех пор, пока не будет достигнут b или r , сохраняя пройденный путь, отмечая посещенные узлы.
- Если вы достигнете b , кратчайший путь будет пройденным.
- Если вы достигнете r , то также перейдите от b к корню; если вы дойдете до узла, достигнутого при переходе от a к r , остановитесь. Присоединяйтесь к двум там, где они встречаются, и у вас будет кратчайший путь в T .
Доказательство справедливости этого алгоритма предоставляется читателю в качестве упражнения. Это O (| V |), как у BFS, но обычно будет быстрее. Только несколько конфигураций MST на практике потребуют времени O (| V |).Конечно, создание дерева родительских ссылок для начала занимает O (| V |) времени, поэтому это помогает только в некоторых обстоятельствах, например, если вы используете алгоритм построения MST, который естественным образом создает эту структуру в процессе определения MST.
Как сказал другой комментатор, обратите внимание, что если существует MST для графа, он связан, поэтому | V | <= | E | и, следовательно, O (| V |) Кроме того, чтобы исправить дерево за время O (| V |), если необходимо, просто найдите самое длинное ребро в цикле и удалите его, заменив новым ребром. Эффективное выполнение этого с помощью MST родительской ссылки также является упражнением для читателя.