Think about any situation where some steps must come before others: you can\u2019t cook without ingredients, register for an advanced class without prerequisites, or compile code before resolving dependencies. Topological sorting answers this scheduling problem by determining a valid order for interdependent tasks so every prerequisite appears before the tasks that rely on it.<\/p>\n\n\n\n
Topological sort operates on a directed acyclic graph (DAG), where nodes represent tasks and directed edges represent dependencies. Visiting each node and edge once (via DFS or Kahn\u2019s algorithm), it produces a linear ordering of tasks in linear time, making it a fundamental and widely used tool for dependency resolution in compilers, build systems, and project planning.<\/p>\n\n\n\n
In this article, we will walk through everything you need to understand about topological sorting: what a DAG is and why it matters, what topological order means and when it exists, the two main algorithms for computing it, how to detect cycles in the process, Python implementations of both approaches, and where topological sorting is actually used in the software you work with every day.<\/p>\n\n\n\n
\n Topological sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge from vertex U to vertex V, vertex U appears before vertex V in the ordering. It is commonly used to solve dependency-based problems where certain tasks must be completed before others can begin, such as course scheduling, build systems, and task planning. Topological sorting is only possible when the graph contains no cycles, and efficient algorithms such as Kahn’s Algorithm and Depth-First Search (DFS) can compute the ordering in O(V + E) time, where V is the number of vertices and E is the number of edges.\n <\/p>\n\n <\/div>\n\n<\/div>\n\n\n\n
Topological sorting for a directed acyclic graph is a linear ordering of its vertices such that for every directed edge U to V, vertex U comes before V in the ordering. There may be several topological orderings for a graph.<\/p>\n\n\n\n
Here is a clean Python <\/a>implementation of the DFS approach:<\/p>\n\n\n\n from collections import defaultdict<\/p>\n\n\n\n class Graph:<\/p>\n\n\n\n def __init__(self, vertices):<\/p>\n\n\n\n self.V = vertices<\/p>\n\n\n\n self.graph = defaultdict(list)<\/p>\n\n\n\n def add_edge(self, u, v):<\/p>\n\n\n\n self.graph[u].append(v)<\/p>\n\n\n\n def _dfs_helper(self, node, visited, stack):<\/p>\n\n\n\n visited.add(node)<\/p>\n\n\n\n for neighbor in self.graph[node]:<\/p>\n\n\n\n if neighbor not in visited:<\/p>\n\n\n\n self._dfs_helper(neighbor, visited, stack)<\/p>\n\n\n\n # Add to stack AFTER all descendants are processed<\/p>\n\n\n\n stack.append(node)<\/p>\n\n\n\n def topological_sort_dfs(self):<\/p>\n\n\n\n visited = set()<\/p>\n\n\n\n stack = []<\/p>\n\n\n\n for node in range(self.V):<\/p>\n\n\n\n if node not in visited:<\/p>\n\n\n\n self._dfs_helper(node, visited, stack)<\/p>\n\n\n\n # Reverse the stack for correct topological order<\/p>\n\n\n\n return stack[::-1]<\/p>\n\n\n\n # Example: Course prerequisites<\/p>\n\n\n\n # 0 -> 1 means Course 0 must be completed before Course 1<\/p>\n\n\n\n g = Graph(6)<\/p>\n\n\n\n g.add_edge(5, 2)<\/p>\n\n\n\n g.add_edge(5, 0)<\/p>\n\n\n\n g.add_edge(4, 0)<\/p>\n\n\n\n g.add_edge(4, 1)<\/p>\n\n\n\n g.add_edge(2, 3)<\/p>\n\n\n\n g.add_edge(3, 1)<\/p>\n\n\n\n result = g.topological_sort_dfs()<\/p>\n\n\n\n print(“Topological Order (DFS):”, result)<\/p>\n\n\n\n # Output: Topological Order (DFS): [5, 4, 2, 3, 1, 0]<\/p>\n\n\n\n The time complexity of this approach is O(V + E) because every vertex and every edge is visited exactly once. The space complexity is O(V) for the visited set and the recursion stack.<\/p>\n\n\n\n \n Topological sorting<\/strong> powers many tools developers use every day. Build systems such as Make<\/strong> and Gradle<\/strong>, package managers like pip<\/strong> and npm<\/strong>, and workflow orchestrators such as Apache Airflow<\/strong> all model tasks as a Directed Acyclic Graph (DAG)<\/strong>. By performing a topological sort, these systems determine a safe execution order in which every dependency is processed before the tasks that rely on it. An additional benefit of Kahn\u2019s Algorithm<\/strong> is that it can detect cycles: if some nodes never reach an in-degree of zero during execution, the graph contains a circular dependency that must be resolved before processing can continue.\n <\/p>\n<\/div>\n\n\n\n Here is the complete Python implementation:<\/p>\n\n\n\n from collections import defaultdict, deque<\/p>\n\n\n\n def kahns_topological_sort(vertices, edges):<\/p>\n\n\n\n # Build adjacency list and in-degree count<\/p>\n\n\n\n graph = defaultdict(list)<\/p>\n\n\n\n in_degree = {i: 0 for i in range(vertices)}<\/p>\n\n\n\n for u, v in edges:<\/p>\n\n\n\n graph[u].append(v)<\/p>\n\n\n\n in_degree[v] += 1<\/p>\n\n\n\n # Initialize queue with all zero in-degree nodes<\/p>\n\n\n\n queue = deque([node for node in in_degree if in_degree[node] == 0])<\/p>\n\n\n\n topological_order = []<\/p>\n\n\n\n while queue:<\/p>\n\n\n\n node = queue.popleft()<\/p>\n\n\n\n topological_order.append(node)<\/p>\n\n\n\n for neighbor in graph[node]:<\/p>\n\n\n\n in_degree[neighbor] -= 1<\/p>\n\n\n\n if in_degree[neighbor] == 0:<\/p>\n\n\n\n queue.append(neighbor)<\/p>\n\n\n\n # If not all nodes processed, a cycle exists<\/p>\n\n\n\n if len(topological_order) != vertices:<\/p>\n\n\n\n return None # Cycle detected<\/p>\n\n\n\n return topological_order<\/p>\n\n\n\n # Same graph as before<\/p>\n\n\n\n edges = [(5,2), (5,0), (4,0), (4,1), (2,3), (3,1)]<\/p>\n\n\n\n result = kahns_topological_sort(6, edges)<\/p>\n\n\n\n print(“Topological Order (Kahn’s):”, result)<\/p>\n\n\n\n # Output: Topological Order (Kahn’s): [4, 5, 0, 2, 3, 1]<\/p>\n\n\n\n Notice that Kahn’s algorithm naturally produces a different but equally valid topological ordering compared to the DFS approach. Both are correct. The time complexity is O(V + E), identical to the DFS approach.<\/p>\n\n\n\nAlgorithm 2: Kahn’s Algorithm (BFS-Based)<\/strong><\/h2>\n\n\n\n
\n
DFS vs. Kahn’s: Choosing the Right Approach For Topological Sorting<\/strong><\/h2>\n\n\n\n