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

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在研究使用递归回溯的有向图循环。这里有一个建议的伪代码

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)

尽管与相比Tarjans algorithm，这不是最高效的算法，但对于我来说，这足够简单。当前，此代码没有检测到的循环数。

我用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个周期作为输出。

我可以看到我的当前代码对已经属于先前检测到的循环的每个顶点进行了循环检测（例如：具有三个节点的循环为每个单独的节点提供了三个循环，而这必须是一个）。我在这里需要一些提示，以解决问题并进行一些修复。

回答：

对于(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调用后设置访问标记。

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

以上是 使用递归回溯在有向图中找到所有循环 的全部内容， 来源链接： utcz.com/qa/403929.html

回到顶部