టోపోలాజికల్ సార్ట్ DAG (దిశానిర్దేశ చేసిన నిరాకార గ్రాఫ్) యొక్క శీర్షాలను సరళంగా ఆర్డర్ చేస్తుంది, తద్వారా ప్రతి అంచు u->v u కంటే ముందు v ఉంటుంది. "వాటి డిపెండెన్సీలు ఇచ్చినట్లు ఈ పనులను నేను ఏ క్రమంలో చేయగలను?" అనే ప్రశ్నకు సమాధానమిస్తుంది.
రెండు సాధారణ విధానాలు: (ఇన్-డిగ్రీ 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 పైప్లైన్లు.
టోపోలాజికల్ సార్ట్ దిశానిర్దేశ చేసిన గ్రాఫ్ల కోసం సైకిల్ ఎంపిక గా కూడా ఉపయోగపడుతుంది.
ఒక సమస్యను "పరిమితుల కింద ఆర్డర్" గా గుర్తించి టోపో సార్ట్ కోసం చేరుకోవడం సీనియర్ సిగ్నల్.