C Program: Topological Sorting With Sample Program

0
1685

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.

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-1Fill 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.

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.

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

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.

Output screens for topological sorting C program

c-program-topological-sorting-with-sample-program-2 c-program-topological-sorting-with-sample-program-1

Download C Program: Topological Sorting code

Save

LEAVE A REPLY

Please enter your comment!
Please enter your name here