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

المشكلة: ترتيب مهام بتبعيات

لا يمكنك أخذ "خوارزميات متقدّمة" قبل "مقدمة برمجة"، ولا تجميع ملف .o قبل تصحيحه (compile) من الكود المصدري. كل هذه مسائل "رتّب هذه العناصر بحيث يسبق كل متطلَّب ما يعتمد عليه" — وهي بالضبط ما يحلّه الترتيب الطوبولوجي.

التعريف: ترتيب خطّي لعقد رسم بياني موجّه بحيث لكل ضلع u → v، تظهر u قبل v بالترتيب الناتج.

الشرط الإلزامي: رسم بياني موجّه بلا دورات (DAG)

الترتيب الطوبولوجي ممكن فقط إذا كان الرسم البياني موجّهًا (Directed) وبلا دورات (Acyclic) — يُسمّى اختصارًا DAG. لماذا؟

• برسم غير موجّه: لا يوجد اتجاه "يسبق" واضح أصلًا.
• برسم فيه دورة (مثلًا A → B → C → A): تناقض منطقي — كل عقدة تعتمد على الأخرى وتعتمد عليها بنفس الوقت، فلا يوجد ترتيب صالح ممكن.

💡 هذا يجعل الترتيب الطوبولوجي أداة كشف دورات ممتازة أيضًا: إن فشلت خوارزمية الترتيب في تضمين كل العقد، فالرسم البياني يحوي دورة.

الطريقة الأولى: خوارزمية Kahn (بالاعتماد على درجة الدخول)

الفكرة: ابدأ بالعقد التي لا تعتمد على شيء (درجة دخول = صفر، أي لا أضلاع داخلة إليها)، أخرجها من الرسم، وكرّر — العقد التي تصبح درجة دخولها صفرًا بعد إزالة جيرانها هي التالية بالترتيب.

from collections import deque

def topological_sort_kahn(graph, num_nodes):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in graph if in_degree[node] == 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) != num_nodes:
        raise ValueError("الرسم البياني يحوي دورة — لا يوجد ترتيب طوبولوجي صالح")
    return order


courses = {
    "مقدمة برمجة": ["هياكل بيانات"],
    "هياكل بيانات": ["خوارزميات متقدمة"],
    "رياضيات منفصلة": ["خوارزميات متقدمة"],
    "خوارزميات متقدمة": [],
}
print(topological_sort_kahn(courses, len(courses)))
# مثال: ['مقدمة برمجة', 'رياضيات منفصلة', 'هياكل بيانات', 'خوارزميات متقدمة']

لاحظ استخدام الطابور تمامًا كما في BFS — Kahn عمليًا نسخة معدَّلة من BFS.

الطريقة الثانية: DFS مع مكدّس

بديل شائع آخر: نفّذ DFS عاديًا، وبعد الانتهاء من استكشاف كل جيران عقدة (لا قبل ذلك)، ادفعها لمكدّس. عكس ترتيب المكدّس في النهاية يُعطي الترتيب الطوبولوجي.

def topological_sort_dfs(graph):
    visited = set()
    stack = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)  # بعد استكشاف كل الجيران فقط

    for node in graph:
        if node not in visited:
            dfs(node)

    return stack[::-1]  # عكس الترتيب

التعقيد

كلا الطريقتين: O(V + E) — نفس تعقيد BFS/DFS العادي، لأننا نزور كل عقدة وكل ضلع مرة واحدة تقريبًا.

ملاحظة مهمّة: الترتيب غير وحيد

قد يوجد أكثر من ترتيب طوبولوجي صحيح لنفس الرسم البياني (أي عقدتين بلا اعتماد مباشر بينهما يمكن تبديل مكانيهما). الترتيب وحيد فقط إذا شكّلت العقد مسارًا متتاليًا بلا تفرّع.

التطبيقات الحقيقية

• جدولة المواد الجامعية حسب المتطلبات السابقة.
• أنظمة البناء (Build Systems) مثل Makefile — تجميع الملفات بترتيب تبعياتها.
• إدارة الحزم (npm/pip): تثبيت الاعتماديات قبل الحزمة التي تحتاجها.
• جداول البيانات: حساب خلية تعتمد على خلايا أخرى بالترتيب الصحيح.

أخطاء شائعة

• محاولة تطبيقها على رسم بياني غير موجّه — المفهوم لا معنى له أصلًا بلا اتجاه واضح للاعتماديات.
• عدم التحقق من وجود دورة أولًا — لو كانت النتيجة (بطريقة Kahn) أقل عددًا من إجمالي العقد، فهذا يعني وجود دورة يجب معالجتها أولًا، لا تجاهله.
• نسيان أن الترتيب الطوبولوجي ليس فريدًا عادةً — لا تفترض أن ناتج خوارزميتك هو "الوحيد الصحيح" عند مقارنته بحلّ آخر مختلف الترتيب لكنه صالح أيضًا.

🎯 التالي: الشجرة اللاحقة (Trie) — هيكل بيانات لتخزين النصوص بكفاءة، أساس الإكمال التلقائي.