Algorithm: Remove minium weight sum of edges to make a Weighted diagraph no cycles

Question

1. All edge weights are positive.
2. Exists multiple edges between two vertexes

Example: Geive 4 Vertexes and 5 egdegs

A1 -> A2 => 1
A2 -> A3 => 4
A3 -> A1 => 2
A4 -> A2 => 1
A3 -> A4 => 3

just remove A1 -> A2 and A4 -> A2

For simple case, simple graph, one cycle, the question is easy to solve by removing cycle minimum weight egde. For complex case, if two cycle have common edges, this situation become complex, I didn't find a effient algorithm to solve this problem.

Answer 1

It sounds like you want to produce a maximum spanning tree. It maximizes the sum of edge-weights used in a graph that has no cycles, thereby minimizing the sum of edge-weights not used (i.e., removed).

You could use Kruskal's or Prim's algorithm, which inherently finds a minimum spanning tree, but you can modify it to find a maximum spanning tree instead. For example, go through a sorted listed of edges in descending order of edge-weight. Add the current edge to the graph if it connects two previously unconnected vertices, otherwise, skip it (i.e., remove it from the input graph).