Topological sort ਇੱਕ DAG (directed acyclic graph) ਦੇ vertices ਨੂੰ linearly ਕ੍ਰਮਬੱਧ ਕਰਦਾ ਹੈ ਤਾਂ ਜੋ ਹਰੇਕ edge u->v ਵਿੱਚ u before v ਹੋਵੇ। ਇਹ "ਇਨ੍ਹਾਂ ਕੰਮਾਂ ਨੂੰ ਉਹਨਾਂ ਦੀ dependencies ਨੂੰ ਦੇਖਦੇ ਹੋਏ ਕਿਸ ਕ੍ਰਮ ਵਿੱਚ ਕਰ ਸਕਦਾ ਹਾਂ?" ਦਾ ਉੱਤਰ ਦਿੰਦਾ ਹੈ।
ਦੋ ਸਾਧਾਰਨ ਤਰੀਕੇ: (ਬਾਰ-ਬਾਰ 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 ਹੈ।