Алгоритмы и структуры данных

Алгоритм обратного удаления

Тесно связан с алгоритмом Краскала.

В этом алгоритме мы сортируем все ребра в порядке убывания их весов. После сортировки поочередно выбираем ребра в порядке убывания. Мы включаем текущее выбранное ребро, если исключение текущего ребра приводит к отключению в текущем графе. Основная идея — удалить ребро, если его удаление не приводит к отключению графа.

Алгоритм:
1. Отсортируйте все ребра графа в порядке невозрастания весов ребер.
2. Инициализируйте MST как исходный граф и удалите лишние ребра, используя шаг 3.
3. Выберите ребро с наибольшим весом из оставшихся ребер и проверьте, разъединяет ли удаление ребра граф или нет. Если отключается, то ребро не удаляем. В противном случае мы удаляем край и продолжаем.

Сложность: O((E*(V+E)) + E log E)

www.tgoop.com/the_algorithms/4602

6.1K viewsNov 13, 2023 at 09:01

Алгоритм обратного удаления

Тесно связан с алгоритмом Краскала.

В этом алгоритме мы сортируем все ребра в порядке убывания их весов. После сортировки поочередно выбираем ребра в порядке убывания. Мы включаем текущее выбранное ребро, если исключение текущего ребра приводит к отключению в текущем графе. Основная идея — удалить ребро, если его удаление не приводит к отключению графа.

Алгоритм:
1. Отсортируйте все ребра графа в порядке невозрастания весов ребер.
2. Инициализируйте MST как исходный граф и удалите лишние ребра, используя шаг 3.
3. Выберите ребро с наибольшим весом из оставшихся ребер и проверьте, разъединяет ли удаление ребра граф или нет. Если отключается, то ребро не удаляем. В противном случае мы удаляем край и продолжаем.

Сложность: O((E*(V+E)) + E log E)

BY Алгоритмы и структуры данных