Topological sort DAG (directed acyclic graph) च्या शिरोबिंदूंना रेखीय क्रमाने क्रमांकित करते जेणेकरून प्रत्येक किनारे u->v साठी u v पूर्वी असेल. हे प्रश्नाचे उत्तर देते "या कार्यांची अवलंबित्व विचारात घेऊन मी कोणत्या क्रमाने ही कार्ये करू शकतो?"
दोन सामान्य दृष्टिकोन: (इन-डिग्री 0 असलेल्या नोड्स पुन्हा पुन्हा काढून टाकणे) किंवा (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, कार्य शेड्यूलिंग, अभ्यासक्रम पूर्वापेक्षा आणि अवलंबित्व निराकरणासाठी वापरा. जर परिणाम V पेक्षा कमी असेल तर आलेखामध्ये चक्र आहे (वैध क्रम नाही). क्रम सामान्यतः अद्वितीय नसतो.
अवलंबित्व क्रम सर्वत्र आहे — कम्पाइलर, पॅकेज मॅनेजर, स्प्रेडशीट पुनर्गणना, CI पाइपलाइन.
Topological sort निर्देशित आलेखांसाठी चक्र शोधणे म्हणून देखील कार्य करतो.
समस्या "अर्थबंधन अंतर्गत क्रम" म्हणून ओळखणे आणि topo sort कडे वळणे हे वरिष्ठ-स्तराचे मजबूत सिग्नल आहे.