DFS

Program To Implement Depth First Search(DFS)

     Algorithm:

1. Place the starting node s on the top of the stack.
2. If the stack is empty, return failure and stop.
3. If the element on the stack is goal node g, return success and stop. Otherwise,
4. Remove and expand the first element , and place the children at the top of the stack.
5. Return to step 2.
   
   
                            Example

   

   
   

   Source Code

   
   

   #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();

   }