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