الترتيب الطوبولوجي Topological Sort

الصياغة

from collections import deque
in_degree = {n: 0 for n in graph}
for n in graph:
    for neighbor in graph[n]:
        in_degree[neighbor] += 1
queue = deque([n for n in graph if in_degree[n] == 0])
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)

📄 مثال

from collections import deque

def topological_sort(graph):
    in_degree = {n: 0 for n in graph}
    for n in graph:
        for neighbor in graph[n]:
            in_degree[neighbor] += 1
    queue = deque([n for n in graph if in_degree[n] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    if len(order) != len(graph):
        raise ValueError("يوجد دورة — لا يوجد ترتيب طوبولوجي صالح")
    return order

tasks = {"تصميم": ["تطوير"], "تطوير": ["اختبار"], "اختبار": []}
print(topological_sort(tasks))  # ['تصميم', 'تطوير', 'اختبار']

أهم النقاط

💡 نصائح عملية

• لو ناتج خوارزمية Kahn يحوي عقدًا أقل من إجمالي عدد عقد الرسم البياني، فهذا يكشف وجود دورة — استخدمها كأداة كشف دورات مجانية

⚠️ أخطاء شائعة

• محاولة تطبيقها على رسم بياني فيه دورة دون التحقق أولًا — تُعطي ترتيبًا جزئيًا ناقصًا بصمت بدل خطأ واضح إن لم تتحقق من طول الناتج

خصائص ذات صلة