Как найти множество ребер обратной связи в неориентированном графе

Пусть G = (V,E) — неориентированный граф. Множество ребер F ⊆ E называется множество обратных ребер, если каждый цикл G имеет хотя бы одно ребро в F.

(a) Предположим, что G не взвешена. Разработайте эффективный алгоритм поиска набор ребер обратной связи минимального размера.

(b) Предположим, что G — взвешенный неориентированный граф с положительными весами ребер. Разработайте эффективный алгоритм для нахождения набора ребер обратной связи минимального веса.

Мое решение (нужны предложения):

a) Набор ребер обратной связи минимального размера: поскольку граф невзвешенный, мы можем использовать DFS. Запускаем DFS из любой вершины как обычно. Когда мы встречаем задний край, мы вставляем его в набор ребер обратной связи. Когда DFS завершится, набор будет ответом.

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

Кто-нибудь может сказать, верно ли это решение?