Topological sort inaandika kwa mstari vertices ya DAG (directed acyclic graph) ili kila ukingo u->v ina u kabla v. Inajibu swali "kwa utaratibu gani ninaweza kufanya kazi hizi kutokana na tegemezi zao?"
Mazuia mawili ya kawaida: (ondoa nodi zilizo na in-degree 0 mara kwa mara) au (post-order kinyume). Utaratibu halali upo .
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']
Tumia kwa mifumo ya ujenzi, upangaji wa kazi, sharti la kozi, na utatuzi wa tegemezi. Ikiwa matokeo ni mafupi kuliko V, grafu ina duara (hakuna utaratibu halali). Utaratibu kwa ujumla sio wa nchi moja.
Utaratibu wa tegemezi uko mahali — waokutani, meneja wa pakiti, hesabu ya karatasi, mifumo ya CI.
Topological sort inafanya kazi pia kama kugundua duara kwa grafu moja kwa moja.
Kutambua tatizo kama "agizo chini ya vizuizi" na kumkamata topological sort ni ishara kali kwa msanidi mzee.