Topological Sorting
Topological Sorting Difficulty Level : Medium Last Updated : 29 Jan, 2023 Read Discuss(280+) Courses Practice Video 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. Note: Topological Sorting for a graph is not possible if the graph is not a DAG. For example, a topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. Another topological sorting of the following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with an in-degree of 0 (a vertex with no incoming edges). Recommended Problem Topological sort Graph Data Structures Moonfrog Labs Flipkart +8 more Solve Problem Submission count: 1.2L Topological Sorting vs Depth First Traversal (DFS) : In DFS , we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to