C program for dfs (depth first search)

c program for dfs(depth first search) using array. DFS is Depht first Search, which is used to traverse un-weighted Graph.  There are two most popular graph traversing technique, i.e DFS and BFS. DFs make use of Stack while, BFS make use data structure Queue. Also see c program for bfs.

C program for dfs

#include<stdio.h>
#include<conio.h>

char stack[20];
int top=-1, n;
char arr[20];
char dfs(int );
char ajMat[20][20];
char b[20];
void display();
int p=0;

int main()
{
    char v;
    int l=0;
    printf("Enter the number of nodes in a graph");
    scanf("%d",&n);
    printf("Enter the value of node of graph");
    for(int i=0; i<n; i++)
    {
        scanf("%s",&b[i]);
    }
    char k=b[0];
    printf("Enter the value in adjancency matrix in from of 'Y' or 'N'\n");
    printf("\nIf there is an edge between the two vertices then enter 'Y' or 'N'\n");
    for(int i=0; i<n; i++)
    printf(" %c ",b[i]);
    for(int i=0;i<n; i++)
    {
         printf("\n%c ",b[i]);
         for(int j=0; j<n; j++)
         {
              printf("%c ",v=getch());
              ajMat[i][j]=v;
         }
         printf("\n\n");
    }
    for(int i=0;i<n;i++)
    {
         l=0;
         while(k!=b[l])
         l++;
         k=dfs(l);
    }
    display();
    getch();
}

void display()
{
     printf(" DFS of Graph : ");
     for(int i=0; i<n; i++)
     printf("%c ",arr[i]);
}
void push(char val)
{
     top=top+1;
     stack[top]=val;
}
char pop()
{
     return stack[top];
}

bool unVisit(char val)
{
      for(int i=0; i<p; i++)
      if(val==arr[i])
      return false;
      for(int i=0; i<=top; i++)
      if(val==stack[top])
      return false;
      return true;
}

char dfs(int i)
{
     int k;
     char m;
     if(top==-1)
     {
          push(b[i]);
     }
     m=pop();
     top--;
     arr[p]=m;
     p++;
     for(int j=0; j<n; j++)
     {
          if(ajMat[i][j]=='y')
          {
               if(unVisit(b[j]))
               {
                     push(b[j]);
               }
          }
     }
    return stack[top];
}

Here is the Graph for below output :

C program for dfs
C program for dfs

Output of C program for dfs:

C program for dfs
C program for dfs

One thought on “C program for dfs (depth first search)”

Add Comment Register



Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>