MST с модификацией
Кто-нибудь может придумать, как изменить алгоритм Крускала для минимального остовного дерева, чтобы оно включало определенное ребро (u,v)?
3 ответа
Может быть, я запутался, но, насколько я помню, Kruskal может работать с отрицательными весами, так что вы можете дать это преимущество -infinity вес.
- Конечно, на самом деле это не будет
-infinity, но число достаточно низкое, чтобы быть достаточно значительным, чтобы его нельзя было игнорировать, что-то вроде-1 * sigma(|weight(e)|)для каждого е в Е.
Если вы можете изменить структуру графа, вы можете удалить вершины u а также vи замените их новой вершиной w, у которой раньше были ребра u и v. В случае двойных краев выберите тот, который имеет наименьший вес.
При условии, что мы знаем вес ребер (u, v), мы также можем просто добавить его в начало нашего отсортированного списка весов ребер (поскольку Kruskal сортирует вес ребер в возрастающем порядке). В этом случае ребро (u, v) будет первым ребром, включенным в наше дерево, и Kruskal будет работать нормально, находя остовное дерево минимального веса с помощью (u,v).