c program on the depth first search (dfs ) of the graph

Algorithm:-

                    It work on stack.

      Step 1. Initialize all the vertex to the Ready state.

      Step 2. PUSH the starting vertex onto stack and change it’s status to the working state.

      Step 3. Repeat Step 4 and Step 5 until stack is empty.

      Step 4. POP the Top vertex ‘n’ and process n and change it’s status to the processed state.

      Step 5. PUSH onto stack all the neighbours of the vertex ‘n’ . that are still in ready state                           and change their status to the waiting state.

Code:-

#include<stdio.h>
int stack[20];
int top=-1;

// FUNCTION FOR PUSH THE ELEMENT IN TO STACK
void push(int a)
{
top++;
stack[top]=a;
}

// function for pop the element fron the stack
int pop()
{
int a;
if(top==-1)
return 0;
else
{
a=stack[top];
top–;
return a;
}
}

int main()
{
int n,graph[10][10],visited[10]={0},i,j,flag=0,ans[10],k=0,a;
printf(“Enter number of vertex in the graphn”);
scanf(“%d”,&n);
printf(“Enter the graph in form of adjacency matrixn”);
for( i=1;i<=n;i++)
{
    for( j=1;j<=n;j++)
     scanf(“%d”,&graph[i][j]);
}

// logic for DFS

i=1;
while(i!=0)
{
     if(visited[i]==0)
     {
     ans[k]=i;
     k++;
     }
     visited[i]=1;
     flag=0;
     for( j=1;j<=n;j++)
     {
     if(visited[i]!=0)
     {
         if(graph[i][j]!=0)
         {
         flag=1;
         // if vertex is not visited then push it into stack
         if(visited[j]==0)
         push(j);
         }
     }
}
// if there is no edge from vertex then
     if(flag==0)
     {
     a=i;
         while(1)
         {
         a++;
        
         // if any edge from a to i then
         if(graph[a][i]==1)
         {
             push(a);
             break;
         }
         }
     }
     i=pop();

}
// printing the ans
printf(“Traversal is:-n”);
for(i=0 ;i<k;i++)
printf(“%d “,ans[i]);
return 0;
}

Output:-

Enter number of vertex in the graph
6
Enter the graph in form of adjacency matrix
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
0 1 0 0 1 0

Traversal is:-
1 2 4 6 5 3




Leave a Reply

Your email address will not be published.