خوارزمية بريم
تخيّل أنك تمدّ كابلًا من محطة كهرباء: تصل أقرب بلدة أولًا، ثم البلدة الأقرب إلى أي مكان موصول بالفعل، وهكذا. هذه هي خوارزمية بريم، وهي تنتهي دائمًا بأرخص شبكة ممكنة.
الفكرة
تربط شجرة الامتداد الدنيا كل عقد رسم بياني موزون بأصغر طول كلي ممكن للحواف. تبنيها خوارزمية بريم بتنمية شجرة واحدة إلى الخارج من البداية. لا تنقسم الشجرة أبدًا إلى أجزاء: في كل خطوة تنضم إليها عقدة جديدة واحدة بالضبط، عبر أقصر حافة خارجة من الشجرة.
خطوة بخطوة
ضع البداية في الشجرة. لكل عقدة خارج الشجرة، احفظ أفضل حافة لها: أقصر حافة لها إلى أي عقدة في الشجرة. ثم كرّر: اختر العقدة الخارجية التي أفضل حافة لها هي الأقصر، وأضفها إلى الشجرة مع تلك الحافة، وافحص حوافها. الجار خارج الشجرة الذي صار يمكن الوصول إليه بحافة أقصر يأخذ تلك الحافة أفضلَ حافة جديدة له. توقف عندما تصبح كل العقد في الشجرة.
مثال
خذ الحواف A–B بطول 1، وB–C بطول 2، وA–C بطول 3، وC–D بطول 4، وB–D بطول 5، وابدأ من A. تمنح حواف A العقدة B أفضل حافة 1 والعقدة C أفضل حافة 3. B هي الأقرب، فتنضم عبر A–B؛ وتحسّن حوافها C إلى 2 وتمنح D القيمة 5. تنضم C عبر B–C، وتحسّن حافتها C–D العقدة D إلى 4. وأخيرًا تنضم D عبر C–D. الطول الكلي للشجرة A–B وB–C وC–D هو 1 + 2 + 4 = 7.
لماذا هي صحيحة
في كل خطوة تنقسم العقد إلى مجموعتين: التي في الشجرة والتي خارجها. تقول خاصية القطع إن أقصر حافة بين مجموعتين كهاتين تنتمي دائمًا إلى شجرة امتداد دنيا ما. وبريم تضيف دائمًا تلك الحافة بالضبط، فيمكن دائمًا إكمال ما بنته من الشجرة حتى الآن إلى شجرة امتداد دنيا، وعندما تنضم كل العقد تكون هي نفسها شجرة امتداد دنيا.
التاريخ والسرعة
نشر عالم الرياضيات التشيكي فويتيخ يارنيك (Vojtěch Jarník) الخوارزمية عام 1930. ثم أعاد روبرت بريم (Robert Prim) اكتشافها في مختبرات بل (Bell Labs) عام 1957، وإدسخر ديكسترا (Edsger Dijkstra) مرة أخرى عام 1959. مع وضع العقد المنتظرة في كومة ثنائية يزداد العمل بنسبة E log V، حيث V عدد العقد وE عدد الحواف؛ ومع مصفوفة عادية يكون نحو V²، وهذا أفضل حين يتصل كل زوج من العقد تقريبًا. ومع كومة فيبوناتشي يكون E + V log V.
استكشفها
افتح التطبيق، وانقر على عقدة لتبدأ منها، واضغط «خطوة». العقد التي في الشجرة خضراء، والعقد المنتظرة زرقاء، وأفضل حافة لكل عقدة منتظرة مرسومة بخط متقطع. تظهر العقد المنتظرة أسفل الرسم البياني مع طول أفضل حافة لها، الأقصر أولًا: الأولى تنضم تاليًا. ابدأ من عقد مختلفة وشاهد الترتيب يتغير بينما يبقى الطول الكلي نفسه.
الأسئلة المتداولة
ما الفرق بين خوارزمية بريم وخوارزمية ديكسترا؟
كلتاهما تنمّي منطقة من البداية باستخدام طابور أولوية. ترتّب بريم العقدة المنتظرة حسب طول أفضل حافة واحدة لها إلى الشجرة؛ وترتّبها ديكسترا حسب مسافتها الكاملة من البداية. تعطي بريم شجرة امتداد دنيا، وتعطي ديكسترا شجرة أقصر المسارات.
هل تعمل خوارزمية بريم مع أطوال حواف سالبة؟
نعم. بخلاف خوارزمية ديكسترا، لا تفعل بريم سوى مقارنة الحواف بعضها ببعض، فلا تسبب الأطوال السالبة أي مشكلة: تظل تجد شجرة امتداد بأصغر طول كلي.
ماذا لو لم يكن الرسم البياني متصلًا؟
عندئذ تتوقف خوارزمية بريم بعد الوصول إلى كل عقدة يمكنها بلوغها: فتعطي شجرة امتداد دنيا لجزء البداية فقط. وتشغيلها من جديد من عقدة لم تُبلغ بعد يعطي غابة امتداد دنيا.
أيهما أفضل: خوارزمية بريم أم كروسكال؟
لا تفوز إحداهما دائمًا. تناسب بريم الرسوم البيانية الكثيفة والرسوم المخزنة كقوائم جيران؛ وتناسب كروسكال الرسوم المتفرقة المعطاة كقائمة حواف. وكلتاهما تجد شجرة بالطول الكلي نفسه.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب خوارزمية بريم