Topological Sort in C and C++

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

We know many sorting calculations used to sort the given information. It might be numeric information or strings.

Take the circumstance that our information things have a connection. They are connected with some condition

that one ought to happen simply after the other one occurred.

For instance, the shoe should wear after socks as they were. Another model, in scholastic course one should think about

Applications of Algorithms subject simply subsequent to examining Designing of Algorithms.

Furthermore, Designing of Algorithms should ponder simply in the wake of adapting any programming language.

We can see that work requires pre-imperative. In these circumstances, we speak to our information in a diagram

and we utilize guided edges from pre-essential to next one. What’s more, we apply Topological sorting to settle.

Most significant condition to do Topological sorting on any diagram is that Graph ought to be Connected Directed Acyclic chart.

It is beyond the realm of imagination to expect to apply Topological sorting either diagram isn’t coordinated or it has a Cycle.

One more condition is that diagram ought to contain a sink vertex.

The vertex which doesn’t have any cordial edge is called sink vertex. Thought behind this sink vertex is that if each vertex has an active edge in a coordinated

chart it unquestionably shapes a cycle, which disregards the condition.

Note: Topological sorting on a diagram results non-novel solution

Stage 1: Write in-degree of all vertices:

Fathoming Using In-degree Method

Stage 2: Write the vertex which has in-degree 0 (zero) in solution. Here vertex 1 has in-degree 0. Along these lines,

Solution is: 1 – > (not yet finished )

Decline in-degree tally of vertices who are adjoining the vertex which as of late added to the solution.

Here vertex 1 is as of late added to the solution. Vertices 2 and 3 are adjoining vertex 1.

To decline them an in-degree check of those and update.

The refreshed result is:

Again rehash something very similar which we have done in step1 that, compose the vertices which have degree 0 in solution.

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

Note that, you may include vertex 2 into solution, and I may add vertex 3 to the solution.

That implies the solution to topological sorting isn’t extraordinary.

Presently include vertex 3.

Solution is: 1->3->

Again decline the in-degree tally of vertices which are contiguous vertex 3.

The refreshed result is:

Presently add vertex 2 to the solution since it just has in-degree 0.

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

Refreshed result is:

At last, add 4 to the solution.

Last 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;
}

Remark underneath in the event that you have any inquiries identified with above program for topological sort in C and C++.