Data Structures24 min read
Topological Sort
Order tasks with dependencies using topological sort, useful for builds, courses, and workflows.
David Miller
December 21, 2025
0.0k0
Topological sort orders nodes so dependencies come first.
Example: course prerequisites ```python graph = { "A": ["C"], "B": ["C"], "C": ["D"], "D": [] } ```
Kahn's algorithm ```python from collections import deque, defaultdict
def topo(g): indeg = defaultdict(int) for u in g: for v in g[u]: indeg[v] += 1
q = deque([u for u in g if indeg[u] == 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
print(topo(graph)) ```
Graph ```mermaid flowchart LR A --> C B --> C C --> D ```
Remember - only for DAG (no cycles) - used in scheduling and builds
#Python#Advanced#Graph