*DFS Algorithm for Connected Graph*

*DFS Algorithm for Connected Graph*

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.

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

**SOURCE CODE : :**

**SOURCE CODE : :**

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

**OUTPUT : :**

**OUTPUT : :**

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

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

- 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

can you explain ??

both are same .its your choice .our aim is to chose any unvisited adjacent node of current node