Topological Sort

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

Topological sorting is not possible if graph is not directed acyclic graph.

Topological Sort

As shown in above diagram 0 should come in order before 1 or in other words 0 should be completed before 1. 1 should come before 2.

Topological sort order is 0->1->3->2

Topological sort problems can be solved easily with Kahn’s algorithm. Algorithm is as follows:

• Store in degree of all the nodes in an array. lets say a should be completed before b then b is dependent on a. hence in degree of b will be 1.
• Take an adjacency list to store all the nodes which have incoming node from key node. if a->b then {a:[b]}. means arrow is towards b
• Take all the nodes in queue which have in degree 0
• While queue is not empty
• Take first node from queue
• Store this in answer array
• Reduce in degree of all the dependent nodes since this node has visited or processed.
• Check in degree immediately after reducing it whether it is empty. If empty then push in queue
• Repeat