The post C Program for Traversing Undirected Graph through DFS Recursively appeared first on CodezClub.

]]>Write a C Program for Traversing Undirected Graph through DFS Recursively. Here’s simple Program for Traversing an Undirected Graph through DFS Recursively in C Programming Language.

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 for Traversing Undirected Graph through DFS Recursively in output which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program for Traversing Undirected Graph through DFS Recursively */ #include<stdio.h> #define MAX 100 #define initial 1 #define visited 2 #define finished 3 int adj[MAX][MAX]; int n; /* Denotes number of vertices in the graph */ int state[MAX]; int predecessor[MAX]; void create_graph(); void DFS(int v); void DF_Traversal(); 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; predecessor[v] = -1; } printf("\nEnter starting vertex for Depth First Search : "); scanf("%d",&v); DFS(v); for(v=0; v<n; v++) { if(state[v] == initial) DFS(v); } }/*End of DF_Traversal()*/ void DFS(int v) { int i; state[v] = visited; printf("%d ",v); for(i=0; i<n; i++) { if(adj[v][i] == 1) { if(state[i] == initial) DFS(i); } } state[v] = finished; }/*End of DFS()*/ void create_graph() { int i,max_edges,origin,destin; printf("Enter number of vertices : "); scanf("%d",&n); max_edges = n*(n-1)/2; 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; adj[destin][origin] = 1; } } }

/* C Program for Traversing Undirected Graph through DFS Recursively */ 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 ) : 2 4 Enter edge 5( -1 -1 to quit ) : 3 5 Enter edge 6( -1 -1 to quit ) : 1 5 Enter edge 7( -1 -1 to quit ) : -1 -1 Enter starting vertex for Depth First Search : 0 0 1 5 3 2 4 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…**

- Find whether a Directed Graph is Cyclic or not
- 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

The post C Program for Traversing Undirected Graph through DFS Recursively appeared first on CodezClub.

]]>The post C Program to find whether a Directed Graph is Cyclic or not appeared first on CodezClub.

]]>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) 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 :

/* 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; } } }

/* 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…**

- 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

The post C Program to find whether a Directed Graph is Cyclic or not appeared first on CodezClub.

]]>The post C Program for Traversing Directed Graph through DFS and classifying all edges appeared first on CodezClub.

]]>Write a C Program for Traversing Directed Graph through DFS and classifying all edges. Here’s simple Program for Traversing Directed Graph through DFS and classifying all edges.

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 a Directed Graph through DFS recursively**

Below is the source code for C Program for Traversing Directed Graph through DFS and classifying all edges in output which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program for Traversing Directed Graph through DFS and classifying all edges */ #include<stdio.h> #define MAX 50 #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]; int time; int d[MAX]; int f[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; printf("\nEnter starting vertex for Depth First Search : "); scanf("%d",&v); DFS(v); for(v=0; v<n; v++) { if(state[v] == initial) DFS(v); } printf("\n"); }/*End of DF_Traversal( )*/ void DFS(int v) { int i; time++; d[v] = time; state[v] = visited; for(i=0; i<n; i++) { if(adj[v][i] == 1) { if(state[i] == initial) { printf("\n(%d,%d) - Tree edge\n", v, i); DFS(i); } else if(state[i] == visited) { printf("\n(%d,%d) - Back edge\n", v, i); } else if(d[v] < d[i]) { printf("\n(%d,%d) - Forward edge\n", v, i); } else printf("\n(%d,%d) - Cross edge\n", v, i); } } state[v] = finished; f[v] = ++time; }/*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; } } }

/* C Program for Traversing Directed Graph through DFS and classifying all edges */ 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 ) : 0 4 Enter edge 5( -1 -1 to quit ) : 1 3 Enter edge 6( -1 -1 to quit ) : 3 4 Enter edge 7( -1 -1 to quit ) : 2 5 Enter edge 8( -1 -1 to quit ) : 5 4 Enter edge 9( -1 -1 to quit ) : -1 -1 Enter starting vertex for Depth First Search : 0 (0,1) - Tree edge (1,3) - Tree edge (3,4) - Tree edge (0,2) - Tree edge (2,5) - Tree edge (5,4) - Cross edge (0,3) - Forward edge (0,4) - Forward edge 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…**

- 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

The post C Program for Traversing Directed Graph through DFS and classifying all edges appeared first on CodezClub.

]]>The post C Program for Traversing a Directed Graph through DFS each vertex assigned discovery and finishing time appeared first on CodezClub.

]]>Write a C Program for Traversing a Directed Graph through DFS recursively, each vertex assigned discovery and finishing time. Here’s simple Program for Traversing a Directed Graph through DFS each vertex is assigned a discovery and finishing time.

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.

**Also Read : : C Program for traversing a Directed Graph through DFS recursively**

Below is the source code for C Program for Traversing a Directed Graph through DFS recursively, with comments displayed in output which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program for traversing a directed graph through DFS recursively, each vertex is assigned a discovery and a finishing time */ #include<stdio.h> #define MAX 50 #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]; int time; int d[MAX]; int f[MAX]; void DF_Traversal(); void DFS(int v); int main() { int i; create_graph(); DF_Traversal(); for(i=0; i<n; i++) printf("\nVertex %d, Discovery time - %d, Finshing time - %d\n", i, d[i], f[i]); return 0; }/*End of main()*/ void DF_Traversal() { int v; for(v=0; v<n; v++) state[v]=initial; printf("\nEnter starting vertex for Depth First Search : "); scanf("%d",&v); DFS(v); for(v=0; v<n; v++) { if(state[v] == initial) DFS(v); } printf("\n"); }/*End of DF_Traversal( )*/ void DFS(int v) { int i; time++; d[v] = time; /*discovery time*/ state[v] = visited; printf("%d ", v); for(i=0; i<n; i++) { if(adj[v][i]==1) { if(state[i]==initial) DFS(i); } } state[v] = finished; f[v] = ++time; /*Finishing time*/ }/*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; } } }

/* C Program for traversing a directed graph through DFS recursively, each vertex is assigned a discovery and a finishing time */ 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 4 Enter edge 7( -1 -1 to quit ) : 2 5 Enter edge 8( -1 -1 to quit ) : -1 -1 Enter starting vertex for Depth First Search : 0 0 1 3 4 2 5 Vertex 0, Discovery time - 1, Finshing time - 12 Vertex 1, Discovery time - 2, Finshing time - 7 Vertex 2, Discovery time - 8, Finshing time - 11 Vertex 3, Discovery time - 3, Finshing time - 6 Vertex 4, Discovery time - 4, Finshing time - 5 Vertex 5, Discovery time - 9, Finshing time - 10 Process returned 0

* 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…**

- 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
- DFS Algorithm for Connected Graph
- DFS Algorithm for Disconnected Graph

The post C Program for Traversing a Directed Graph through DFS each vertex assigned discovery and finishing time appeared first on CodezClub.

]]>The post C Program for Traversing a Directed Graph through DFS recursively, with comments displayed in output appeared first on CodezClub.

]]>Write a C Program for Traversing a Directed Graph through DFS recursively. Here’s simple Program for Traversing a Directed Graph through DFS recursively, with comments displayed in output.

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.

**Also Read : : C Program to implement BFS Algorithm for Connected Graph**

Below is the source code for C Program for Traversing a Directed Graph through DFS recursively, with comments displayed in output which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program for traversing a directed graph through DFS recursively, with comments displayed in the output */ #include<stdio.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; printf("\nEnter starting vertex for Depth First Search : "); scanf("%d",&v); DFS(v); for(v=0; v<n; v++) { if(state[v] == initial) DFS(v); } printf("\n"); }/*End of DF_Traversal( )*/ void DFS(int v) { int i; state[v] = visited; printf("\nDFS(%d) called \n", v); for(i=0; i<n; i++) { if( adj[v][i] == 1 ) { if(state[i] == initial ) { printf("\n-- %d is adjacent to %d and initial\n", i, v); DFS(i); } } } state[v] = finished; printf("\nVertex %d finished\n", v); }/*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; } } }

/* C Program for traversing a directed graph through DFS recursively, with comments displayed in the output */ Enter number of vertices : 5 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 4 Enter edge 7( -1 -1 to quit ) : -1 -1 Enter starting vertex for Depth First Search : 0 DFS(0) called -- 1 is adjacent to 0 and initial DFS(1) called -- 3 is adjacent to 1 and initial DFS(3) called -- 4 is adjacent to 3 and initial DFS(4) called Vertex 4 finished Vertex 3 finished Vertex 1 finished -- 2 is adjacent to 0 and initial DFS(2) called Vertex 2 finished Vertex 0 finished Process returned 0

* 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…**

- Traversing a Directed Graph through DFS recursively
- Traversing an Undirected Graph through DFS
- Traversing a directed graph through DFS
- DFS Algorithm for Connected Graph
- DFS Algorithm for Disconnected Graph

The post C Program for Traversing a Directed Graph through DFS recursively, with comments displayed in output appeared first on CodezClub.

]]>The post C Program for traversing a Directed Graph through DFS recursively appeared first on CodezClub.

]]>Write a C Program for traversing a Directed Graph through DFS recursively. Here’s simple C Program for traversing a Directed Graph through DFS recursively, visiting all the vertices.

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.

**Also Read : : C Program to implement BFS Algorithm for Connected Graph**

Below is the source code for C Program for traversing a Directed Graph through DFS recursively which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program for traversing a Directed Graph through DFS recursively */ #include<stdio.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; printf("\nEnter starting vertex for Depth First Search : "); scanf("%d",&v); DFS(v); for(v=0; v<n; v++) { if(state[v] == initial) DFS(v); } printf("\n"); }/*End of DF_Traversal()*/ void DFS(int v) { int i; printf("%d ",v); state[v] = visited; for(i=0; i<n; i++) { if(adj[v][i] == 1 && state[i] == initial) DFS(i); } 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; } }/*End of for*/ }/*End of create_graph()*/

/* C Program for traversing a Directed Graph through DFS recursively */ Enter number of vertices : 5 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 ) : 2 4 Enter edge 6( -1 -1 to quit ) : 4 3 Enter edge 7( -1 -1 to quit ) : -1 -1 Enter starting vertex for Depth First Search : 0 0 1 3 2 4 Process returned 0

* 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…**

- Traversing an Undirected Graph through DFS
- Traversing a directed graph through DFS
- DFS Algorithm for Connected Graph
- DFS Algorithm for Disconnected Graph
- BFS Algorithm for Connected Graph
- BFS Algorithm for Disconnected Graph

The post C Program for traversing a Directed Graph through DFS recursively appeared first on CodezClub.

]]>The post C Program for Traversing an Undirected Graph through DFS appeared first on CodezClub.

]]>Write a C Program for traversing an Undirected Graph through DFS. Here’s simple Program for traversing an Undirected graph through DFS, visiting all the vertices.

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.

**Also Read : : C Program to implement BFS Algorithm for Connected Graph**

Below is the source code for C Program for Traversing an Undirected Graph through DFS which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program for traversing an Undirected Graph through DFS */ #include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define visited 2 int n; /*Number of vertices in the graph */ int adj[MAX][MAX]; /*Adjacency Matrix*/ int state[MAX]; /*Can be initial or visited */ void DF_Traversal(); void DFS(int v); void create_graph(); int stack[MAX]; int top = -1; void push(int v); int pop(); int isEmpty_stack(); 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; printf("\nEnter starting vertex for Depth First Search : "); scanf("%d",&v); DFS(v); for(v=0; v<n; v++) { if(state[v] == initial) DFS(v); } printf("\n"); }/*End of DF_Traversal( )*/ void DFS(int v) { int i; push(v); while(!isEmpty_stack()) { v = pop(); if(state[v]==initial) { printf("%d ",v); state[v] = visited; } for(i=n-1; i>=0; i--) if(adj[v][i]==1 && state[i]==initial) push(i); } }/*End of DFS( )*/ void push(int v) { if(top == (MAX-1)) { printf("\nStack Overflow\n"); return; } top = top+1; stack[top] = v; }/*End of push()*/ int pop() { int v; if(top == -1) { printf("\nStack Underflow\n"); exit(1); } else { v = stack[top]; top = top-1; return v; } }/*End of pop()*/ int isEmpty_stack( ) { if(top == -1) return 1; else return 0; }/*End if isEmpty_stack()*/ void create_graph() { int i,max_edges,origin,destin; printf("\nEnter number of vertices : "); scanf("%d",&n); max_edges = n*(n-1)/2; 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; adj[destin][origin] = 1; } }/*End of for*/ }/*End if create_graph( )*/

/* C Program for traversing an Undirected Graph through DFS */ 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 4 Enter edge 7(-1 -1 to quit) : -1 -1 Enter starting vertex for Depth First Search : 0 0 1 3 4 2 5 Process returned 0

* 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…**

- Traversing a directed graph through DFS
- DFS Algorithm for Connected Graph
- DFS Algorithm for Disconnected Graph
- BFS Algorithm for Connected Graph
- BFS Algorithm for Disconnected Graph
- Connected Components in an Undirected Graph

