Implementation (Part 2)
الدرس 6 من 9 في دورة خوارزمية كروسكال - خوارزميات الرسوم البيانية على Coddy.
الآن أضف الحافة الآمنة الأرخص حتى تكتمل MST.
التحدي
متوسطالآن قم ببناء شجرة الامتداد الدنيا (MST).
اكتب دالة باسم kruskal تأخذ n ومصفوفة edges المسطحة (ثلاثيات، غير موجهة) لرسم بياني متصل، وتُعيد الوزن الإجمالي لشجرة الامتداد الدنيا الخاصة به.
خذ أرخص حافة غير مستخدمة بشكل متكرر؛ إذا كانت نقاط نهايتها في مجموعات مختلفة، قم بدمجهما (union) وأضف وزنها؛ وإلا فتخطاها.
أعد استخدام فكرة الـ union-find من الدرس السابق.
جرّب بنفسك
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// اكتب الكود هنا
return 0;
}
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس خوارزمية كروسكال - خوارزميات الرسوم البيانية
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity