Как я могу обнаружить цикл в неориентированном графике и опустить край с максимальным весом в этом цикле?

Question

Я знаю, что DFS или union-find могут использоваться для обнаружения цикла. Но есть ли быстрый способ найти ребро с максимальным весом в этом цикле?

Answer 1

Нет хорошего способа сделать это хотя бы один раз, но если вы собираетесь выполнять итерации до ациклического графа, вы оставите минимальное остовное дерево, которое можно вычислить за линейное время.

Answer 2

Нет, DFS и последовательный поиск - оптимальное решение. Просто найдите цикл и пройдитесь по его краям, чтобы найти край максимального веса. Сложность здесь на самом деле не имеет значения - вам все равно нужно было найти цикл, а сложность нахождения максимального края одинакова.