Как найти минимальное связующее дерево, содержащее заданное ребро?

Question

В взвешенном неориентированном графе мне нужно найти минимальное остовное дерево, содержащее заданное ребро 'e', ​​если это возможно.Как мне это сделать?Крускал, начиная с 'е'?

Answer 1

Для ленивого решения обнуляем стоимость этого ребра и запускаем на нем любой алгоритм MST.

Answer 2

Я бы не использовал бы алгоритм Крускала , потому что , если ребро e является частью цикла и e имеет максимальный вес в этом цикле, то алгоритм не будет включать 'e «. Я считаю, что с модификацией это может сработать. Но с модификацией алгоритма Прима требуется минимальная.

Алгоритм Прима лучше всего подходит для этой задачи, если мы вспомним, что алгоритм Прима выглядит так:

ШАГ 1 : начать с набора S , содержащего случайно выбранную вершину.

ШАГ 2 : Из всех ребер с одной вершиной в наборе S и другими вершинами в наборе V - S , выбрать тот с минимальным весом. Пусть это будет (x, y) , x принадлежит S и y принадлежит V - S .

ШАГ 3 : Добавьте y , чтобы установить S .

ШАГ 4 : повторяйте шаги 2 и 3 до тех пор, пока S не содержит все вершины.

Требуется изменение :

Для вашей проблемы просто измените шаг 1 на:

ШАГ 1 : Начните с набора S , содержащего вершину u и v , где ребро 'e' = ( u , v ).