Вторые минуты стоят связующего дерева
Я пишу алгоритм для нахождения, что вторые минуты стоят связующего дерева. моя идея была следующие:
- Используйте kruskals для нахождения самого низкого MST.
- Удалите самый дешевый край MST.
- Выполненный kruskals снова на всем графике.
- возвратите новый MST.
Мой вопрос: это будет работать? Существует ли лучший путь, возможно, чтобы сделать это?
3 ответа
Рассмотрим этот случай:
------100----
| |
A--1--B--3--C
| |
| 3
| |
2-----D
MST состоит из A-B-D-C (стоимость 6). Вторая минимальная стоимость - A-B-C-D (стоимость 7). Если вы удалите край с наименьшей стоимостью, вместо этого вы получите A-C-B-D (стоимость 105).
Значит, ваша идея не сработает. Я не знаю, что получше ...
Вы можете сделать это - попробуйте удалить ребра MST по одному с графика и запустите MST, взяв с него минимум . Так что это похоже на ваше, за исключением итеративного:
- Используйте Kruskals, чтобы найти MST.
- Для каждого ребра в MST:
- Удалить ребро из графа
- Вычислить MST 'на MST
- Следить за наименьшим MST
- Добавить ребро обратно в граф
- Возвращает наименьшее значение MST.
Вы можете сделать это в O (V 2 ). Сначала вычислите MST, используя алгоритм Прима (можно выполнить в O (V 2 )).
Вычислить max [u, v] = стоимость края максимальной стоимости на (уникальном) пути от u до v в MST . Может быть выполнено за O (V 2 ).
Найдите ребро (u, v) , которое НЕ является частью MST, которая минимизирует abs (max [u, v] - weight (u, v)) . Можно сделать за O (E) == O (V 2 ).
Верните MST '= MST - {край с максимальным [u, v] весом} + {(u, v)} , что даст вам второй лучший MST.
Вот ссылка на псевдокод и более подробные объяснения.