The post C Program for Traversing an Undirected Graph through DFS appeared first on CodezClub.

]]>The post C Program for Traversing a directed graph through DFS, showing all tree edges and predecessors of all vertices appeared first on CodezClub.

]]>Write a C Program for Traversing a directed graph through DFS. Here’s simple Program for Traversing a directed graph through DFS, showing all tree edges and predecessors of all vertices in C Programming Language.

Depth First Search (DFS) algorithm traverses a graph in a depth ward 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.

**Also Read : : C Program to implement BFS Algorithm for Disconnected Graph**

Below is the source code for C Program for Traversing a directed graph through DFS which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program for Traversing a directed graph through DFS */ #include<stdio.h> #include<stdlib.h> #define MAX 100 #define NIL -1 #define initial 1 #define visited 2 int n; /* Number of vertices in the graph */ int adj[MAX][MAX]; /*Adjacency Matrix*/ int predecessor[MAX]; int state[MAX]; /*Can be initial or visited */ void DF_Traversal(); void DFS(int v); void create_graph(); int stack[MAX]; int top = -1; void push(int v); int pop(); int isEmpty_stack(); 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; predecessor[v] = NIL; } printf("\nEnter starting vertex for Depth First Search : "); scanf("%d",&v); DFS(v); for(v=0; v<n; v++) { if(state[v] == initial) DFS(v); } printf("\n"); for(v=0; v<n; v++) printf("\nVertex %d, Predecessor %d\n", v,predecessor[v]); printf("\nTree Edges : "); for(v=0; v<n; v++) { if(predecessor[v]!=-1) printf("\nTree edge : %d->%d\n", predecessor[v], v); } }/*End of DF_Traversal( )*/ void DFS(int v) { int i; push(v); while(!isEmpty_stack()) { v = pop(); if(state[v]==initial) { printf("%d ",v); state[v] = visited; } for(i=n-1; i>=0; i--) { if(adj[v][i]==1 && state[i]==initial) { push(i); predecessor[i] = v; } } } }/*End of DFS( )*/ void push(int v) { if(top == (MAX-1)) { printf("\nStack Overflow\n"); return; } top = top+1; stack[top] = v; }/*End of push()*/ int pop() { int v; if(top == -1) { printf("\nStack Underflow\n"); exit(1); } else { v = stack[top]; top = top-1; return v; } }/*End of pop()*/ int isEmpty_stack() { if(top == -1) return 1; else return 0; }/*End if isEmpty_stack()*/ 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; } } }

/* C Program for Traversing a directed graph through DFS */ 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 4 Enter edge 7( -1 -1 to quit ) : 4 5 Enter edge 8( -1 -1 to quit ) : -1 -1 Enter starting vertex for Depth First Search : 0 0 1 3 4 5 2 Vertex 0, Predecessor -1 Vertex 1, Predecessor 0 Vertex 2, Predecessor 0 Vertex 3, Predecessor 1 Vertex 4, Predecessor 3 Vertex 5, Predecessor 4 Tree Edges : Tree edge : 0->1 Tree edge : 0->2 Tree edge : 1->3 Tree edge : 3->4 Tree edge : 4->5 Process returned 0

* 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…**

- DFS Algorithm for Connected Graph
- DFS Algorithm for Disconnected Graph
- BFS Algorithm for Connected Graph
- BFS Algorithm for Disconnected Graph
- Connected Components in an Undirected Graph

The post C Program for Traversing a directed graph through DFS, showing all tree edges and predecessors of all vertices appeared first on CodezClub.

]]>The post C Program to implement DFS Algorithm for Disconnected Graph appeared first on CodezClub.

]]>Write a C Program to implement DFS Algorithm for Disconnected Graph. Here’s simple Program for traversing a directed graph through Depth First Search(DFS), visiting all the vertices from start vertex.

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.

**Also Read : : C Program to implement BFS Algorithm for Disconnected Graph**

