Motivation
الدرس 2 من 9 في دورة خوارزمية كروسكال - خوارزميات الرسوم البيانية على Coddy.
يحافظ Kruskal على الغابة المتنامية من الحواف المختارة في بنية union-find. لإضافة حافة بأمان، فإنه يتحقق مما إذا كانت نقطتا النهاية موجودتين بالفعل في نفس المجموعة (مما قد يؤدي إلى تكوين دورة).
لماذا نتعلم Kruskal؟
- أشجار الامتداد الدنيا (MSTs) الحقيقية: تصميم الشبكات، التجميع (clustering)، ومد الكابلات أو الطرق بأقل تكلفة.
- Union-find: بنية جميلة وقابلة لإعادة الاستخدام لتتبع الاتصال تظهر في جميع مجالات علوم الكمبيوتر.
- صحة الخوارزمية الجشعة (Greedy correctness): مثال آخر حيث يؤدي اختيار الخيار الآمن الأرخص دائمًا إلى الوصول للحل الأمثل العام.
تستخدم جميع أشجار الامتداد الدنيا لرسم بياني ما نفس المجموعة المتعددة (multiset) من أوزان الحواف، لذا فإن الوزن الإجمالي (وأكبر حافة) يكون فريدًا.
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
