Поиск всех циклов в ориентированном графе с использованием рекурсивного обратного отсчета

Я работаю над поиском циклов в ориентированном графе с использованием рекурсивного обратного отсчета. Для этого здесь предлагается предложенный псевдокод, который находится здесь:

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;

Вызвать вышеуказанную функцию с помощью запуска node:

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

Для (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];
}