Мне дан связный взвешенный граф с неотрицательными весами. Я хочу преобразовать его в связный, ациклический граф так, чтобы сумма весов удаленных ребер была минимальной. Выходными данными будут удаленные ребра.
Мои мысли: поскольку связанный ациклический граф - это дерево, я могу просто взять максимальные n-1 ребра и удалить все остальные. Но это не всегда может быть правильно. Это может привести к отключенному графику.
Тогда я подумал об использовании dfs. Я знаю, как мы можем определить, есть ли у цикла цикл с использованием dfs, но я не знаю, как обнаружить все вовлеченные ребра и как мы можем преобразовать его в ациклический граф. Любая помощь (код / псевдокод / алгоритм в словах) будет принята с благодарностью. Спасибо ...