C Program: Topological Sorting With Sample Program

Last updated: September 4, 2016 10:26 am

CWC

4 Min Read

Sorting is the technique by which arrangement of data is done. Topological sorting is also the same but is performed in case of directed graphs , For example if there are two vertices a and b and the edge is directing from a to b so a will come before b in the sorted list.

Contents

What is adjacent matrix for the directed graph?Output screens for topological sorting C program Download C Program: Topological Sorting code Click here to donload source code CodeWithC-Topological-Sorting

We begin the code with header files “stdio.h” “conio.h” “math.h”

For topological sort to perform we need to find adjacent matrix.

What is adjacent matrix for the directed graph?

We have below matrix

C-program-Topological-sorting-with-example-code

In the above figure, we need to find the adjacent matrix so we need to take a matrix of 4*4 like this,

C-program-Topological-sorting-with-example-code-1 Fill the matrix with 1 and 0 , fill 1 in the place where a vertice is directing towards other vertice and 0 at every other left cell. Vertices in rows would be taken as the ones directing and vertices in columns will be taken as the ones which are getting directed at.

Taking the above figure, A is directing towards B and C, similarly C is directing towards D and D is directing towards B. so fill it up

C-program-Topological-sorting-with-example-code-2

Fill when asked.

printf("ENTER THE ADJACENT MATRIX\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&am[i][j]);

Now we take two array y[] and z[] and make it zero. Array y[] is used to count up 1’s in the columns .

Then a while loop is set to make the loop run the number of times as number of vertices present in the program.

Then it is checked if the added column is equal to zero if it is not zero then the loop is repeated with incrementing ‘k’ but in case it is zero which means it isn’t directing towards any letter so it is printed on the output screen and thus it means that it is removed from the graph so it is now not directing towards any other letter, thus it is reduced from the table that is if ‘a’ is removed from the figure so now it is not pointing towards b or c so both 1 will be replaced with a 0.

for(i=0;i<n;i++)
{
if(am[k][i]==1)
am[k][i]=am[k][i]-1;
}

And now again array y[] is made zero and the columns are added up and stored in array y[] and the loop is continues . Array z[] is used to avoid duplicacy , as in case that a letter is not printed twice as it makes the value of array z[k]=1 and it only prints if z[k]=0

printf("\n%d\n",k);
z[k]=1;

I have used a finite number of vertices and I have taken numbers instead of letters as vertices. Most important thing to solve topological sort is to make a adjacent matrix and understand the logic.