java - 计算回边以获得有向图中的循环数

Question

我一直在编写代码来获取有向图中所有可能的循环。 Here是一种跟踪后沿的实现，只要找到一个后沿，它就会返回真值，即检测到一个周期。我将其扩展到以下内容:计算树中所有可能的后向边缘，后向边缘的数量应该给出循环数。不确定这是否正确。使用它，我实现了以下内容:下面的 count 变量没有用。最初我让它给出每个周期的计数。但这并没有给出正确的答案。但是存储所有后边的 edgeMap 的大小似乎在一些图中给出了正确的循环数，但不是全部。

该代码适用于图片中的 G2 和 G3，但不适用于 G1。 (G1 只有两个周期，但我得到三个后沿)。关于我可能出错的地方的任何建议都会有所帮助

public int allCyclesDirectedmain(){
        clearAll();
        int count=0;
        Map<Vertex, Vertex> edgeMap = new HashMap<>();


        for (Vertex v : vertexMap.values()) {
            if (!v.isVisited && allCyclesDirected(v,edgeMap))
                count++;
        }
        System.out.println(edgeMap);
        return count;

    }
public boolean allCyclesDirected(Vertex v, Map<Vertex, Vertex> edgeMap ){
        if (!v.isVisited){
            v.setVisited(true);
            Iterator<Edge> e = v.adj.iterator();
            while (e.hasNext()){
                    Vertex t = e.next().target;
                    if (!t.isVisited && allCyclesDirected(t,edgeMap)){
                        edgeMap.put(v, t);
                            return true;
                    }
                    else 
                            return true;
                    }
                }
        return false;
    }

Answer 1

backedge的数量不是循环的数量，因为一个backedge可以参与多个循环。

在您的图表 G1 中，让我们跟踪从 A 开始的深度优先搜索的进程:它访问 A->B->C，然后在 D 和 E 之间做出选择。假设它需要 D。然后它访问E，并找到一条通往 B 的后边。事实是，EB 边参与了 BCE 循环和 BCDE 循环!

这是另一个示例:考虑四个节点上的完整有向图。有12条边，但是

• 6 个双顶点循环
• 8 个三顶点循环
• 6 个四顶点循环

总共 20 个周期 - 比图中的边还多!事实上，图中的循环数可以是指数级的，计算它们的问题称为#CYCLE，is not computable in polynomial time if P != NP。 .