كيف يمكن تطبيق Union/Find هياكل البيانات على خوارزمية Kruskal؟

Question

http://en.wikipedia.org/wiki/disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

الاتحاد/العثور على بنية البيانات المستخدمة لمجموعات التفكيك ...

Answer 1

يتم ذكره في إدخال خوارزمية Kruskal ، ولكن يمكنك استخدام هيكل الاتحاد/البحث للاختبار (عبر البحث) إذا كانت الحافة تربط شجرتين مختلفتين أو ما إذا كانت ستشكل دورة عند إضافتها.

يمكن تحديث نفس الهيكل (عبر الاتحاد) إذا لم تشكل الحافة دورة ويتم إضافتها إلى شجرة الامتداد.