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

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

نُشرت هذه الخوارزمية لأول مرة عام 1926 على يد ^{أوتاكار} بوروفكا كطريقة لإنشاء شبكة كهرباء فعّالة لمورافيا . ^{[ 1 ] [ 2 ] [ 3 ]} أُعيد اكتشاف الخوارزمية بواسطة شوكيه عام 1938؛ ^{[ 4} ] ثم بواسطة فلوريك ، ولوكاسيفيتش ، وبيركال ، وستاينهاوس ، وزوبرزيكي عام 1951؛ ^{[ 5 ]} وأخيرًا بواسطة جورج سولين عام 1965. ^{[ 6 ]} وتُعرف هذه الخوارزمية غالبًا باسم خوارزمية سولين ، خاصةً في أدبيات الحوسبة المتوازية .

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

يوضح الكود الزائف التالي تطبيقًا أساسيًا لخوارزمية بوروفكا. في العبارات الشرطية، يُعتبر كل ضلع uv أقل تكلفة من "لا شيء". الغرض من المتغير المكتمل هو تحديد ما إذا كانت الغابة F غابة ممتدة أم لا.

إذا لم تكن للحواف أوزان مميزة، فيجب استخدام قاعدة ثابتة لكسر التعادل ، كأن تعتمد على ترتيب كلي للرؤوس أو الحواف. يمكن تحقيق ذلك بتمثيل الرؤوس كأعداد صحيحة ومقارنتها مباشرةً، أو بمقارنة عناوينها في الذاكرة ، وما إلى ذلك. قاعدة كسر التعادل ضرورية لضمان أن الرسم البياني الناتج هو بالفعل غابة، أي أنه لا يحتوي على دورات. على سبيل المثال، لنفترض رسمًا بيانيًا مثلثيًا بعقد { أ ، ب ، ج } وجميع حوافه وزنها 1. عندئذٍ، يمكن إنشاء دورة إذا اخترنا ab كأصغر حافة وزن لـ { أ }، وbc لـ { ب }، و ca لـ { ج }. قاعدة كسر التعادل التي ترتب الحواف أولًا حسب المصدر، ثم حسب الوجهة، ستمنع إنشاء دورة، مما ينتج عنه الشجرة الممتدة الدنيا { ab ، bc }.

خوارزمية Borůvka هي المدخلات: رسم بياني غير موجه مرجح G = ( V , E ). المخرجات: F ، غابة ممتدة دنيا لـ G. قم بتهيئة غابة F إلى ( V ، E ′ ) حيث E ′ = {}. مكتمل := خطأ بينما غير مكتمل do أوجد المكونات المتصلة لـ F وقم بتعيين مكونها لكل رأس قم بتهيئة أرخص حافة لكل مكون إلى "لا شيء" لكل حافة uv في E ، حيث u و v في مكونات مختلفة من F : ليكن wx هو الحافة الأرخص للمكون u. إذا كانت wx مفضلة على uv ، فاجعل uv هي الحافة الأرخص للمكون u. ليكن yz هو الحافة الأرخص للمكون v . إذا كانت yz مفضلة على uv ، فاجعل uv هي الحافة الأرخص للمكون v. إذا كانت الحافة الأرخص لجميع المكونات مُعيّنة على " لا شيء" ، فهذا يعني أنه لا يمكن دمج المزيد من الأشجار - لقد انتهينا. اكتمل := صحيح. وإلا، اكتمل := خطأ. لكل مكون لا تكون حافته الأرخص "لا شيء"، أضف حافته الأرخص إلى E'.دالة is-preferred-over( edge1 , edge2 ) تُرجع ( edge2 is "None") أو (وزن( الحافة1 ) < وزن( الحافة2 )) أو (وزن( الحافة1 ) = وزن( الحافة2 ) وقاعدة كسر التعادل( الحافة1 ، الحافة2 )) دالة tie-breaking-rule( edge1 , edge2 ) هي قاعدة كسر التعادل؛ تُرجع القيمة true إذا وفقط إذا تم تفضيل edge1 على edge2 في حالة التعادل.

كتحسين، يمكن للمرء إزالة كل حافة من G التي تم العثور عليها لربط رأسين في نفس المكون، بحيث لا تساهم في وقت البحث عن أرخص الحواف في المكونات اللاحقة.

يمكن إثبات أن خوارزمية بوروفكا تستغرق O (log V ) تكرارًا للحلقة الخارجية حتى تنتهي، وبالتالي تعمل في زمن O ( E log V ) ، حيث E هو عدد الحواف، و V هو عدد الرؤوس في G (بافتراض أن E ≥ V ). في الرسوم البيانية المستوية ، وبشكل أعم في عائلات الرسوم البيانية المغلقة تحت عمليات الرسم البياني الجزئي ، يمكن جعلها تعمل في زمن خطي، عن طريق إزالة جميع الحواف باستثناء الحافة الأقل تكلفة بين كل زوج من المكونات بعد كل مرحلة من مراحل الخوارزمية. ^{[ 7 ]}

تشمل الخوارزميات الأخرى لحل هذه المشكلة خوارزمية بريم وخوارزمية كروسكال . ويمكن الحصول على خوارزميات متوازية سريعة من خلال دمج خوارزمية بريم مع خوارزمية بوروفكا. ^{[ 8 ]}

خوارزمية أسرع لشجرة الامتداد الدنيا العشوائية، والمستندة جزئيًا إلى خوارزمية بوروفكا، من ابتكار كارغر وكلاين وتارجان، تعمل في زمن متوقع قدره O( E ) . ^{[ 9 ]} أما خوارزمية شجرة الامتداد الدنيا (الحتمية) الأكثر شهرة، والتي وضعها برنارد شازيل، فهي أيضًا مستندة جزئيًا إلى خوارزمية بوروفكا، وتعمل في زمن قدره O( Eα ( E , V )) ، حيث α هي دالة أكرمان العكسية . ^{[ 10 ]} تجمع هذه الخوارزميات العشوائية والحتمية بين خطوات خوارزمية بوروفكا، التي تقلل عدد المكونات المتبقية للربط، وخطوات من نوع مختلف تقلل عدد الحواف بين أزواج المكونات.