Topological Sort using Dfs

Topological Sort using Dfs

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])
     {

      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("\nPop out order ");
 for (i=n-1;i>=0;i--)
 {
   if (reach[i])
    printf("%d\t",i);
 }

 for (i=n-1;i>=0;i--)
 {
   if (reach[i]==0)
    printf("\n%d",i);
 }

return 0;
}

Output:

Enter The Number OF Vertices
4
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 B & vertex A0

Enter connection bt vertex B & vertex B0

Enter connection bt vertex B & vertex C0

Enter connection bt vertex B & vertex D1

Enter connection bt vertex C & vertex A0

Enter connection bt vertex C & vertex B0

Enter connection bt vertex C & vertex C0

Enter connection bt vertex C & vertex D0

Enter connection bt vertex D & vertex A1

Enter connection bt vertex D & vertex B0

Enter connection bt vertex D & vertex C1

Enter connection bt vertex D & vertex D0

Pop out order 3  2  1  0

Read More