Topological Sort-Java

In the field of computer science, a topological sort (sometimes abbreviated toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).

Read More

Code

Java Code

import java.util.*;
public class Topological {

public static void main(String[] args) {
int vnos;
System.out.println("Topological Sort");
System.out.println("Enter the number of vertices");
Scanner sc = new Scanner(System.in);
vnos=sc.nextInt();
Graph a=new Graph(vnos);
sc.close();
}

}
class Graph {

int vnos; //number of vertices
int g[][]; //adjacency matrix for graph
int indegree[];

Graph(int vnos) { //constructor
indegree=new int[vnos];
g=new int[vnos][vnos];
this.vnos = vnos;
read();
System.out.println("The entered graph is as follows");
printg();
System.out.println("The topological sort is as follows");
topo();
}

void read() { //to read the cost adjacency matrix and initialize it

int i, j;
System.out.println("Enter the adjacency matrix for the graph");
for(i=0;i<=vnos-1;i++){
for(j=0;j<=vnos-1;j++){
if(i==j){
g[i][i]=0;
continue;
}
System.out.println("Enter the value for edge"+i+","+j);
Scanner sc = new Scanner(System.in);
g[i][j]=sc.nextInt();
if(g[i][j]==1){
indegree[j]++;
}
}
}

}
void printg() { //to print the graph
int i, j;
for (i = 0; i <= vnos - 1; i++) {
for (j = 0; j <= vnos - 1; j++) {

System.out.print(g[i][j]+"\t");
}
System.out.println();

}
}

void topo(){
int count=0;
int i;
int v;
while(count<vnos){
v=-1;
for(i=0;i<=vnos-1;i++){
if(indegree[i]==0){
v=i;
indegree[v]=-1;
break;
}
}
if(v==-1){
System.out.println("All tasks cannot be completed");
return;
}
System.out.println(v);
for(i=0;i<=vnos-1;i++){
if(g[v][i]==1){
//cout<<"indegree of the vertex "<<indegree[i]<<endl;
indegree[i]--;
//cout<<"now it is "<<indegree[i]<<endl;
}
}

count++;
}

}
};

Output

Topological Sort
Enter the number of vertices
7
Enter the adjacency matrix for the graph
Enter the value for edge0,1
1
Enter the value for edge0,2
1
Enter the value for edge0,3
1
Enter the value for edge0,4
0
Enter the value for edge0,5
0
Enter the value for edge0,6
0
Enter the value for edge1,0
0
Enter the value for edge1,2
0
Enter the value for edge1,3
0
Enter the value for edge1,4
1
Enter the value for edge1,5
0
Enter the value for edge1,6
0
Enter the value for edge2,0
0
Enter the value for edge2,1
0
Enter the value for edge2,3
0
Enter the value for edge2,4
0
Enter the value for edge2,5
1
Enter the value for edge2,6
0
Enter the value for edge3,0
0
Enter the value for edge3,1
0
Enter the value for edge3,2
0
Enter the value for edge3,4
0
Enter the value for edge3,5
1
Enter the value for edge3,6
0
Enter the value for edge4,0
0
Enter the value for edge4,1
0
Enter the value for edge4,2
0
Enter the value for edge4,3
1
Enter the value for edge4,5
0
Enter the value for edge4,6
1
Enter the value for edge5,0
0
Enter the value for edge5,1
0
Enter the value for edge5,2
0
Enter the value for edge5,3
0
Enter the value for edge5,4
0
Enter the value for edge5,6
1
Enter the value for edge6,0
0
Enter the value for edge6,1
0
Enter the value for edge6,2
0
Enter the value for edge6,3
0
Enter the value for edge6,4
0
Enter the value for edge6,5
0
The entered graph is as follows
0 1 1 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 1 0
0 0 0 1 0 0 1
0 0 0 0 0 0 1
0 0 0 0 0 0 0
The topological sort is as follows
0
1
2
4
3
5
6



You may also want to check out

• Newspaper Boy Problem