计算后沿以获得有向图中的周期数

Question

我一直在编写代码以在有向图中获得所有可能的周期。 Here是一个跟踪后边缘的实现，每当找到一个后边缘时，它返回true，检测到一个周期。我将其扩展到以下内容：计算树中所有可能的后边缘，后边缘的数量应该给出周期数。不确定这是否正确。使用这个，我实现了以下：下面的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

备份数量不是周期数，因为单个备份可以参与多个周期。

在图表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。

Answer 2

如前所述，单个后备可能会在多个周期中起作用，因此后备数量与周期数不同。可以使用Johnson的算法来查找图中的所有简单循环。