Program for implementing Depth First Search

/* Depth first search algorithm extends the current path as far as possible before backtracking to the lastchoice point and trying the next alternative path. Depth first search may fail to find a solution if it enters acycle in the graph. This can be avoided if we never extend a path to a node which it already contains.*/

#include<stdio.h>

#include<conio.h>

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

void dfs(int v)

{

 int i;

Also Read : Program for implementing Breadth First Search

 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 \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 End”);

 else

  printf(“\n Graph is not connected”);

 getch();

 }

Output:

depth_first_search

 

Mohit Arora
Follow me