حواف الشجرة
الطول الكلي
الحواف المفحوصة

  • الحالية
  • في الشجرة
  • مجاورة للشجرة
  • أفضل حافة حتى الآن

مزيد عن خوارزمية بريم

خوارزمية بريم

تبني خوارزمية بريم شجرة الامتداد الدنيا، أي أرخص مجموعة حواف تربط كل العقد، بتنمية شجرة واحدة من البداية. في كل خطوة تضيف العقدة التي يمكن الوصول إليها بأقصر حافة من الشجرة. انقر على عقدة لتبدأ منها، وتقدّم خطوة بخطوة لترى العقد المنتظرة وأفضل حوافها ونمو الشجرة. اضغط «تشغيل» لمشاهدة نمو الشجرة، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. انقر على عقدة لتجعلها البداية: منها تنمو الشجرة. الرقم على كل حافة هو طولها. أسفل الرسم البياني العقد التي تنتظر الانضمام، ومع كل منها طول أفضل حافة لها إلى الشجرة، وهذه الحافة مرسومة بخط متقطع. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.

كيف يعمل

  1. انقر على عقدة لتجعلها البداية: منها تنمو الشجرة.
  2. اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع.
  3. راقب العقد المنتظرة أسفل الرسم البياني، ومع كل منها أفضل حافة لها إلى الشجرة. «رسم بياني جديد» ينشئ رسمًا آخر لتجربته.

كيف تعمل خوارزمية بريم

ابدأ بشجرة من عقدة واحدة. تتذكر كل عقدة خارج الشجرة أقصر حافة لها إلى الشجرة، إن وُجدت. كرّر: خذ العقدة ذات أقصر حافة، وأضفها مع تلك الحافة إلى الشجرة، وافحص حوافها: إذا كانت إحداها أقصر من أفضل حافة لجارٍ حتى الآن، تصبح أفضل حافة لذلك الجار. عندما تنضم كل العقد، يكون عدد حواف الشجرة أقل من عدد العقد بواحدة، ويكون طولها الكلي أصغر ما يمكن.

بريم وديكسترا

تبدو خوارزمية بريم وخوارزمية ديكسترا متطابقتين تقريبًا: كلتاهما تنمّي منطقة من البداية وتحفظ العقد المنتظرة في طابور أولوية. الفرق هو الرقم في الطابور. تحفظ ديكسترا مسافة كل عقدة كاملة من البداية؛ أما بريم فتحفظ طول أفضل حافة واحدة لها إلى الشجرة فقط. لذلك تبني ديكسترا شجرة أقصر المسارات، وتبني بريم شجرة بأصغر طول كلي، وكثيرًا ما تختلف الشجرتان.

الأسئلة المتداولة

ما خوارزمية بريم؟

خوارزمية جشعة تبني شجرة الامتداد الدنيا لرسم بياني موزون بتنمية شجرة واحدة من عقدة البداية، وتضيف دائمًا أقصر حافة تربط الشجرة بعقدة خارجها.

هل تهم عقدة البداية؟

للترتيب فقط: من أي بداية تنتهي خوارزمية بريم بشجرة امتداد لها أصغر طول كلي نفسه. وعندما تتساوى أطوال بعض الحواف، قد تختلف الشجرة نفسها.

من اخترع خوارزمية بريم؟

وصفها فويتيخ يارنيك (Vojtěch Jarník) أول مرة عام 1930. ثم أعاد اكتشافها روبرت بريم (Robert Prim) عام 1957 وإدسخر ديكسترا (Edsger Dijkstra) عام 1959، لذلك تُسمى أيضًا خوارزمية يارنيك أو خوارزمية بريم–يارنيك.

ما سرعة خوارزمية بريم؟

مع كومة ثنائية يزداد العمل بنسبة E log V، حيث V عدد العقد وE عدد الحواف. ومع مصفوفة بسيطة بدل الكومة تحتاج إلى نحو V² خطوة، وهذا أفضل للرسوم البيانية الكثيفة التي يتصل فيها كل زوج من العقد تقريبًا.

هل يُرسل الرسم البياني إلى أي مكان؟

لا. يُنشأ الرسم البياني وتُبنى الشجرة داخل متصفحك، وتبقى إعداداتك الأخيرة في التخزين المحلي لهذا المتصفح.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

الانتقال إلى المحرر