تنفيذ خوارزمية Kruskal باستخدام خيوط

Question

أقوم بتنفيذ خوارزمية Kruskal وأرغب في استخدام المواضيع. ومع ذلك، لست متأكدا من أنني أعرف ما يكفي عن الخوارزمية للقيام بذلك.

ما أتصوره هو أنني سوف تم حل أجزاء مختلفة من الرسم البياني وتواصلها في النهاية. يمكن لأي شخص لي نقطة في الاتجاه الصحيح؟ شكرًا.

Answer 1

من عند ويكيبيديا

ركزت الأبحاث على حل مشكلة الشجرة الدنيا بأقل طريقة متوازية للغاية. مع وجود عدد خطي من المعالجات، من الممكن حل المشكلة في وقت O (LOGN). ورقة عام 2003 "خوارزميات سريعة من خوارزميات الذاكرة المشتركة لحساب الغابة الدنيا للرسوم البيانية المتفرقة" بواسطة David A. Bader و Guojing Cong توضح خوارزمية عملية عملية يمكن أن يحسب mSTS 3 مرات بشكل أسرع على 8 معالجات من خوارزمية متسلسلة محسنة. [9] عادة ما تستند الخوارزميات الموازية على خوارزمية Boruvka، ولا سيما خوارزمية Kruskal لا تقميز أيضا معالجات إضافية.

لذلك، قد تنظر في الخوارزمية المذكورة في تلك الورقة، لكن Kruskal ربما لن تستفيد من مؤشرات الترابط متعددة.

Answer 2

من الصعب موازية خوارزمية KRUSKAL ل MST لأنها تعتبر الحواف في ترتيب محدد بدقة. يجب أن نلقي نظرة على بوروفكا الخوارزمية التي من الأسهل التوازية حيث يمكن أن تعمل على كل مجموعة من الفئة الفرعية من MST جزئي بشكل مستقل.