为BGL图形简单循环删除算法 [英] Simple cycle removing algorithm for a BGL graph

问题描述

我的问题应该是pretty的简单，给定一个图（BGL的adjacency_list）有一个简单的算法来去除周期？我的第一次尝试是使用DFS游客来检测会关闭循环，然后将其删除的边缘，但我无法正确地执行它。

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.

有什么建议？ code样品将是最好的。

Any suggestions? Code samples would be best.

推荐答案

升压是伟大的。它有一个 depth_first_search 方法接受访问者。 在这里你可以看到关于它的更多信息。

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.

这篇关于为BGL图形简单循环删除算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！