Introduction

مرحباً بكم مجدداً في سلسلة خوارزميات الرسوم البيانية (Graph Algorithms)! تقوم شجرة الامتداد الدنيا (MST) بربط كل رأس في رسم بياني موزون باستخدام أقل وزن إجمالي ممكن للحواف، دون وجود دورات.

تبني خوارزمية كروسكال (Kruskal's Algorithm) شجرة الامتداد الدنيا بأسلوب جشع: فهي تقوم بفرز الحواف من الأرخص إلى الأغلى وتضيف كل واحدة منها، طالما أنها لا تشكل دورة. تكمن الحيلة في اكتشاف الدورات بسرعة في بنية بيانات تسمى union-find (المعروفة أيضاً باسم disjoint-set).

الرسم البياني غير موجه وموزون، ويُعطى كـ n (الرؤوس من 0 إلى n - 1) و edges، وهي مصفوفة مسطحة من الثلاثيات [u0, v0, w0, ...] لحافة غير موجهة u - v بوزن w.

لنبدأ!