Topological Sort in C and C++

Here you will learn and get program for topological sort in C and C++.

We know many sorting algorithms used to sort the given data. It may be numeric data or strings. Take a situation that our data items have relation. They are related with some condition that one should happen only after other one happened.

For example shoe should wear after socks only. Another example, in academic course one should study Applications of Algorithms subject only after studying Designing of Algorithms. And Designing of Algorithms should study only after learning any programming language. We can observe that a work requires pre-requisite. In these situations we represent our data in a graph and we use directed edges from pre-requisite to next one. And we apply Topological sorting to solve.

Most important condition to do Topological sorting on any graph is that Graph should be Connected Directed Acyclic graph. It is not possible to apply Topological sorting either graph is not directed or it have a Cycle.

One more condition is that graph should contain a sink vertex. The vertex which doesn’t have any outgoing edge is called sink vertex. Idea behind this sink vertex is that if every vertex has an outgoing edge in a directed graph it definitely forms a cycle, which violates the condition.

Note: Topological sorting on a graph results non-unique solution

Topological Sort Example

Solving Using In-degree Method

Step 1: Write in-degree of all vertices:

Vertex	in-degree
1	0
2	1
3	1
4	2

Step 2: Write the vertex which has in-degree 0 (zero) in solution. Here vertex 1 has in-degree 0. So,

Solution is: 1 -> (not yet completed )

Decrease in-degree count of vertices who are adjacent to the vertex which recently added to the solution.

Here vertex 1 is recently added to the solution. Vertices 2 and 3 are adjacent to vertex 1. So decrease the in-degree count of those and update.

Updated result is:

Vertex	in-degree
1	Already added to solution
2	0
3	0
4	2

Again repeat the same thing which we have done in step1 that, write the vertices which have degree 0 in solution.

Here we can observe that two vertices (2 and 3) have in-degree 0 (zero). Add any vertex into the solution.

Note that, you may add vertex 2 into solution, and I may add vertex 3 to solution. That means the solution to topological sorting is not unique.

Now add vertex 3.

Solution is: 1->3->

Again decrease the in-degree count of vertices which are adjacent to vertex 3.

Updated result is:

Vertex	in-degree
1	Already added to solution
2	0
3	Already added to solution
4	1

Now add vertex 2 to solution because it only has in-degree 0.

Solution is: 1->3->2->

Updated result is:

Vertex	in-degree
1	Already added to solution
2	Already added to solution
3	Already added to solution
4	0

Finally add 4 to solution.

Final solution is: 1->3->2->4

Program for Topological Sort in C

#include <stdio.h>

int main(){
	int i,j,k,n,a[10][10],indeg[10],flag[10],count=0;

	printf("Enter the no of vertices:\n");
	scanf("%d",&n);

	printf("Enter the adjacency matrix:\n");
	for(i=0;i<n;i++){
		printf("Enter row %d\n",i+1);
		for(j=0;j<n;j++)
			scanf("%d",&a[i][j]);
	}

	for(i=0;i<n;i++){
        indeg[i]=0;
        flag[i]=0;
    }

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            indeg[i]=indeg[i]+a[j][i];

    printf("\nThe topological order is:");

    while(count<n){
        for(k=0;k<n;k++){
            if((indeg[k]==0) && (flag[k]==0)){
                printf("%d ",(k+1));
                flag [k]=1;
            }

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

        count++;
    }

    return 0;
}

Output

Enter the no of vertices:
4
Enter the adjacency matrix:
Enter row 1
0 1 1 0
Enter row 2
0 0 0 1
Enter row 3
0 0 0 1
Enter row 4
0 0 0 0

The topological order is:1 2 3 4

Program for Topological Sort in C++

#include<iostream>

using namespace std;

int main(){
	int i,j,k,n,a[10][10],indeg[10],flag[10],count=0;

	cout<<"Enter the no of vertices:\n";
	cin>>n;

	cout<<"Enter the adjacency matrix:\n";
	for(i=0;i<n;i++){
		cout<<"Enter row "<<i+1<<"\n";
		for(j=0;j<n;j++)
			cin>>a[i][j];
	}

	for(i=0;i<n;i++){
        indeg[i]=0;
        flag[i]=0;
    }

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            indeg[i]=indeg[i]+a[j][i];

    cout<<"\nThe topological order is:";

    while(count<n){
        for(k=0;k<n;k++){
            if((indeg[k]==0) && (flag[k]==0)){
                cout<<k+1<<" ";
                flag[k]=1;
            }

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

        count++;
    }

    return 0;
}

Comment below if you have any queries related to above program for topological sort in C and C++.