Topological sort ხაზოვანი რიგით განალაგებს DAG-ის (directed acyclic graph) წვეროებს ისე, რომ ყველა გაზომილი u->v ზე u იყოს v-ის წინ. ეს პასუხობს კითხვას "რა თანმიმდევრობით შემიძლია ამ ამოცანების შესრულება მათი დამოკიდებულებების გათვალისწინებით?"
ორი გავრცელებული მიდგომა: (ხელმეორედ წაშალეთ ნულოვანი შემავალი კვანტიკოს მქონე ხვლებ) ან (reverse post-order). სამართლიანი რიგი არსებობს .
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']
იყენეთ build systems-ისთვის, დავალებების დაგეგმვისთვის, კურსის წინაპირობებისთვის და დამოკიდებულების გამოკლებისთვის. თუ შედეგი V-ზე მოკლეა, გრაფიკს აქვს ციკლი (სამართლიანი რიგი არ არის). რიგი ზოგადად არ არის უნიკალური.
დამოკიდებულების მდგომარეობა ყველგან არის — კომპილატორები, პაკეტების მენეჯერები, ცხრილის გადაანგარიშება, CI-ის მილსადენი.
Topological sort ორმაგ სამუშაოდ მუშაობს ციკლის დაკვირვებაში მიმართული გრაფიკებისთვის.
პრობლემის "რეგულაციის ქვეშ დაკვეთა" და topo sort-ის მიმართ უფროსი სიგნალი აქვს.