Search for all cycles in a directed graph by depth-first traversal
I wrote a program to search for all cycles in a directed graph and their number by depth-first search. The graph is defined by a list of edges. But this program doesn't work quite right.(Graph and what happened in the images) Dear programmers, can anyone help with this problem?`
int from = 0, n = 0, k = 0,ncycle=0, to;
void DFS(int v){
color[v]=1;
for (int i=0; i<nreber; i++){
if(g[i][0]==v){
to = g[i][1];
if( color[to]==0){
p[n][0]=g[i][0];
p[n][1]=g[i][1];
from=v;
n++;
DFS(to);
}
else if (color[to]=1){
p[n][0]=g[i][0];
p[n][1]=g[i][1];
k=n;
cout<<ncycle+1<<") ";
for(int i=0; i<k;i++)
cout << p[i][0] << '-'<< p[i][1] << ' ';
cout << p[k][0] << '-' << p[k][1] << ' ' << endl;
ncycle++;
}
color[v]=2;
}
}
}
0
Author: aleksandr barakin, 2019-05-31
1 answers
As far as I understand, all the loops can be obtained something like this (pseudocode):
dfs(v, v_start):
if (visited[v]):
if (v == v_start):
вывести цикл
return
visited[v] = 1
for neighbor in adjlist[v]:
dfs(neighbor, v_start )
visited[v] = 0
for v in vertices:
dfs(v, v)
remove(v)
P.S. They write that the Johnson algorithm is efficient (and in Python networkx. simple_cycles it is used)
0
Author: MBo, 2019-05-31 10:11:07