Topologické třídění lineárně uspořádá vrcholy DAG (orientovaného acyklického grafu) tak, aby pro každou hranu u->v byl u před v. Odpovídá na otázku "v jakém pořadí mohu provádět tyto úlohy vzhledem na jejich závislosti?"
Dva běžné přístupy: (opakovaně odebírej uzly s vstupním stupněm 0) nebo (obrácené pořadí post-order). Platné uspořádání existuje .
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']
Užívej pro build systémy, plánování úloh, prerekvizity kurzů a řešení závislostí. Pokud je výsledek kratší než V, graf obsahuje cyklus (neexistuje platné pořadí). Uspořádání obecně není jedinečné.
Ordering závislostí je všude — kompilátory, správce balíčků, přepočet tabulky, CI pipelines.
Topologické třídění slouží zároveň jako detekce cyklů v orientovaných grafech.
Rozeznání problému jako "pořadí pod omezeními" a volba topologického třídění je silný signál seniorního inženýra.