# Topological Sort — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/topological-sort

> Linear ordering of a DAG's nodes so every edge points forward — the backbone of build systems and course scheduling.

## Only works on DAGs

A **topological sort** orders nodes of a **Directed Acyclic Graph (DAG)** so that for every edge `u -> v`, `u` comes before `v`. It only exists if the graph has **no cycle** — think task scheduling where some tasks depend on others.

## Kahn's algorithm (BFS)

Repeatedly remove nodes with **in-degree 0**, decrementing their neighbours' in-degree. If fewer than `n` nodes get removed, a cycle exists.

```python
from collections import deque

def topo_sort(n, edges):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1

    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    return order if len(order) == n else []  # [] means a cycle exists
```

## DFS variant

Run DFS and push each node to a stack **after** visiting all its descendants (post-order). Reversing that stack gives a valid topological order.

```python
def topo_dfs(n, g):
    visited = [False] * n
    stack = []

    def dfs(u):
        visited[u] = True
        for v in g[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)

    for u in range(n):
        if not visited[u]:
            dfs(u)
    return stack[::-1]
```

## Where it shows up

Build systems (compile order), course prerequisites, package managers resolving dependencies, and detecting cycles in a dependency graph all reduce to topological sort.