提升DFS back_edge [英] Boost DFS back_edge

问题描述

我试图在无向图中查找任何循环中所有的边.使用Boost的 depth_first_search 和我对后边缘，我不明白为什么要调用back_edge方法样本Graph中的两个边都不包含任何循环.

I'm trying to find all edges that are part of any cycle in a undirected Graph. Using Boost's depth_first_search and my understanding of back edges, I don't see why the back_edge method is called for both edges in the sample Graph which doesn't contain any cycles.

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace std;
using namespace boost;

typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > Graph;
typedef graph_traits<Graph>::edge_descriptor Edge;

class MyVisitor : public default_dfs_visitor {
    public: void back_edge(Edge e, const Graph& g) const {
        // should only be called when cycle found, right?
        cerr << "back_edge " << e << endl;
        return;
    }
};

int main() {
    Graph g;
    add_edge(0, 1, g);
    add_edge(0, 2, g);

    MyVisitor vis;
    depth_first_search(g, visitor(vis));
    return 0;
}

推荐答案

由于图形是无向的，因此任何树边缘也是后边缘. DFSVisitor的文档不会失败提这个.

Since your graph is undirected, any tree edge is also a back edge. The documentation for DFSVisitor doesn't fail to mention this.

对于无向图，树边缘和后边缘之间存在一些歧义，因为边缘(u，v)和(v，u)是相同的边缘，但是tree_edge()和back_edge()函数都将被调用.

For an undirected graph there is some ambiguity between tree edges and back edges since the edge (u,v) and (v,u) are the same edge, but both the tree_edge() and back_edge() functions will be invoked.

解决这种歧义的一种方法是记录树边缘，然后忽略已经标记为树边缘的后边缘.记录树边缘的一种简单方法是在tree_edge事件点记录前辈.

One way to resolve this ambiguity is to record the tree edges, and then disregard the back-edges that are already marked as tree edges. An easy way to record tree edges is to record predecessors at the tree_edge event point.

以最直接的方式实施: 在Coliru上直播

Implementing this in the most straightforward manner: Live on Coliru

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

namespace {
    using namespace boost;

    typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > Graph;
    typedef graph_traits<Graph>::edge_descriptor Edge;
    typedef std::set<Edge> EdgeSet;
}

struct MyVisitor : default_dfs_visitor {
    MyVisitor(EdgeSet& tree_edges) : tree_edges(tree_edges) {}

    void tree_edge(Edge e, const Graph& g) const {
        std::cerr << "tree_edge " << e << std::endl;
        tree_edges.insert(e);
    }
    void back_edge(Edge e, const Graph& g) const {
        if (tree_edges.find(e) == tree_edges.end())
            std::cerr << "back_edge " << e << std::endl;
    }

  private: 
    EdgeSet& tree_edges;
};

int main() {
    Graph g;
    add_edge(0, 1, g);
    add_edge(0, 2, g);

    std::set<Edge> tree_edges;
    MyVisitor vis(tree_edges);

    depth_first_search(g, visitor(vis));
}

这篇关于提升DFS back_edge的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！