获取已找到的图形循环中的所有顶点或边

Question

我需要的是存储在图上形成循环的所有边或顶点。在网上搜索了两天后，我离不起作用的代码越近：

struct CycleDetector : public dfs_visitor<> {
CycleDetector(std::vector<Vertex> p, std::vector<Vertex>& _cycle) : m_predecessor(p), cycle(_cycle)  { }
void back_edge(Edge e, Graph const& g)
{
    Vertex t = target(e, g);
    Vertex c = source(e, g);
    std::cout << "(" << t << "," << c << ")" << std::endl;
    std::cout << "Predecessor: " << m_predecessor[c] << std::endl;
    cycle.push_back(c);
    do {
        c = m_predecessor[c];
        cycle.push_back(c);
    } while(c != t);
}
protected:
std::vector<Vertex>& cycle;
std::vector<Vertex> m_predecessor;
};
int main()
{
//after a routine to create the graph and add_edges
std::vector<Vertex> cycle;
std::vector<Vertex> p(num_vertices(g1));
CycleDetector vis(p, cycle);
depth_first_search(g1, visitor(vis));
for (int i=0; i<cycle.size(); i++)
  std::cout << cycle[i] << ", ";
std::cout << std::endl;

这是程序的输出。这是一个极大度为2的生成树。我在E和H顶点上添加一条边，以创建一个循环。我需要检测这个循环并返回形成它的所有顶点或边。

谢谢。

程序的输出

Answer 1

经过大量的搜索和尝试，我想我得到了我需要的。我创建了一个映射来存储深度优先搜索中每个节点的父节点。对于每一个tree_edge，我都存储节点及其父节点。当调用back_edge时，我可以检测到一个循环，然后运行父节点的映射。

我希望它能帮助

struct MyVisitor : default_dfs_visitor {
MyVisitor(EdgeSet& tree_edges, std::vector<Vertex>& _cycle) : tree_edges(tree_edges), cycle(_cycle) {}
void tree_edge(Edge e, const Graph& g) {
    std::cerr << "tree_edge " << e << std::endl;
    tree_edges.insert(e);
    Vertex t = target(e, g);
    Vertex c = source(e, g);
    m_predecessor[t] = c;

}
void back_edge(Edge e, const Graph& g) {
    if (tree_edges.find(e) == tree_edges.end()) {
        std::cerr << "back_edge " << e << std::endl;
        Vertex t = target(e, g);
        Vertex c = source(e, g);
        std::cout << "(" << name[t] << "," << name[c] << ")" << std::endl;
        cycle.push_back(c);
        do {
        c = m_predecessor[c];
        cycle.push_back(c);
        } while(c != t);
    }
}
private: 
   EdgeSet& tree_edges;
public:
   std::vector<Vertex>& cycle;
   map<Vertex, Vertex> m_predecessor;
};
int main() {
//routine that add the edges and other things
EdgeSet tree_edges;
std::vector<Vertex> cycle;
MyVisitor vis(tree_edges, cycle);
depth_first_search(g1, visitor(vis));
for (int i=0; i<cycle.size(); i++)
  std::cout << cycle[i] << ", ";
std::cout << std::endl;

谢谢！