Topological sort एक DAG (directed acyclic graph) को vertices लाई linear order गर्छ ताकि हरेक edge u->v मा u before v हुन्छ। यसले "यी कार्यहरू तिनीहरूको निर्भरता दिएर कस्तो क्रममा गर्न सक्छु?" भन्ने प्रश्नको जवाफ दिन्छ।
दुई साधारण तरिकाहरू: (बारम्बार in-degree 0 भएका nodes हटाउनुहोस्) वा (reverse post-order)। एक मान्य ordering अवस्थित हुन्छ ।
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, task scheduling, course prerequisites, र dependency resolution को लागि प्रयोग गरनुहोस्। यदि परिणाम V भन्दा छोटो छ भने, ग्राफमा cycle छ (कुनै मान्य क्रम छैन)। ordering सामान्यतया अद्वितीय छैन।
Dependency ordering सर्वत्र छ — compilers, package managers, spreadsheet recalculation, CI pipelines।
Topological sort directed graphs को लागि cycle detection को रूपमा दोब्बर काम गर्छ।
एक समस्यालाई "constraints अन्तर्गत क्रम" को रूपमा चिनेर topo sort को लागि पहुँच गर्नु एक बलियो senior signal हो।