MST с модификацией

Question

Может ли кто-нибудь подумать о способе модифицировать алгоритм Крускала для минимального связующего дерева, чтобы он должен был содержать некоторый ребро (u, v)?

Answer 1

Возможно, я сбиваю с толку, но, насколько я помню, kruskal может обрабатывать отрицательные веса, поэтому вы можете дать этому краю -infinity вес.

• Конечно, это не на самом деле будет -infinity, но ряд достаточно низкой быть значительным настолько, что нельзя игнорировать, что-то вроде -1 * sigma(|weight(e)|) для каждого е в Е.

Answer 2

Если вы можете измените структуру графа, вы можете удалить вершины u и v и заменить их новой вершиной w, в которой используются ребра u и v. В случае повторяющихся ребер выберите один с наименьшим весом.

Answer 3

При условии, что мы знаем вес кромки (u, v), мы также можем просто добавить его к фронту нашего отсортированного списка реберных весов (так как Крускаль сортирует вес ребер в порядке возрастания). В этом случае ребро (u, v) будет первым ребром, включенным в наше дерево, и Kruskal будет работать нормально, найдя остовное дерево с минимальным весом с (u, v).