Kruskal's Algorithm

خوارزمية Kruskal Kruskal's Algorithm

خوارزمية Kruskal تبني الشجرة الممتدة الصغرى (MST) بترتيب كل أضلاع الرسم البياني تصاعديًا وإضافة كل ضلع لا يُكوّن دورة، بمساعدة Union-Find.

خوارزمية جشعة (Greedy): رتّب الأضلاع تصاعديًا حسب الوزن، ثم مرّ عليها وأضف كل ضلع لا يربط عقدتين بالفعل بنفس المجموعة (أي لا يُكوّن دورة) — تحقّق ذلك بسرعة عبر Union-Find بدل DFS/BFS الأبطأ.

الصياغة

edges.sort()  # [(weight, u, v), ...]
uf = UnionFind(n)
mst_weight = 0
for weight, u, v in edges:
    if uf.union(u, v):
        mst_weight += weight

📄 مثال

def kruskal(n, edges):
    edges.sort()  # (weight, u, v)
    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

edges = [(1, 2, 3), (6, 0, 1), (2, 0, 2), (3, 1, 3)]
print(kruskal(4, edges))

أهم النقاط

النقطة	الوظيفة
التعقيد الزمني	O(E log E) — يهيمن عليه ترتيب الأضلاع؛ عمليات Union-Find شبه ثابتة
الأنسب لـ	رسوم بيانية متفرّقة (عدد أضلاع أقل نسبيًا)
الهيكل المساعد	Union-Find لفحص الدورات بسرعة

💡 نصائح عملية

لو الرسم البياني غير متصل، ناتج Kruskal يكون 'غابة ممتدة صغرى' (Minimum Spanning Forest) — شجرة منفصلة لكل مكوّن متصل، وليس شجرة واحدة

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

فحص الدورة بـ DFS/BFS بكل إضافة ضلع بدل Union-Find — يعمل لكن أبطأ بكثير ويفقد الخوارزمية ميزتها الأساسية

🎓 تريد فهم الصورة الكاملة خطوة بخطوة؟ ابدأ من مسار DSA الكامل بالعربي.