شجرة Kruskal الممتدة الدنيا

تصل شجرة الامتداد الدنيا كل رأس باستخدام أقل وزن إجمالي ممكن للحواف، من دون دورات. تخيّل توصيل بلدة بأقل تكلفة. 🌲

Kruskal's algorithm خوارزمية جشعة تمامًا: تستمر في إضافة أرخص حافة لا تنشئ دورة حتى تتصل كل أجزاء الرسم البياني.

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

لا تؤدي إضافة حافة إلى تكوين دورة إلا إذا كان طرفاها متصلين مسبقًا. تجيب DSU عن اختبار الاتصال هذا في وقت يقارب الثابت. 🤝

مرّ على الحواف من الأرخص إلى الأغلى. ولكل حافة، تحقّق مما إذا كان طرفاها يشتركان مسبقًا في جذر واحد داخل DSU.

إذا اختلف الجذران، فإن الحافة تصل بين جزأين منفصلين، لذا اقبلها وادمجهما. وإذا تطابق الجذران، فتجاوزها لتجنّب تكوين دورة.

تحتوي شجرة امتداد تضم n من الرؤوس على n ناقص 1 حافة بالضبط. وبمجرد قبول هذا العدد، يمكنك التوقف مبكرًا.

إذا انتهيت من جميع الحواف وقد قبلت أقل من n ناقص 1، فالرسم البياني غير متصل ولا توجد شجرة امتداد.

يستحوذ الترتيب على معظم الوقت، لذا تعمل خوارزمية Kruskal's في O(E log E). أما عمليات DSU فهي رخيصة جدًا ولا تكاد تضيف شيئًا إلى هذا المجموع.

تضمن خاصية القطع أن أخف حافة تعبر أي تقسيم تكون آمنة للإضافة، ولهذا لا يخطئ اختيار الحواف بدءًا من الأرخص.

تتألق خوارزمية Kruskal's مع الرسوم البيانية قليلة الحواف المقدّمة على شكل قائمة حواف، وهو التنسيق الذي تمنحك إياه معظم مسائل المسابقات مباشرة. ⚡

أنشأت Kruskal's MST: رتّبت الحواف، وأضفت الأرخص التي تصل بين مكوّنين عبر DSU، وتوقفت عند n ناقص 1 حافة. 🎉