Znajdowanie wszystkich cykli na grafie ukierunkowanym przy użyciu rekurencyjnego śledzenia wstecznego
Pracuję nad znalezieniem cykli w grafie ukierunkowanym za pomocą rekurencyjnego śledzenia wstecznego. Sugeruje to pseudokodtutaj, który jest tutaj:
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;
Wywołaj powyższą funkcję z węzłem początkowym:
visited = {}
dfs(adj,start,visited)
Chociaż nie jest to najbardziej wydajny algorytm w porównaniu zTarjans algorithm
, to dość proste, żebym zrozumiał. Obecnie ten kod nie ma liczby wykrytych cykli liczbowych.
Zaimplementowałem to w Javie:
//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);
}
Dla wykresu z następującymi krawędziami:(1 2),(2 3),(3 1),(2 5),(5 6),(6 2)
- Dostaję 6 cykli jako wyjście.
(1 2),(2 3),(3 4),(4,1),(2 5),(5 6),(6 2)
- Dostaję 7 cykli jako wyjście.
Widzę, że mój obecny kod wykrywa cykl dla każdego wierzchołka, który jest już częścią wcześniej wykrytego cyklu (np .: cykl z trzema węzłami daje mi trzy cykle dla każdego pojedynczego węzła, podczas gdy musi to być jeden). Potrzebuję tutaj wskazówek, co się dzieje, a co nie.