الترتيب الطوبولوجي يرتب رؤوس 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، فإن الرسم البياني يحتوي على دورة (لا يوجد ترتيب صحيح). عادةً ما يكون الترتيب غير فريد.
ترتيب التبعيات موجود في كل مكان — المترجمات، مديرو الحزم، إعادة حساب جداول البيانات، خطوط أنابيب التكامل المستمر.
الترتيب الطوبولوجي يعمل أيضاً كأداة للكشف عن الدورات في الرسوم البيانية الموجهة.
التعرف على المشكلة بأنها "ترتيب تحت القيود" واللجوء إلى الترتيب الطوبولوجي يشير إلى مستوى متقدم من المهارة.