شارك
الرئيسيةما هي خوارزمية بوروفكا؟
خوارزمية بوروفكا (Boruvka Algorithm): ويطلق عليها أيضاً ” خوارزمية سولين”، وهي خوارزمية عشوائية سريعة، تم تشكيلها من تقاطع خوارزميتي “كروسكال” (Kruskal) و”بريم” (Prim)، تتبع أسلوب الخوارزميات الجشعة، وتهدف لإيجاد مجموعة المسارات الأقل بين العقد في الرسوم البيانية، والتي تشكل منها الشجرة الممتدة الأصغر.
تم ابتكار هذه الخوارزمية من قبل عالم الرياضيات التشيكي “أوتاكار بوروفكا” (Otakar Boruvka) في عام 1926، قبل وجود أجهزة الحاسوب كطريقة لبناء شبكة فعالة من التمديدات الكهربائية.
آلية عمل الخوارزمية
حتى يتم تشكيل الشجرة الممتدة، ينبغي وصل جميع العقد في الرسم البياني ببعضها مع مراعاة ارتباطها ببعضها من خلال الضلع الأقل وزناً.
تعتبر الخوارزمية جميع العقد في الرسم البياني كمكونات منفردة ويمكن تجميعها في مجموعات، ثم تقوم بتهيئة شجرة ممتدة صغرى فارغة وتطبق خطوتين على كل مكوّن:
- تبحث الخوارزمية عن أقرب ضلع موزون ليربط المكون بمكون آخر.
- تضيف الخوارزمية الضلع إلى الشجرة الممتدة الصغرى.
ثم تكمل الخوارزمية تشكيل الشجرة الممتدة الصغرى الجديدة بإعادة الخطوتين على المكونات الجديدة، حتى يتم ربط كافة المكونات ببعضها البعض.
اقرأ أيضاً: