DEPTH-FIRST TRAVERSAL

Program

#include <stdio.h>
#define max 10

/* a function to build adjacency matrix of a graph */
void buildadjm(int adj[][max], int n)
   {
     int i,j;
     for(i=0;i<n;i++)
         for(j=0;j<n;j++)
          {
     printf("enter 1 if there is an edge from %d to %d, otherwise enter
0 \n",
   i,j);

            scanf("%d",&adj[i][j]);
            }
      }

/* a function to visit the nodes in a depth-first order */
void dfs(int x,int visited[],int adj[][max],int n)
{
   int j;
   visited[x] = 1;
   printf("The node visited id %d\n",x);
   for(j=0;j<n;j++)
      if(adj[x][j] ==1 && visited[j] ==0)
           dfs(j,visited,adj,n);
}
void main()
   {
      int adj[max][max],node,n;
      int i, visited[max];
      printf("enter the number of nodes in graph maximum = %d\n",max);
      scanf("%d",&n);
      buildadjm(adj,n);
      for(i=0; i<n; i++)
        visited[i] =0;
      for(i=0; i<n; i++)
       if(visited[i] ==0)
            dfs(i,visited,adj,n);
      }

Explanation

1. Initially, all the elements of an array named visited are set to 0 to indicate that all the vertices are unvisited.
2. The traversal starts with the first vertex (that is, vertex 0), and marks it visited by setting visited[0] to 1. It then considers one of the unvisited vertices adjacent to it and marks it visited, then repeats the process by considering one of its unvisited adjacent vertices.
3. Therefore, if the following adjacency matrix that represents the graph of Figure 22.9 is given as input, the order in which the nodes are visited is given here:
   • Input: 1. The number of nodes in a graph
     2. Information about edges, in the form of values to be stored in adjacency matrix 1 if there is an edge from node i to node j, 0 otherwise
   • Output: Depth-first ordering of the nodes of the graph starting from the initial vertex, which is vertex 0, in our case