How it works?

احتفظ بقيمة منطقية (boolean) inTree لكل رأس (vertex). ابدأ بالرأس 0 فقط في الشجرة. الحدود (frontier) هي كل حافة لها نقطة نهاية واحدة بالضبط داخل الشجرة، وتسمى حافة عبور (crossing edge).

العملية خطوة بخطوة:

1. من بين جميع حواف العبور، اختر الحافة ذات الوزن الأصغر.
2. أضف نقطة نهايتها الخارجية إلى الشجرة وأضف وزنها إلى المجموع الكلي.
3. كرر ذلك حتى تحتوي الشجرة على جميع الرؤوس n (يستغرق ذلك n - 1 من الحواف).

إذا لم توجد حافة عبور في أي مرحلة ولكن بقيت رؤوس في الخارج، فإن الرسم البياني (graph) غير متصل.

مثال مع الحواف [0,1,1, 1,2,2, 2,3,3, 0,3,4]: من 0 خذ 0-1(1)، ثم 1-2(2)، ثم 2-3(3)؛ المجموع 6.