Depth First Search

ALGORITHM DFS(G)

//Implements a depth-first search traversal of a given graph
//Input: GraphG = V , E//Output: Graph G with its vertices marked with consecutive integers
// in the order they are first encountered by the DFS traversal
mark each vertex inV with 0 as a mark of being “unvisited”

count ← 0

for each vertex v in V do
if v is marked with 0

DFS(v)


DFS(v)//visits recursively all the unvisited vertices connected to vertex v

//by a path and numbers them in the order they are encountered
//via global variable count
count← count + 1; mark v with count

for each vertex w in V adjacent to v do
if w is marked with 0


DFS(w) 

C program:

#include<stdio.h>

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

void dfs(int v)

{

   int i;

   reach[v]=1;

   for (i=0;i<n;i++)

    if (a[v][i]&&!reach[i])

     {

      printf("\n %d->%d",v,i);

      dfs(i);

     }

}

int main()

{

  int i,j,count=0;

  printf("Enter The Number OF Vertices\n");

  scanf("%d",&n);

  for (i=0;i<n;i++)

  {

    reach[i]=0;

    for (j=0;j<n;j++)

    {

      a[i][j]=0;

    }

  }

  printf("Enter The Adjacency Matrix\n");

  for (i=0;i<n;i++)

    for (j=0;j<n;j++)

{

printf("\nEnter connection bt vertex %c & vertex %c",i+65,j+65);

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

}

  dfs(0);

  printf("\n");

 for (i=0;i<n;i++)

 {

   if (reach[i])

    count++;

 }

  if (count==n)

   printf("The Graph is connected\n");

  else

  printf("The Graph is not Connected\n");

 return 0;

}

Output:

Enter The Number OF Vertices

5

Enter The Adjacency Matrix

Enter connection bt vertex A & vertex A0

Enter connection bt vertex A & vertex B1

Enter connection bt vertex A & vertex C0

Enter connection bt vertex A & vertex D0

Enter connection bt vertex A & vertex E1

Enter connection bt vertex B & vertex A1

Enter connection bt vertex B & vertex B0

Enter connection bt vertex B & vertex C1

Enter connection bt vertex B & vertex D0

Enter connection bt vertex B & vertex E0

Enter connection bt vertex C & vertex A0

Enter connection bt vertex C & vertex B1

Enter connection bt vertex C & vertex C0

Enter connection bt vertex C & vertex D1

Enter connection bt vertex C & vertex E0

Enter connection bt vertex D & vertex A0

Enter connection bt vertex D & vertex B0

Enter connection bt vertex D & vertex C1

Enter connection bt vertex D & vertex D0

Enter connection bt vertex D & vertex E1

Enter connection bt vertex E & vertex A1

Enter connection bt vertex E & vertex B0

Enter connection bt vertex E & vertex C0

Enter connection bt vertex E & vertex D1

Enter connection bt vertex E & vertex E0

 0->1

 1->2

 2->3

 3->4

The Graph is connected