Topological Sorting

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.

Topological ordering lists vertices without violating dependencies.

Solution:

• There are two solutions – Recursive and Non-Recursive
• Recursive – We will create one map for vertex and in-degree, and each time we decrease value when it reaches zero we add to sort list.
• Second method is to use stack and push at the end when even all adjacent node processed

Latest Source Code:
Github: TopologicalSort.java

Output:

 0 -> []
1 -> []
2 -> [3]
3 -> [1]
4 -> [0, 1]
5 -> [2, 0]

[4, 5, 2, 3, 1, 0]
[5, 4, 2, 3, 1, 0]