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

كروسكال ألغوريثم

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

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

Prim’s Algorithm

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

وكثيراً ما يفضل هذا الأسلوب على الرسومات الكثيفة، وهو يستخدم طريقة ذات أولوية لاختيار الطرف التالي مع الحد الأدنى من الوزن بكفاءة.

المقارنة والتنفيذ

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

  • أنواع الكرسكال على الصعيد العالمي
  • بريم ينمو الشجرة من عقدة البداية
  • استخدام هياكل بيانات مختلفة للكفاءة
  • يعتمد الاختيار على كثافة الرسوم البيانية وحجمها