ટોપોલોજિકલ સોર્ટ DAG (નિર્દેશિત એસાયક્લિક ગ્રાફ) ના શિરોબિંદુઓને રેખીય રીતે ક્રમમાં ગોઠવે છે જેથી દરેક ધાર u->v માટે u પહેલાં v આવે. તે પ્રશ્નનો જવાબ આપે છે: "આ કાર્યો તેમની અવલંબનતાઓ આપવામાં આવ્યા પછી કઈ ક્રમમાં કરી શકું છું?"
બે સામાન્ય પદ્ધતિઓ: (વારંવાર in-degree 0 સાથે નોડ્સ દૂર કરો) અથવા (વિપરીત પોસ્ટ-ઑર્ડર). માન્ય ક્રમ .
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']
બિલ્ડ સિસ્ટમ્સ, કાર્ય શેડ્યુલિંગ, કોર્સ પૂર્વપ્રમાણ અને અવલંબનતા સમાધાન માટે વાપરો. જો પરિણામ V કરતા ટૂંકો હોય, તો ગ્રાફમાં ચક્ર છે (કોઈ માન્ય ક્રમ નથી). ક્રમ સામાન્યતઃ અનન્ય નથી.
અવલંબનતા ક્રમ સર્વત્ર છે — કમ્પાઈલર્સ, પેકેજ મેનેજર્સ, સ્પ્રેડશીટ री-કેલ્યુલેશન, CI પાઈપલાઈનો.
ટોપોલોજિકલ સોર્ટ નિર્દેશિત ગ્રાફ્સ માટે ચક્ર શોધ તરીકે પણ કાર્ય કરે છે.
સમસ્યાને "અવરોધોતળે ક્રમ" તરીકે ઓળખવું અને ટોપોલોજિકલ સોર્ટ સુધી પહોંચવું એ વરિષ્ઠ સંકેતનો મજબૂત સંકેત છે.