How it works?

تحتفظ بنية Union-find بمصفوفة parent. تبدأ كل رأس كجذر لنفسها. هناك عمليتان تقودان كل شيء:

• find(x): تتبع روابط parent حتى تصل إلى الجذر (الرأس الذي يكون هو نفسه أباً لنفسه). يتم توصيل رأسين عندما يتشاركان في نفس الجذر.
• union(a, b): توجيه أحد الجذور إلى الآخر، مما يؤدي إلى دمج المجموعتين.

خوارزمية كروسكال (Kruskal's Algorithm):

1. معالجة الحواف من الوزن الأصغر إلى الأكبر.
2. لكل حافة، قم بإجراء find لجذور نقاط نهايتها. إذا كانت الجذور مختلفة، فإن الحافة تربط بين قطعتين منفصلتين: قم بإجراء union لهما وأضف وزنها إلى المجموع الكلي.
3. إذا كانت الجذور متماثلة، فإن الحافة ستشكل دورة (cycle)، لذا تخطاها.

بعد معالجة كل حافة، تشكل الحواف المختارة شجرة الامتداد الدنيا MST (بالنسبة للرسم البياني المتصل، بالضبط n - 1 منها).