الشجرة الممتدة الصغرى (Minimum Spanning Tree)

المشكلة: أرخص شبكة تربط كل النقاط

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

شجرة تضم V عقدة تحتاج بالضبط V - 1 ضلعًا لتبقى شجرة (متصلة وبلا دورات).

خوارزمية Kruskal: رتّب، ثم اختر بجشع

فكرة Kruskal جشعة (Greedy) وبسيطة:

1. رتّب كل أضلاع الرسم البياني تصاعديًا حسب الوزن.
2. مرّ على الأضلاع بالترتيب، وأضف الضلع فقط إذا لم يُكوّن دورة مع ما أُضيف سابقًا.
3. توقّف عند إضافة V - 1 ضلعًا.

السؤال العملي: كيف تتحقق بسرعة أن إضافة ضلع لن يُكوّن دورة؟ هنا يأتي دور Union-Find من الدرس السابق: ضلع بين عقدتين يُكوّن دورة إذا وفقط إذا كانتا بالفعل بنفس المجموعة (نفس الجذر).

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True


def kruskal(n, edges):
    # edges: [(weight, u, v), ...]
    edges.sort()  # ترتيب تصاعدي حسب الوزن
    uf = UnionFind(n)
    mst_weight = 0
    mst_edges = []
    for weight, u, v in edges:
        if uf.union(u, v):  # لم تُكوّن دورة → أضفه
            mst_weight += weight
            mst_edges.append((u, v, weight))
    return mst_weight, mst_edges


# عقد مرقّمة 0..3، أضلاع (الوزن، عقدة، عقدة)
edges = [(1, 2, 3), (6, 0, 1), (2, 0, 2), (3, 1, 3)]
print(kruskal(4, edges))

التعقيد

• ترتيب الأضلاع: O(E log E).
• عمليات Union-Find لكل الأضلاع: شبه ثابتة إجمالًا (راجع الدرس السابق).
• الإجمالي: O(E log E) — أو بصياغة مكافئة O(E log V) (لأن E لا يتجاوز V² بأي رسم بياني بسيط).

البديل: خوارزمية Prim

بدل ترتيب كل الأضلاع دفعة واحدة، Prim تنمّي شجرة واحدة تدريجيًا: تبدأ من عقدة، وبكل خطوة تضيف أرخص ضلع يربط الشجرة الحالية بعقدة خارجها (بمساعدة طابور أولوية/كومة — تذكّرك بخوارزمية Dijkstra؟ الفكرة متشابهة، لكن Dijkstra تتتبّع أرخص مسار من المصدر، بينما Prim تتتبّع أرخص ضلع لتوسيع الشجرة).

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

• تصميم شبكات الكابلات/الأنابيب بأقل تكلفة مادة.
• تبسيط الشبكات (Network Design): أقل عدد وصلات يبقي الشبكة متصلة.
• خوارزميات التجميع (Clustering) في تعلّم الآلة — قطع أغلى أضلاع MST لتقسيم البيانات لمجموعات.

أخطاء شائعة

• الخلط بين MST وأقصر مسار (Dijkstra): MST تقلّل مجموع وزن الشجرة كلها، بينما Dijkstra تقلّل تكلفة المسار من نقطة لنقطة واحدة محدّدة — ليسا نفس المسألة وقد تختلف نتائجهما تمامًا على نفس الرسم البياني.
• تطبيق Kruskal بفحص الدورة عبر DFS/BFS في كل خطوة بدل Union-Find — يعمل لكنه أبطأ بكثير (يفقد ميزة الزمن شبه الثابت).
• نسيان أن MST تتطلّب رسمًا بيانيًا غير موجّه — المفهوم لا ينطبق مباشرة على الرسوم الموجّهة بنفس الطريقة.

🎯 التالي: الترتيب الطوبولوجي — ترتيب عقد رسم بياني موجّه حسب التبعيات.