使用递归回溯找到有向图中的所有循环。

Question

使用递归回溯找到有向图中的所有循环。

javaalgorithmrecursiondirected-graphcyclic-graph

4

我正在使用递归回溯法寻找有向图中的循环。这里提供了一个建议的伪代码（链接），如下：

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

使用起始节点调用上述函数：

visited = {}
dfs(adj,start,visited)

虽然与Tarjan算法相比，这不是最高效的算法，但对我来说足够简单易懂。目前，此代码未统计检测到的循环次数。

我用Java实现了此算法：

//this is the main method that calls the helper DFS which runs on each node
public int allCyclesDirectedmain(){
    //this initializes all vertices
    clearAll();
    int[] count = new int[1];
    for (Vertex v: vertexMap.values()){
        //System.out.println(v.name);
        //clearAll();
        dfs(v,v,count);
    }
    return count[0];
}

//start and v are same when the method first fires.
public void dfs(Vertex start, Vertex v,int[] count){
   if (v.isVisited){
       if (start==v){
           //found a path
           count[0]++;
       }
       return ;
   }
   v.setVisited(true);
   for (Edge e : v.adj){
       Vertex next = e.target;
       dfs(start,next,count);
   }
   v.setVisited(false);
}

对于具有以下边的图：
(1 2),(2 3),(3 1),(2 5),(5 6),(6 2)-- 我得到了6个循环作为输出。 (1 2),(2 3),(3 4),(4,1),(2 5),(5 6),(6 2) -- 我得到了7个循环作为输出。

我可以看出我的当前代码对已经是先前检测到循环的一部分的每个顶点进行循环检测（例如：三个节点的循环给我每个单独节点的三个循环，而这应该是一个循环）。在这里我需要一些提示，关于出了什么问题以及如何修复。

- brain storm

1

你能把所有的代码上传到这里吗？我想在Python中尝试一下，如果你上传它会很有帮助。 - Lee Yaan

请上传完整的代码，我想在我的端上实现它。谢谢。 - Vishwa Ratna

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

对于 (1 2),(2 3),(3 1)，你调用了以下函数：

dfs(vertex1, vertex1, count)，这将给你带来循环：1 -> 2 -> 3 -> 1。
dfs(vertex2, vertex2, count)，这将给你带来循环：2 -> 3 -> 1 -> 2。
dfs(vertex3, vertex3, count)，这将给你带来循环：3 -> 1 -> 2 -> 3。

因此你多次计算了相同的循环。

我能想到最简单的解决方法就是在 dfs 调用后设置 visited 标志。

public int allCyclesDirectedmain(){
    clearAll();
    int[] count = new int[1];
    for (Vertex v: vertexMap.values()){
        dfs(v,v,count);
        v.setVisited(true); // <---
    }
    return count[0];
}