Lab program 3a: Obtain the Topological ordering of vertices in a given digraph.

Description:

Topological sort is an ordering of the vertices in a directed acyclic graph, such that, if there is a path from u to v, then v appears after u in the ordering.

The graphs should be directed: otherwise for any edge (u,v) there would be a path from u to v and also from v to u, and hence they cannot be ordered.

The graphs should be acyclic: otherwise for any two vertices u and v on a cycle u would precede v and v would precede u.

Using Source Removal algorithm:

1. Compute the indegrees of all vertices
2. Find a vertex U with indegree 0 and print it (store it in the ordering)
3. If there is no such vertex then there is a cycle and the vertices cannot be ordered. Stop.
4. Remove U and all its edges (U,V) from the graph.
5. Update the indegrees of the remaining vertices.
6. Repeat steps 2 through 4 while there are vertices to be processed.

Solution:

  #include<stdio.h>

   int temp[10],k=0;

  

void topo(int n,int indegree[10],int a[10][10])

   {

   int i,j;

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

     {

               if(indegree[i]==0)

                {

                indegree[i]=1;

                  temp[++k]=i;

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

                           {

                            if(a[i][j]==1&&indegree[j]!=-1)

                             indegree[j]--;

                           }

                           i=0;

                  }

       }

   }

  void main()

   {

   int i,j,n,indegree[10],a[10][10];

   printf("enter the number of vertices:");

   scanf("%d",&n);

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

   indegree[i]=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]);

      if(a[i][j]==1)

      indegree[j]++;

   }

   topo(n,indegree,a);

   if(k!=n)

   printf("topological ordering is not possible\n");

 

else

   {

      printf("\n topological ordering is :\n");

      for(i=1;i<=k;i++)

      printf("v%d\t",temp[i]);

    }

  }

Using DFS algorithm:

1. Run DFS(G), computing finish time for each vertex
2. As each vertex is finished, insert it onto the front of a list

Solution:

#include<stdio.h>

int i,visit[20],n,adj[20][20],s,topo_order[10];

void dfs(int v)

{

  int w;

  visit[v]=1;

  for(w=1;w<=n;w++)

    if((adj[v][w]==1) && (visit[w]==0))

      dfs(w);

  topo_order[i--]=v;

}

void main()

{

  int v,w;

  printf("Enter the number of vertices:\n");

  scanf("%d",&n);

  printf("Enter the adjacency matrix:\n");

  for(v=1;v<=n;v++)

    for(w=1;w<=n;w++)

      scanf("%d",&adj[v][w]);

  for(v=1;v<=n;v++)

      visit[v]=0;

  i=n;

  for(v=1;v<=n;v++)

  {

   if(visit[v]==0)

      dfs(v);

  }

  printf("\nTopological sorting is:");

  for(v=1;v<=n;v++)

     printf("v%d ",topo_order[v]);

}

  

OUTPUT 1 :

Enter the number of vertices:

5

Enter the adjacency matrix

0 0 1 0 0

0 0 1 0 0

0 0 0 1 1

0 0 0 0 1

0 0 0 0 0

Topological ordering is v1 v2 v3 v4 v5

OUTPUT 2 :

enter the number of vertices:

3

Enter the adjacency matrix

0 1 0

0 0 1

1 0 0

Topological ordering is not possible