0

我编写了用于计算有向图中的循环数的代码DFS。检查循环是否存在的方法工作正常。我现在遍历所有顶点（我在 HashMap 中）并检查是否有一个顶点未被访问，然后检查是否存在循环，如果存在则将计数器加 1。现在代码中断，它没有给出正确的数字循环例如：对于具有以下边的图：

(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;
}
4

1 回答 1

1

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

  • isCyclicDirected只是检测图中是否有任何循环。您不能直接使用它来计算周期。例如，您的算法将在 (AB) (BA) (CA) 中计算两个周期，因为 (CA) 连接到访问节点。

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

于 2013-11-26T22:27:46.187 回答