How to Implement Topological Sorting in Java
 Topological Sorting in Java
 Two RealWorld Examples of Topological Sort
 Demonstration of Direct Acyclic Graph
 Implementation of Topological Sort in Java
 Topological Sorting in Recursive Order in Java
This indepth article will teach you how to implement topological sorting on a direct acyclic graph in recursive order. There are two segments in this tutorial.
First, we theoretically unfold the structure, application, scope and sorting of topological order to help our readers build the foundation to then execute the Java code themselves.
As you might have already guessed, the second portion of this article is about the implementation of Directed Acyclic Graphs (DAG).
Topological Sorting in Java
Topological sorting is the ordering of noted (n
) in a graph. If there is an edge between (u,v)
, then u
must come before v
.
In a realworld scenario, it can be a foundation to build applications that interdepend on each other.
Before we approach topological sorting, you must consider that only Directed Acyclic Graphs (DAG) can be ordered topologically.
Two RealWorld Examples of Topological Sort
 For example, in an integrated development environment (IDE), given the underlying logic to manage the user file system, an IDE may use a topological order to determine the execution and management of the files based on user preferences acquired via GUI.
 Consider the following example: Two routes can take you to your destination (A and B).
To get there, you can only take one at a time. Assume you take route B. In that situation, you do not travel on road A.
So, it does not create an absolute cycle. Hence, a topological sort is also possible.
There is, on the contrary, only one cycle. The topological order is likely to be ruled out.
Applications of Topological Sorting
 Scheduling jobs based on interdependence between jobs. This type of sorting is widely performed in researchbased applied software engineering, energy efficiency, cloud and networking.
 Another application of the toposorting can be to determine how compilation tasks should be performed in makefiles, data serializations, and symbol dependencies in linkers.
 Also, it is applicable for manufacturing workflows and contextfree grammar.
 A lot of Build Systems use this kind of algorithm.
 Migration Systems have long been utilizing this sequential order.
Time Complexity
It’s similar to the Depthfirst search (DFS) algorithm but with an extra stack. The time complexity is O(V+E)
in generic terms.
Auxiliary Space
O(V)
 The additional space is required for the stack.
Demonstration of Direct Acyclic Graph
To begin, you should be clear that topological sorting is the only viable solution if the graph is a Directed Acyclic Graph (DAG)
. Also, note that there could be several alternative topological orderings for a given directed acyclic graph.
A topological ordering is the arrangement of the vertex in an array.
Consider the following example:
Up to four possible sorting solutions for this DAG:
A B C D E F
A B C D F E
A C B D E F
A C B D F E
V
, edged as E
.If you have understood the initials, we hope you would also comprehend the following hypothetical depiction of a DAG. It is quite significant to mention that our demonstration is only to explain the generic process.
If you are interested in the data structure aspect, consider an alternative. However, the following depiction is enough to sort direct graphs in a recursive and iterative order using Java for all practical purposes.
So, without further ado, follow the following steps.

Find an indegree of each graph node (
n
):As you can see, the
VA
has the leastindegree
in the graph above. 
Hence, now we will remove
VA
and its associated edges. These same edges are also known as neighbors. 
Once done with it, all you need to do is update the
indegree
of other vertices. 
VB
has the leastindegree
. RemoveVB
and its associated edges. 
Now, update the
indegree
of other vertices.
 The above graph can also be represented as:
C => 0 , D => 0, E => 2
 Similarly, the execution of this graph may also vary.
 It is only for the demonstration for your understanding.
Since we got two vertices with the least indegree, the graph can finally be sorted into the following two n
orders.
A B C D E
A B D C E
Implementation of Topological Sort in Java
We will use this graph for the implementation. We aim to determine the appurtenance of u
before v
based on the graph theory.
Needless to mention that this execution is based on a DAG and DFS. We will sort the graph topologically using an algorithm.
Please, keep reading every step to learn more.
 Graph:
Let’s use v15
as an example. V15
depends on v10
and v5
.
V5
depends on v10
and v20
. V10
is dependent on v20
.
Based on the dependencies, v5
, v10
, and v20
should come before v15
in topological sorting.
You should also understand the depthfirst search (DFS) to understand this implementation.
 DFS Algorithm:
