C program to implement Depth First Search

Here is a simple C program to implement Depth First Search is given below.Depth-first search is an algorithm for traversing or searching tree or graph data structures. One starts at the root and explores as far as possible along each branch before backtracking.

C program to implement Depth First Search

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

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

void dfs(int v)
{
 int i;
 reach[v]=1;
 for(i=1;i<=n;i++)
 if(a[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++)
  a[i][j]=0;
 }
 printf("n Enter the adjacency matrix:n");
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  scanf("%d",&a[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();
}