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