Depthfirst search, also known as depthfirst traversal, is a recursive algorithm for finding all vertices of a graph or tree data structure. Traversing a graph entails visiting all of its nodes.
It categorizes each vertex of the graph into one of two groups.
 The
v
is visited.  The
v
is not visited.
Also, note that the DFS algorithm functions as follows:
 Initially, it arranges the graph’s vertices on top of a stack.
 Then, it adds the top item from the stack to the visited list.
 Following that, it lists the nodes adjacent to that vertex.
 Stack the ones that aren’t on the visited list at the top.
Meanwhile, steps 2 and 3 should be repeated until the stack is empty.
Topological Sorting in Recursive Order in Java
Because topological sorting includes a short stack, we won’t print the vertex right away. Instead, we’ll recursively call topological sorting for all of its neighbors, then push it to a stack.
As of now, let’s break our logical flow into a few easytounderstand parts.
 Class
TopoSortDAG
 contains a stack with all the nodes and determines the visited and not visited nodes.
Code:
public class TopoSortDAG {
Stack<N> customstack;
public TopoSortDAG() {
customstack = new Stack<>();
}
static class N {
int d;
boolean isVstd;
List<N> nghbr;
N(int d) {
this.d = d;
this.nghbr = new ArrayList<>();
}
 Recursive Topological Sort Algorithm
Code:
public void tpSort(N N) {
List<N> nghbr = N.getnghbr();
for (int i = 0; i < nghbr.size(); i++) {
N n = nghbr.get(i);
if (n != null && !n.isVstd) {
tpSort(n);
n.isVstd = true;
}
}
customstack.push(N);
}
Explanation:
 This algorithm performs because when we push a
v
to the stack, we have previously pushed its neighbors (and their dependencies).  Henceforth, the
v
with no dependencies will automatically be at the top of the stack.
20
will be at the top of the stack based on our graph selection.Until now, we hope you have understood the basic concept that drives topological sorting so far.
That said, before we run the entire program, you should first understand each step so that you can create your graph next time you approach toposort
.
Implementation of Topological Sort in Java Using Recursive Order:
// We will implement a topological sort algorithm on a direct acyclic graph using the depthfirst
// search technique.
package delftstack.com.util;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* @author SARWAN
*
*/
public class TopoSortDAG {
Stack<N> customstack;
public TopoSortDAG() {
customstack = new Stack<>();
}
static class N {
int d;
boolean isVstd;
List<N> nghbr;
N(int d) {
this.d = d;
this.nghbr = new ArrayList<>();
}
public void adj(N nghbrN) {
this.nghbr.add(nghbrN);
}
public List<N> getnghbr() {
return nghbr;
}
public void setnghbr(List<N> nghbr) {
this.nghbr = nghbr;
}
public String toString() {
return "" + d;
}
}
public void tpSort(N N) {
List<N> nghbr = N.getnghbr();
for (int i = 0; i < nghbr.size(); i++) {
N n = nghbr.get(i);
if (n != null && !n.isVstd) {
tpSort(n);
n.isVstd = true;
}
}
customstack.push(N);
}
public static void main(String arg[]) {
TopoSortDAG topo = new TopoSortDAG();
N N20 = new N(20);
N N5 = new N(5);
N N10 = new N(10);
N N15 = new N(15);
N N30 = new N(30);
N N25 = new N(25);
N N35 = new N(35);
N20.adj(N5);
N20.adj(N10);
N5.adj(N15);
N10.adj(N5);
N10.adj(N15);
N10.adj(N30);
N10.adj(N25);
N15.adj(N30);
N30.adj(N35);
N25.adj(N35);
System.out.println("Sorting Result Set Based on the Graph:");
topo.tpSort(N20);
Stack<N> reS = topo.customstack;
while (reS.empty() == false) System.out.print(reS.pop() + " ");
}
}
Output:
Sorting Result Set Based on the Graph:
20 10 25 5 15 30 35
Output Stack:
Sarwan Soomro is a freelance software engineer and an expert technical writer who loves writing and coding. He has 5 years of web development and 3 years of professional writing experience, and an MSs in computer science. In addition, he has numerous professional qualifications in the cloud, database, desktop, and online technologies. And has developed multitechnology programming guides for beginners and published many tech articles.
LinkedIn