51. خوارزمية Kruskal's: استخدام هيكل الاتحاد والمجموعات المنفصلة (Disjoint Set Union - DSU)

Kruskal's هي خوارزمية جشعة أخرى لإيجاد شجرة MST، لكنها تركز على الحواف بدلاً من الرؤوس.

خطوات خوارزمية Kruskal's

1. فرز جميع الحواف في الرسم البياني حسب الوزن بترتيب غير متناقص.
2. تهيئة مجموعة MST (فارغة).
3. التكرار عبر الحواف المفرزة:
   • بالنسبة للحافة الحالية (U, V)، تحقق مما إذا كان U و V متصلين بالفعل (أي، في نفس المكون).
   • إذا لم يكونا متصلين (لن تؤدي إضافة الحافة إلى إنشاء دورة)، أضف الحافة إلى مجموعة MST وادمج المكونين.

الاتحاد والمجموعات المنفصلة (DSU)

تعتمد Kruskal's بشكل كبير على هيكل بيانات DSU (المعروف أيضاً باسم Union-Find). يسمح DSU بعمليتين عاليتي الكفاءة O(α(N)) (حيث α هي دالة Ackermann العكسية، وهي تقارب الوقت الثابت):

1. البحث (Find): تحديد المجموعة التي ينتمي إليها العنصر (مفيد لاكتشاف الدورة).
2. الاتحاد (Union): دمج مجموعتين في مجموعة واحدة (مفيد لإضافة حافة).

هذا يجعل Kruskal's فعالاً للغاية، وغالباً ما يكون O(E log E) تهيمن عليه عملية الفرز الأولية.