DSA — Topological Sort

What is Topological Sort?

Linear ordering of vertices such that for every directed edge u→v, u comes before v.

# DFS-based
def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(vertex)
    
    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)
    
    return stack[::-1]

# Kahn's algorithm (BFS-based)
def topological_sort_kahn(graph, in_degree):
    queue = [v for v in graph if in_degree[v] == 0]
    result = []
    
    while queue:
        vertex = queue.pop(0)
        result.append(vertex)
        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result

Time Complexity

Method	Complexity
DFS	O(V + E)
Kahn's	O(V + E)

Applications

• Task scheduling
• Build systems
• Course prerequisites
• Dependency resolution

Mini Practice

1. Implement topological sort
2. Detect cycles using it
3. Schedule tasks with dependencies
4. Compare DFS and BFS approaches

Up Next

Continue with Dynamic Programming — optimization technique.