I am given a connected, weighted graph, with non-negative weights. I want to convert it to a connected, acyclic graph such that sum of weights of the removed edges is minimised. The output would be the removed edges.
My thoughts: Since a connected, acyclic graph is a tree, I can simply take the maximum n-1 edges, and remove all others. But, this may not always be correct. It may lead to a disconnected graph.
Then, I thought of using dfs. I know how we can detect if a graph has cycle using dfs, but I don't know how to detect all the edges that were involved and how we can convert it to a acyclic graph. Any help (code/pseudocode/algo in words) would be appreciated. Thanks...
You need maximum spanning tree. use Kruskal's algorithm for minimal spanning tree with the negating weights.