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

我使用DFS编写了用于计算有向图中周期数的代码。检查循环是否存在的方法工作正常。我现在迭代所有顶点（我在HashMap中），并检查顶点是否未访问，然后检查循环是否存在，如果是这样，则递增计数器1.现在代码中断，它不会给出正确的数字例如：对于具有以下边缘的图：用于循环检测的代码未找到在Java中的有向图中返回正确的循环次数？

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

来源

2013-11-26 brain storm

您希望得到哪个数字？算法返回什么？ –

我期望2，因为有两个周期，但它只返回一个 –

另外，我看到在我的'isCyclicDirected'方法中有太多的return语句。有没有简化它的方法？ –

至少有两个问题你的算法：

isCyclicDirected只是检测是否有图中的任何周期。你不能直接使用它来计算周期。例如，您的算法将计算（A B）（B A）（C A）中的两个周期，因为（C A）连接到访问节点。
如果你想在你的例子中检测两个周期，你的检测需要基于边缘而不是基于顶点。（B E）形成一个循环，但B和E都被标记为前一次运行的访问。

来源

2013-11-26 22:27:46

我明白了你的观点。 1）你是什么意思的边缘为基础，你可以详细说一点2）在'isCyclicDirected'方法中，我有太多的回报，是所有必要或任何简化空间..谢谢 –

假设有一条河，你想计数桥梁。你从桥的一边开始，并将岸标记为已访问。然后你穿过桥并将另一侧标记为已访问。然后你得出结论，只有一座桥，因为你已经访问过双方。 –

我对代码进行了更改，实现方式不同以跟踪边缘。仍然有一些问题，我在这里发布..http：//stackoverflow.com/questions/20253255/couting-back-edges-to-get-the-number-of-cylces-in-a-directed-graph –

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

回答

相关问题