0Pricing
Competitive Programming Academy · درس

‏MST لخوارزمية Prim باستخدام كومة

إنماء الشجرة انطلاقًا من رأس واحد

‏MST لخوارزمية Prim باستخدام كومة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 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) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.

ماذا ستتعلم في «‏MST لخوارزمية Prim باستخدام كومة»؟

إنماء الشجرة انطلاقًا من رأس واحد تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟

لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.

كم من الوقت يستغرق درس «‏MST لخوارزمية Prim باستخدام كومة»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟

نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

  1. ‏DSU مع ضغط المسار
  2. الضم حسب الرتبة والمكوّنات
  3. شجرة Kruskal الممتدة الدنيا
  4. ‏MST لخوارزمية Prim باستخدام كومة
← العودة إلى Competitive Programming Academy