Topological sort yana sa jeri na linear na vertices na DAG (directed acyclic graph) ta yadda kowane edge u->v yana da u kafin v. Yana amsa tambaya "a wanem oda za ni iya yin waɗannan ayyuka jikin nasu dogara?"
Zaɓi biyu na gida: (kawai cire noda tare da in-degree 0 dukan lokaci) ko (jiya post-order). Baɓbar odar da iko ya wanzu .
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']
Yi amfani da build systems, jedullin ayyuka, gidaje abubuwan koyi, da warware dogara. Idan sakamako ya zama gajere fiye V, jadwalin gaida yana da kayi (baɓbar odar da iko). Odar shine gida ba ta musamman.
Warware dogara yana a kowane waje — compilers, managers fakiti, spreadsheet recalculation, CI pipelines.
Topological sort yana aiki a matsayin canji gano wa jadwalin jiya.
Sanin matsala a matsayin "odar karkashin gatari" da isa ga topo sort shine babbar babbar alamar dabaru.