Below is the source code for C Program to implement DFS Algorithm for Disconnected Graph which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program to implement DFS Algorithm for Disconnected Graph */ #include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define visited 2 int n; /*Number of vertices in the graph*/ int adj[MAX][MAX]; /*Adjacency Matrix*/ int state[MAX]; /*Can be initial or visited*/ void DF_Traversal(); void DFS(int v); void create_graph(); int stack[MAX]; int top = -1; void push(int v); int pop(); int isEmpty_stack(); main() { create_graph(); DF_Traversal(); }/*End of main()*/ void DF_Traversal() { int v; for(v=0; v<n; v++) state[v] = initial; printf("\nEnter starting vertex for Depth First Search : "); scanf("%d",&v); DFS(v); for(v=0; v<n; v++) { if(state[v] == initial) DFS(v); } printf("\n"); }/*End of DF_Traversal( )*/ void DFS(int v) { int i; push(v); while(!isEmpty_stack()) { v = pop(); if(state[v]==initial) { printf("%d ",v); state[v] = visited; } for(i=n-1; i>=0; i--) if(adj[v][i]==1 && state[i]==initial) push(i); } }/*End of DFS( )*/ void push(int v) { if(top == (MAX-1)) { printf("\nStack Overflow\n"); return; } top = top+1; stack[top] = v; }/*End of push()*/ int pop() { int v; if(top == -1) { printf("\nStack Underflow\n"); exit(1); } else { v = stack[top]; top = top-1; return v; } }/*End of pop()*/ int isEmpty_stack( ) { if( top == -1) return 1; else return 0; }/*End if isEmpty_stack()*/ 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; } } }/*End of create_graph*/

/* C Program to implement DFS Algorithm for Disconnected Graph */ 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 ) : 4 2 Enter edge 7( -1 -1 to quit ) : 5 5 Enter edge 8( -1 -1 to quit ) : -1 -1 Enter starting vertex for Depth First Search : 0 0 1 3 4 2 5 Process returned 0

* 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…**

- DFS Algorithm for Connected Graph
- BFS Algorithm for Connected Graph
- BFS Algorithm for Disconnected Graph
- Connected Components in an Undirected Graph
- Path Matrix by Warshall’s Algorithm
- Path Matrix by powers of Adjacency matrix

The post C Program to implement DFS Algorithm for Disconnected Graph appeared first on CodezClub.

]]>The post C Program to implement DFS Algorithm for Connected Graph appeared first on CodezClub.

]]>Write a C Program to implement DFS Algorithm for Connected Graph. Here’s simple Program for traversing a directed graph through Depth First Search(DFS), visiting only those vertices that are reachable from start vertex.

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.

**Also Read : : C Program to implement BFS Algorithm for Connected Graph**

Below is the source code for C Program to implement DFS Algorithm for Connected Graph which is successfully compiled and run on Windows System to produce desired output as shown below :

/* C Program to implement DFS Algorithm for Connected Graph */ #include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define visited 2 int n; /* Number of nodes in the graph */ int adj[MAX][MAX]; /*Adjacency Matrix*/ int state[MAX]; /*Can be initial or visited */ void DF_Traversal(); void DFS(int v); void create_graph(); int stack[MAX]; int top = -1; void push(int v); int pop(); int isEmpty_stack(); main() { create_graph(); DF_Traversal(); }/*End of main()*/ void DF_Traversal() { int v; for(v=0; v<n; v++) state[v]=initial; printf("\nEnter starting node for Depth First Search : "); scanf("%d",&v); DFS(v); printf("\n"); }/*End of DF_Traversal( )*/ void DFS(int v) { int i; push(v); while(!isEmpty_stack()) { v = pop(); if(state[v]==initial) { printf("%d ",v); state[v]=visited; } for(i=n-1; i>=0; i--) { if(adj[v][i]==1 && state[i]==initial) push(i); } } }/*End of DFS( )*/ void push(int v) { if(top == (MAX-1)) { printf("\nStack Overflow\n"); return; } top=top+1; stack[top] = v; }/*End of push()*/ int pop() { int v; if(top == -1) { printf("\nStack Underflow\n"); exit(1); } else { v = stack[top]; top=top-1; return v; } }/*End of pop()*/ int isEmpty_stack( ) { if(top == -1) return 1; else return 0; }/*End if isEmpty_stack()*/ void create_graph() { int i,max_edges,origin,destin; printf("\nEnter number of nodes : "); 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; } } }

/* C Program to implement DFS Algorithm for Connected Graph */ Enter number of nodes : 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 ) : 4 2 Enter edge 7( -1 -1 to quit ) : 5 5 Enter edge 8( -1 -1 to quit ) : -1 -1 Enter starting node for Depth First Search : 0 0 1 3 4 2 Process returned 0

* 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…**

- BFS Algorithm for Connected Graph
- BFS Algorithm for Disconnected Graph
- Connected Components in an Undirected Graph
- Path Matrix by Warshall’s Algorithm
- Path Matrix by powers of Adjacency matrix

The post C Program to implement DFS Algorithm for Connected Graph appeared first on CodezClub.

]]>