用于BGL图的简单循环移除算法

Question

我的问题应该很简单,给定一个图(BGL adjacency_list)是否有一个简单的算法去除周期？我的第一次尝试是使用DFS访问者检测关闭循环的边缘然后将其删除但我无法正确实现它.

有什么建议？代码示例最好.

Answer 1

提升很棒.它有一个depth_first_search接受访问者的方法.您可以在此处查看有关它的更多信息.

您需要做的就是实现这样的访问者:

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

当然记住后边缘是关闭图中循环的边缘.