Topological sort tiesiniu būdu išdėsto DAG (directed acyclic graph) viršūnes taip, kad kiekvienas šaltinis u->v turėtų u prieš v. Tai atsakyti į klausimą "kokia tvarka galiu atlikti šias užduotis atsižvelgiant į jų priklausomybes?"
Du bendri požiūriai: (pakartotinai pašalinti mazgus su įėjimo laipsniu 0) arba (reverse post-order). Galiojantis išdėstymas egzistuoja .
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']
Naudokite build systems, užduočių planavimą, kurso reikalavimus ir priklausomybės sprendimą. Jei rezultatas trumpesnis nei V, grafikas turi ciklą (nėra galiojančios tvarkos). Išdėstymas paprastai nėra unikalus.
Priklausomybės tvarka yra visur — kompiliatoriai, paketų valdikliai, skaičiuoklės perskaičiavimas, CI kanallai.
Topological sort taip pat naudojamas ciklo aptikimui nukreiptuose grafikuose.
Problemos atpažinimas kaip "tvarka esant apribojimams" ir topologinio rūšiavimo naudojimas yra stiprus vyresnio lygio signalas.