A graph is given in form of adjacency matrix. Write a code which will check whether cycle is present in the graph or not.
SOLUTION
bool cycle_check( int vertex){
static int visited[n] = {0};
visited[vertex]=1;
for ( int i=0; i-n; i++){
if ( a[vertex][i] == 1){
if ( visited[i] == 1 )
return true;
if ( visited[i] == 0)
return cycle_check(i);
}
}
visited[vertex]=2;
return false;
}
Subscribe to:
Post Comments (Atom)
2 comments:
use coloured DFS.
1. when u visit a node mark it gray and visit its descendants.
2.when all the descendents of a node have been visited mark it black.
3. In the process if u again visit a node which is gray then the graph conatins a cycle.
yep. right.
Post a Comment