Topological sort ایک DAG (directed acyclic graph) کے vertices کو خطی ترتیب میں ترتیب دیتا ہے تاکہ ہر edge u->v میں u v سے پہلے ہو۔ یہ سوال کا جواب دیتا ہے "ان tasks کو ان کے dependencies کے تحت کس ترتیب میں کر سکتا ہوں؟"
دو عام طریقے: (بار بار in-degree 0 والے nodes کو ہٹانا) یا (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، task scheduling، course prerequisites، اور dependency resolution کے لیے استعمال کریں۔ اگر نتیجہ V سے کم ہو تو graph میں cycle ہے (کوئی درست ترتیب نہیں)۔ ترتیب عام طور پر منفرد نہیں ہے۔
Dependency ordering ہر جگہ ہے — compilers، package managers، spreadsheet recalculation، CI pipelines میں۔
Topological sort directed graphs کے لیے cycle detection کے طور پر بھی کام کرتا ہے۔
"order under constraints" کے طور پر کسی مسئلے کو پہچاننا اور topo sort تک پہنچنا ایک مضبوط senior signal ہے۔