Detecting cycles in a graph using DFS: 2 different approaches and what's the difference
Solution 1:
Answering my question:
The graph has a cycle if and only if there exists a back edge. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS forming a cycle.
Both approaches above actually mean the same. However, this method can be applied only to undirected graphs.
The reason why this algorithm doesn't work for directed graphs is that in a directed graph 2 different paths to the same vertex don't make a cycle. For example: A-->B, B-->C, A-->C - don't make a cycle whereas in undirected ones: A--B, B--C, C--A does.
Find a cycle in undirected graphs
An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge).
Find a cycle in directed graphs
In addition to visited vertices we need to keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree.
Update: Working code is in the question section above.
Solution 2:
For the sake of completion, it is possible to find cycles in a directed graph using DFS (from wikipedia):
L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
select an unmarked node n
visit(n)
function visit(node n)
if n has a temporary mark then stop (not a DAG)
if n is not marked (i.e. has not been visited yet) then
mark n temporarily
for each node m with an edge from n to m do
visit(m)
mark n permanently
unmark n temporarily
add n to head of L
Solution 3:
Here is the code I've written in C based on DFS to find out whether a given undirected graph is connected/cyclic or not. with some sample output at the end. Hope it'll be helpful :)
#include<stdio.h>
#include<stdlib.h>
/****Global Variables****/
int A[20][20],visited[20],count=0,n;
int seq[20],connected=1,acyclic=1;
/****DFS Function Declaration****/
void DFS();
/****DFSearch Function Declaration****/
void DFSearch(int cur);
/****Main Function****/
int main()
{
int i,j;
printf("\nEnter no of Vertices: ");
scanf("%d",&n);
printf("\nEnter the Adjacency Matrix(1/0):\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&A[i][j]);
printf("\nThe Depth First Search Traversal:\n");
DFS();
for(i=1;i<=n;i++)
printf("%c,%d\t",'a'+seq[i]-1,i);
if(connected && acyclic) printf("\n\nIt is a Connected, Acyclic Graph!");
if(!connected && acyclic) printf("\n\nIt is a Not-Connected, Acyclic Graph!");
if(connected && !acyclic) printf("\n\nGraph is a Connected, Cyclic Graph!");
if(!connected && !acyclic) printf("\n\nIt is a Not-Connected, Cyclic Graph!");
printf("\n\n");
return 0;
}
/****DFS Function Definition****/
void DFS()
{
int i;
for(i=1;i<=n;i++)
if(!visited[i])
{
if(i>1) connected=0;
DFSearch(i);
}
}
/****DFSearch Function Definition****/
void DFSearch(int cur)
{
int i,j;
visited[cur]=++count;
seq[count]=cur;
for(i=1;i<count-1;i++)
if(A[cur][seq[i]])
acyclic=0;
for(i=1;i<=n;i++)
if(A[cur][i] && !visited[i])
DFSearch(i);
}
Sample Output:
majid@majid-K53SC:~/Desktop$ gcc BFS.c
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 10
Enter the Adjacency Matrix(1/0):
0 0 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0
The Depdth First Search Traversal:
a,1 c,2 d,3 f,4 b,5 e,6 g,7 h,8 i,9 j,10
It is a Not-Connected, Cyclic Graph!
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 4
Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1
The Depth First Search Traversal:
a,1 c,2 b,3 d,4
It is a Connected, Acyclic Graph!
majid@majid-K53SC:~/Desktop$ ./a.out
************************************
Enter no of Vertices: 5
Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0
The Depth First Search Traversal:
a,1 d,2 b,3 c,4 e,5
It is a Not-Connected, Acyclic Graph!
*/