Нахождение всех циклов в ориентированном графе с использованием рекурсивного обратного отслеживания
Я работаю над поиском циклов в ориентированном графе с использованием рекурсивного отслеживания. Для этого есть псевдокодВот, который здесь:
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 циклов в качестве выхода.
Я вижу, что мой текущий код выполняет обнаружение циклов для каждой вершины, которая уже является частью ранее обнаруженного цикла (например: цикл с тремя узлами дает мне три цикла для каждого отдельного узла, в то время как это должен быть один). Мне нужно несколько советов о том, что идет не так, и некоторые исправления.