Topological sort linearly orders the vertices of a DAG (directed acyclic graph) so every edge u->v has u before v. It answers "in what order can I do these tasks given their dependencies?"
Two common approaches: (repeatedly remove nodes with in-degree 0) or (reverse post-order). A valid ordering exists .
from collections import deque
def topo_sort(graph):
indeg = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
indeg[v] += 1 # count incoming edges
queue = deque([u for u in indeg if indeg[u] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1 # "remove" the edge
if indeg[v] == 0:
queue.append(v)
return order if len(order) == len(graph) else None # None -> cycle
topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
Use for build systems, task scheduling, course prerequisites, and dependency resolution. If the result is shorter than V, the graph has a cycle (no valid order). The ordering is generally not unique.
Dependency ordering is everywhere — compilers, package managers, spreadsheet recalculation, CI pipelines.
Topological sort doubles as cycle detection for directed graphs.
Recognizing a problem as "order under constraints" and reaching for topo sort is a strong senior signal.