**Find whether a Directed Graph is Cyclic or not**

**Find whether a Directed Graph is Cyclic or not**

Write a C Program to find whether a Directed Graph is Cyclic or not. Here’s simple Program to find whether a Directed Graph is Cyclic or not.

**Depth First Search (DFS)**

**Depth First Search (DFS)**

Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

It employs the following rules.

**Rule 1**− Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.**Rule 2**− If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)**Rule 3**− Repeat Rule 1 and Rule 2 until the stack is empty.

We shall not see the implementation of Depth First Traversal (or Depth First Search) in C programming language

**Also Read : : C Program for Traversing Directed Graph through DFS and classifying all edges**

Below is the source code for C Program to find whether a Directed Graph is Cyclic or not in output which is successfully compiled and run on Windows System to produce desired output as shown below :

**SOURCE CODE : :**

**SOURCE CODE : :**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
/* C Program to find whether a Directed Graph is Cyclic or not */ #include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define visited 2 #define finished 3 int n; /*Number of vertices in the graph */ int adj[MAX][MAX]; void create_graph( ); int state[MAX]; void DF_Traversal(); void DFS(int v); int main() { create_graph(); DF_Traversal(); return 0; }/*End of main()*/ void DF_Traversal() { int v; for(v=0; v<n; v++) state[v] = initial; DFS(0);/*start DFS from vertex 0*/ for(v=0; v<n; v++) { if(state[v]==initial) DFS(v); } printf("\nGraph is Acyclic\n"); }/*End of DF_Traversal( )*/ void DFS(int v) { int i; state[v] = visited; for(i=0; i<n; i++) { if(adj[v][i]==1) { if(state[i]==initial) DFS(i); else if(state[i]==visited) { printf("\nBack edge (%d,%d) found\n", v, i); printf("\nGraph is cyclic\n"); exit(1); } } } state[v] = finished; }/*End of DFS()*/ void create_graph() { int i,max_edges,origin,destin; printf("\nEnter number of vertices : "); scanf("%d",&n); max_edges = n*(n-1); for(i=1;i<=max_edges;i++) { printf("\nEnter edge %d( -1 -1 to quit ) : ",i); scanf("%d %d",&origin,&destin); if( (origin == -1) && (destin == -1) ) break; if( origin >= n || destin >= n || origin<0 || destin<0) { printf("\nInvalid edge!\n"); i--; } else { adj[origin][destin] = 1; } } } |

*OUTPUT : :*

*OUTPUT : :*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/* C Program to find whether a Directed Graph is Cyclic or not */ Enter number of vertices : 6 Enter edge 1( -1 -1 to quit ) : 0 1 Enter edge 2( -1 -1 to quit ) : 0 2 Enter edge 3( -1 -1 to quit ) : 0 3 Enter edge 4( -1 -1 to quit ) : 1 3 Enter edge 5( -1 -1 to quit ) : 3 4 Enter edge 6( -1 -1 to quit ) : 2 5 Enter edge 7( -1 -1 to quit ) : 5 4 Enter edge 8( -1 -1 to quit ) : -1 -1 Graph is Acyclic Process returned 0 |

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may * Contact Us* through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

**Thanks for reading the post…**

**Recommended Posts : :**

**Recommended Posts : :**

- Traversing Directed Graph through DFS and classifying all edges
- Traversing a Directed Graph through DFS each vertex assigned discovery and finishing time
- Traversing a Directed Graph through DFS recursively, with comments displayed in output
- Traversing a Directed Graph through DFS recursively
- Traversing an Undirected Graph through DFS
- Traversing a directed graph through DFS