टोपोलॉजिकल सॉर्ट एक 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 पाइपलाइन।
टोपोलॉजिकल सॉर्ट निर्देशित ग्राफ के लिए चक्र पहचान के रूप में भी काम करता है।
किसी समस्या को "बाधाओं के तहत क्रमण" के रूप में पहचानना और टोपोलॉजिकल सॉर्ट तक पहुंचना एक मजबूत वरिष्ठ संकेत है।