问题:

My problem should be pretty simple, given a graph (BGL adjacency_list) is there a simple algorithm to remove cycles? My first attempt was to use the DFS visitor to detect an edge that'd close the cycle and then remove it but I was unable to implement it correctly.

Any suggestions? Code samples would be best.

回答1:

Boost is great. It has a depth_first_search method that accepts a visitor. You can see more information about it here.

All you need to do is implement a visitor like this:

class CycleTerminator : public boost::dfs_visitor<> {
    template <class Edge, class Graph>
    void back_edge(Edge e, Graph& g) {
        //implement
    }
};

remembering of course that a back edge is an edge that closes a cycle in the graph.

回答2:

It's a simple DFS, as you said. Each time you come to a node you visited before, there's a cycle. Just remove the last edge.

A pseudocode in no particular language.

void walk(current_node, previous_node)
   if visited[current_node]
      remove edge between current_node and previous_node
      return
   end

   visited[current_node] = true
   for (each adjacent node) 
      walk(adjacent_node, current_node)
   end
end