MST لخوارزمية Prim باستخدام كومة
إنماء الشجرة انطلاقًا من رأس واحد
MST لخوارزمية Prim باستخدام كومة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
مسار مختلف إلى شجرة الامتداد الدنيا
تجد Prim's algorithm أيضًا شجرة امتداد دنيا، لكنها تنمّي كتلة متصلة واحدة إلى الخارج بدلًا من ترتيب جميع الحواف أولًا. 🌱
النمو انطلاقًا من رأس واحد
اختر أي رأس بداية وعلّمه بأنه تمت زيارته. تبدأ الشجرة بعقدة واحدة وتتوسع حافةً واحدة في كل مرة.
visited = [False] * nفكرة الحد الفاصل
في كل خطوة، تنظر إلى كل حافة تعبر من الشجرة إلى خارجها. تختار Prim's دائمًا الأرخص بين حواف الحد الفاصل تلك.
تختار الكومة الحد الأدنى
تجعل الكومة الدنيا العثور على أرخص حافة في الحد الفاصل سريعًا. تضع الحواف المرشحة فيها وتستخرج أصغر وزن منها في كل جولة.
import heapq
heap = [(0, start)]استخراج أرخص حافة
استخرج أصغر عنصر من الكومة. سيمنحك الوزن والرأس التالي الأقل تكلفة لإلحاقه بالشجرة النامية.
w, u = heapq.heappop(heap)تجاوز العناصر القديمة
قد يظهر الرأس في الكومة أكثر من مرة. إذا استخرجت عنصرًا لرأس تمت زيارته مسبقًا، فتجاهله واستخرج العنصر التالي.
if visited[u]:
continueالإضافة والتوسّع
علّم الرأس المستخرج بأنه تمت زيارته وأضف وزنه إلى المجموع. ثم ضع كل حواف الخروج منه في الكومة للخطوات اللاحقة.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))كرّر حتى تكتمل الشجرة
استمر في الاستخراج والتوسّع حتى تتم زيارة كل رأس. عندها يكون المجموع المتراكم هو وزن شجرة الامتداد الدنيا.
زمن التنفيذ
يمكن وضع كل حافة في الكومة مرة واحدة واستخراجها مرة واحدة، لذا تعمل Prim's المعتمدة على الكومة في O(E log V)، وهو ما يقارب Kruskal's.
مقارنة Prim's وKruskal's
استخدم Prim's مع الرسوم البيانية الكثيفة وقائمة التجاور، واستخدم Kruskal's عندما تكون لديك قائمة حواف عادية مسبقًا. تنتج كلتاهما الوزن نفسه لشجرة الامتداد الدنيا.
تبدو مثل Dijkstra
تحاكي حلقة الكومة حلقة Dijkstra's، لكنك تقارن أوزان الحواف الأصلية، لا مسافات المسارات. سيوفّر لك التعرّف على هذا النمط وقتًا في كتابة الشيفرة. ⚡
اختبار سريع
تذكّر كيف تختار Prim's حافتها التالية في كل جولة.
مراجعة
أنشأت شجرة امتداد دنيا باستخدام Prim's: ابدأ من أي مكان، واستخدم كومة دنيا لإضافة أرخص حافة في الحد الفاصل، وتجاوز الزيارات القديمة. أحسنت! 🎉
الأسئلة الشائعة
هل درس «MST لخوارزمية Prim باستخدام كومة» مجاني؟
نعم — نص درس «MST لخوارزمية Prim باستخدام كومة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «MST لخوارزمية Prim باستخدام كومة»؟
إنماء الشجرة انطلاقًا من رأس واحد تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «MST لخوارزمية Prim باستخدام كومة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- DSU مع ضغط المسار
- الضم حسب الرتبة والمكوّنات
- شجرة Kruskal الممتدة الدنيا
- MST لخوارزمية Prim باستخدام كومة