DFS algorithm introduction and implementation in C language

DFS algorithm:-

The full form of DFS is Depth first search. It is a graph traversal algorithm that starts with the starting or initial node of the graph and then goes to the next reachable node(neighbor) until we find the ending or last node or the node which has no neighbors. DFS is similar to BFS algorithm and it uses Stack data structure.

डी.एफ.एस. का पूरा नाम डेप्थ फर्स्ट सर्च है। यह एक ग्राफ ट्रेवर्सल अल्गोरिथम है जिसमे प्रारंभिक नोड से ग्राफ को ट्रेवर्स किया जाता है इसके पश्चात् सभी पहुचने योग्य (पडोसी) नोड्स को विजिट किया जाता है। यह प्रक्रिया सभी नोड्स पर तब तक चलती रहती है जब तक कि या तो अंतिम नोड या वह नोड जिसके कोई पडोसी नोड नहीं है प्राप्त नहीं हो जाता। डी.एफ.एस अल्गोरिथम बी.एफ.एस.के सामान ही होती है एवं यह.अल्गोरिथम स्टैक डाटा स्ट्रक्चर का प्रयोग करती है।       

Steps of DFS Algorithm(डी.एफ.एस. अल्गोरिथम के चरण ):-

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Push the starting node A on to the stack and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until Stack is empty

Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)

Step 5: Push all the neighbors of N on to the stack that are in the ready state (whose STATUS = 1) and set their STATUS = 2 (waiting state)

Step 6: EXIT

Consider following Graph/tree:-

निम्न ग्राफ को देखते है :-

C Program for DFS algorithm:-

#include<stdio.h>

#include<conio.h>

int graph[20][20],reach[20],n;

void dfs(int v){

 int i;

 reach[v]=1;

 for(i=1;i<=n;i++){

 if(graph[v][i] && !reach[i])

 {

  printf("\n %d->%d",v,i);

  dfs(i);

 }}

}

void main(){

 int i,j,count=0;

 clrscr();

 printf("\n Enter number of vertices:");

 scanf("%d",&n);

 for(i=1;i<=n;i++)

 {

  reach[i]=0;

  for(j=1;j<=n;j++)

   graph[i][j]=0;

 }

 printf("\n Enter the adjacency matrix:\n");

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

   scanf("%d",&graph[i][j]);

 dfs(1);

 printf("\n");

 for(i=1;i<=n;i++)

 {

  if(reach[i])

   count++;

 }

 if(count==n)

  printf("\n Graph is connected");

 else

  printf("\n Graph is not connected");

 getch();

}