Добавить новое ребро на график и найти новое связующее дерево в O (n)

Question

Предположим, нам дано минимальное остовное дерево T данного графа G (с n вершинами и m ребрами) и новое ребро e = (u, v) веса w, которое мы добавим к G. Дайте эффективный алгоритмнайти минимальное остовное дерево графа G + e.Ваш алгоритм должен работать за O (n) время, чтобы получить полный кредит.

(c) из руководства Skiena

Запустите Prim или Kruskal alg от u или v, пока мы не достигнем фрагмента данногоПуть к связующему дереву?Кажется, что новое связующее дерево не сильно изменится с одного нового ребра.

Answer 1

Определите путь между конечными точками нового ребра в G. Если ребро максимальной длины в этом пути больше, чем у нового ребра, замените его новым ребром. Это выполняется за время O (N).

Источник: IOI по обслуживанию трассы 2003