统计反向边来获取有向图中循环的数量

Question

我一直在编写代码，以获取有向图中所有可能的循环。这里是一个追踪反向边的实现，每当发现一个反向边时，它会返回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;
    }

- eagertoLearn

---

我认为你正在思考一个非平凡问题，已经有一些已知的解决方案。你是否查看了 SO 上以前的答案？例如这个：https://dev59.com/PXRB5IYBdhLWcg3wtJGF 其中一个答案提到了一个在 Java 中计算循环次数的算法：http://normalisiert.de/code/java/elementaryCycles.zip - Ricardo

@Ricardo：我看了一下。我同意，这不是一个简单的问题。你提供的链接中有Himadri Choudhury的帖子。那个解决方案似乎很优雅，但并不清楚。我在那里留了一个注释，但没有人回复。 - brain storm

Answer 1

回边的数量并不是循环的数量，因为单个回边可以参与多个循环。

在您的图G1中，让我们从A开始跟踪深度优先搜索的进展：它访问A->B->C，然后在D和E之间做出选择。让我们假设它选择了D。然后它访问E，并发现一个回边连接到B。问题在于，EB边既参与了BCE循环，又参与了BCDE循环！

这里有另一个例子：考虑四个节点的完全定向图。有12条边，但是：

- 6个两顶点循环 - 8个三顶点循环 - 6个四顶点循环

总共有20个循环——比图中的边还要多！实际上，一个图中可能有指数级别的循环数量，而计算它们的问题被称为#CYCLE，如果P != NP，则无法在多项式时间内计算。

- Andy Jones

---

假设每次遇到一条反向边，我们记录该反向边以及所有从当前节点返回到相邻祖先节点的边（连接到相邻节点的前任路径）。这是否至少意味着我们拥有参与所有循环的所有边？ - Kun

Answer 2

如先前所述，单个反向边可能对多个环产生贡献，因此反向边的数量不同于环的数量。 可以使用Johnson算法在图中找到所有简单循环。

- Shreyas SIngh