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

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

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

Старт Прима или Крускала ALG с и или V, пока мы не достигнем фрагмента заданной остовного пути дерева? Кажется, новое остовное дерево не сильно изменится с одного нового края.

источник

2011-01-26 yetanothercoder

Поскольку это проблема домашних заданий, вы можете объяснить более конкретно, что вы хотите помочь? Это большая проблема, но мы не просто дадим вам ответ. – templatetypedef

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

Источник: Trail Maintenance IOI 2003

источник

2011-01-26 20:22:48 marcog

Идеальный ответ на вопрос, не относящийся к домашним задаткам. Но это вопрос домашней работы, поэтому -1. –

+16

@j_random_hacker - Некоторым людям интересно узнать, почему вы занижены: см. [Этот вопрос в Meta] (http://meta.stackexchange.com/questions/76694). Что должен сделать marcog, чтобы сделать это лучшим ответом на вопрос о домашнем задании? – ChrisW

Вау! Я не ожидал создать столько споров. Спасибо @ChrisW за указатель. Я попытаюсь объяснить свою позицию по этому Мета-вопросу (который, на мой взгляд, является отличным примером мета-вопроса, BTW). –

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

ответ

Смежные вопросы