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

Topological Sort in C and C++

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++.

 

14 thoughts on “Topological Sort in C and C++”

  1. Question, shouldn’t the following code must be inside the “if((indeg[k]==0) &&..” condition?
    for(i=0;i<n;i++){
    if(a[i][k]==1)
    indeg[k]–;
    }

    1. 0 0 0 0 0 0
      0 0 0 0 0 0
      0 0 0 1 0 0
      0 1 0 0 0 0
      1 1 0 0 0 0
      1 0 1 0 0 0

      For this adjacency matrix, I am getting a wrong output.

    1. Sorry to prove you wrong but I just traced your input in the program and got the result as the following
      5,6,1,3,4,2 which is correct when you refer your DAG.

  2. General design is good, but to make the code right,we must remove the last for. Then we must put a for loop inside the if loop.This loop will be like:

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

  3. 1 2 3 4 5 6
    1 0 0 0 0 0 1
    2 1 0 0 0 0 0
    3 0 0 0 0 0 0
    4 0 1 1 0 0 0
    5 0 0 1 0 0 1
    6 0 0 0 0 0 0

    this code didnt give me a correct answer when i input these matrix

    1. that’s because you use an adjacency matrix to run the program. This type of matrix contains only 1 and 0 elements. You can create an adjacency matrix on a paper by looking at an oriented graph.

    2. i think this one is working

      #include

      #include

      int g[10][10]={0},flag[10],indeg[10],n,count=0;

      int main()
      {
      printf(“enter the value of n\n”);
      scanf(“%d”,&n);

      int i,j,k;

      printf(“enter the matrix\n”);
      for(i=0;i<n;i++)
      {
      for(j=0;j<n;j++)
      {scanf("%d",&g[i][j]);}
      }

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

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

      while(count<n)
      {
      for(i=0;i”,i+1);
      flag[i]=1;
      }

      for(j=0;j<n;j++)
      {
      if(g[j][i]==1&&flag[i]==0)//<————————————-
      {
      indeg[i]–;
      break; //<—————————————————–
      }
      }
      }
      count++;
      }
      return 0;
      }

  4. wrong output for the below input:
    Enter the no of vertices:
    6
    Enter the adjacency matrix
    Enter row 1
    0 0 0 0 1 1
    Enter row 2
    0 0 0 1 1 0
    Enter row 3
    0 0 0 0 0 1
    Enter row 4
    0 0 1 0 0 0
    Enter row 5
    0 0 0 0 0 0
    Enter row 6
    0 0 0 0 0 0
    The topological order is: 1 2 3 4 5 6

  5. Siddharth Dwivedi

    The Corrected code is:

    #include

    using namespace std;

    int main() {
    int i, j, k, n;
    cout <> n;

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

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

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

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

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

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

    return 0;
    }

Leave a Comment

Your email address will not be published. Required fields are marked *