50. أشجار الامتداد الدنيا (Minimum Spanning Trees - MST): مفهوم خوارزمية Prim's

شجرة الامتداد (Spanning Tree) للرسم البياني هي رسم بياني فرعي يربط جميع الرؤوس معاً، دون أي دورات. شجرة الامتداد الدنيا (Minimum Spanning Tree - MST) هي شجرة امتداد حيث يتم تقليل مجموع أوزان الحواف.

خوارزمية Prim's (النهج الجشع)

تبني خوارزمية Prim's شجرة MST بشكل تكراري عن طريق إضافة حواف تربط رأساً جديداً بمجموعة الشجرة المتنامية. إنها استراتيجية تحسين محلية.

1. البدء برأس مصدر عشوائي S في MST.
2. التكرار V-1 مرة:
   • حدد الحافة (U, V) التي تربط رأساً U موجوداً بالفعل في MST برأس V لم تتم زيارته بحيث يكون وزن الحافة (U, V) هو الأدنى.
   • أضف هذه الحافة ذات الوزن الأدنى والرأس V إلى MST.

يتم تطبيق Prim's بكفاءة باستخدام Min Heap (قائمة انتظار ذات أولوية)، مثل Dijkstra's، لتحديد أصغر حافة تالية بسرعة.