Topological Sorting
 Topological Sorting of vertices of a Directed Acyclic Graph (DAG) is a linear ordering of the vertices in such a way that if there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’, then ‘u’ comes before ‘v’ in the ordering.
Example
Consider the following Directed Acyclic Graph
For the given DAG, following 4 different topological orderings are possible
 1 2 3 4 5 6
 1 2 3 4 6 5
 1 3 2 4 5 6
 1 3 2 4 6 5
NOTES

Applications of Topological Sort
 Scheduling jobs from the given dependencies among jobs.
 Instruction Scheduling
 Determining the order of compilation tasks to perform in makefiles.
 Data Serialization
PRACTICE PROBLEMS BASED ON TOPOLOGICAL SORT
Problem01:
The number of different topological orderings for the graph shown is ________ ?
Solution
For video solution, watch this video.
Step01:
Write indegree of each vertex
Step02:
Now, since vertexA has least indegree, so remove vertexA and its associated edges and update indegree of other vertices.
Step03:
Now, since vertexB has least indegree, so remove vertexB and its associated edges and update indegree of other vertices.
Step04:
Now, since we have two vertices with least indegree, so we have 2 choices and therefore we have 2 cases
Case01: Remove vertexC and its associated edges and update indegree of other vertices.
Case02: Remove vertexD and its associated edges and update indegree of other vertices.
Step05:
Now, we will continue with the above two cases separately in the similar manner.
 In case01, first remove vertexD since it has least indegree and then remove the remaining vertexE.
 In case02, first remove vertexC since it has least indegree and then remove the remaining vertexE.
Thus, for the given graph, 2 different topological orderings are possible
 A B C D E
 A B D C E
Problem02:
The number of different topological orderings for the graph shown is ________ ?
Solution
For video solution, watch this video.
Step01:
Write indegree of each vertex
Step02:
Now, since vertex1 has least indegree, so remove vertex1 and its associated edges and update indegree of other vertices.
Step03:
Now, since we have two vertices with least indegree, so we have 2 choices and therefore we have 2 cases
Case01: Remove vertex2 and its associated edges and update indegree of other vertices.
Case02: Remove vertex3 and its associated edges and update indegree of other vertices.
Step04:
Now, we will continue with the above two cases separately in the similar manner.
 In case01, remove vertex3 since it has least indegree and update indegree of other vertices.
 In case02, remove vertex2 since it has least indegree and update indegree of other vertices.
Step05:
 In case01, remove vertex4 since it has least indegree and update indegree of other vertices.
 In case02, remove vertex4 since it has least indegree and update indegree of other vertices.
Step06:
 In case01, we have 2 choices since there are 2 vertices with least indegree. So, 2 cases are possible. We can take any of the two vertices first.
 Same is with case02.
Thus, for the given graph, 4 different topological orderings are possible
 1 2 3 4 5 6
 1 2 3 4 6 5
 1 3 2 4 5 6
 1 3 2 4 6 5
Problem03:
Consider the directed graph given below. Which of the following statements is true? (GATE2014)
 The graph does not have any topological ordering.
 Both PQRS and SRPQ are topological orderings.
 Both PSRQ and SPRQ are topological orderings.
 PSRQ is the only topological ordering.
Solution
For video solution, watch this video.
Correct Option is (C).
 The given graph is a Directed Acyclic Graph, so there will exist topological orderings.
 P and S must appear before R and Q in topological orderings as per the definition.
Problem04:
Consider the following directed graph
The number of different topological ordering of the vertices of the graph is ________ ? (GATE2016)
Solution
For video solution, watch this video.
Number of different topological orderings possible = 6
Thus, Correct answer is 6.
To gain better understanding of the concepts of Topological Sort,
To practice previous years GATE problems on Topological Sort,
Download the handwritten notes of “Topological Sort” here
Get more notes and other study material of Design and Analysis of Algorithms (DAA).
Watch video lectures by visiting our YouTube channel LearnVidFun.