循环检测的代码在Java有向图中没有找到返回正确的循环数？

Question

(A B),(B C),(C E),(E A),(B E)

这是我的代码；

public int getTotalCyclesinDir(){
    clearAll();
    int count=0;
    for (Vertex v : vertexMap.values()) {
        if (!v.isVisited && isCyclicDirected(v))
            count++;
    }
    return count;
}

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

Answer 1

您的算法至少存在两个问题：

>

iscyclicdirected只是检测图中是否有循环。你不能直接用它来计数循环。例如，您的算法将计算（A B）（B A）（C A）中的两个周期，因为（C A）连接到一个被访问的节点。

如果你想在你的例子中检测两个循环，你的检测需要基于边缘而不是基于顶点。(B、E)形成一个循环，但是B和E都被标记为从以前的运行中访问。