خوارزمية كروسكال

رتّب الحواف، وخذ الأقصر، ولا تُغلق حلقة أبدًا. ربما تكون خوارزمية كروسكال أبسط خوارزمية جشعة على الإطلاق، ومع ذلك تجد دائمًا أرخص طريقة لربط كل عقد الرسم البياني.

رسم بياني تنمو فيه عدة أجزاء من شجرة في آن واحد، وحافة متخطاة كانت ستُغلق دورة مرسومة بخط أحمر متقطع، وأسفله قائمة الحواف التي لم تُجرَّب بعد
رسم بياني تنمو فيه عدة أجزاء من شجرة في آن واحد، وحافة متخطاة كانت ستُغلق دورة مرسومة بخط أحمر متقطع، وأسفله قائمة الحواف التي لم تُجرَّب بعد

الفكرة

تربط شجرة الامتداد الدنيا كل عقد رسم بياني موزون بأصغر طول كلي ممكن للحواف. لا تنمّي خوارزمية كروسكال شجرة واحدة من البداية. بل تنظر إلى الرسم البياني كله دفعة واحدة، وتبدأ وكل عقدة جزء قائم بذاته، وتواصل ربط الأجزاء بأقصر حافة متاحة حتى لا يبقى إلا جزء واحد.

خطوة بخطوة

رتّب الحواف من الأقصر إلى الأطول. جرّبها بهذا الترتيب. إذا كان طرفا الحافة في جزأين مختلفين، فأضفها إلى الشجرة: يصبح الجزآن جزءًا واحدًا. وإذا كان الطرفان في الجزء نفسه بالفعل، فالحافة ستُغلق دورة، فتخطَّها. مع n من العقد تكتمل الشجرة بعد n − 1 من الحواف، ولا حاجة إلى النظر في الحواف الباقية.

مثال

خذ الحواف A–B بطول 1، وB–C بطول 2، وA–C بطول 3، وC–D بطول 4، وB–D بطول 5. تضيف كروسكال A–B، ثم B–C التي تضم C إلى الجزء A–B. تأتي A–C بعد ذلك، لكن A وC في جزء واحد بالفعل، فهي ستُغلق الدورة A–B–C وتُتخطى. تضم C–D العقدة D، فتشكّل العقد الأربع الآن شجرة واحدة من ثلاث حواف، طولها الكلي 7. أما B–D، أطول حافة، فلا تُجرَّب أصلًا.

اتحاد-بحث

السؤال الصعب الوحيد الذي تطرحه خوارزمية كروسكال: هل هاتان العقدتان في الجزء نفسه بالفعل؟ وتجيب عنه بنية اتحاد-بحث. كل جزء شجرة صغيرة من روابط تشير إلى ممثِّل. تتبع find الروابط حتى الممثِّل؛ وتعلّق union ممثِّلًا تحت الآخر. ضغط المسار، الذي يجعل كل عقدة مُرّ بها تشير مباشرة إلى الممثِّل، والدمج حسب الحجم يبقيان الروابط قصيرة جدًا حتى يستغرق كل سؤال وقتًا ثابتًا تقريبًا.

التاريخ والسرعة

نشر جوزيف كروسكال (Joseph Kruskal) الخوارزمية عام 1956 في ورقة قصيرة في Proceedings of the American Mathematical Society. ترتيب الحواف هو أبطأ جزء، لذلك يزداد العمل بنسبة E log E، حيث E عدد الحواف. وإذا كانت الحواف مرتبة بالفعل، أو كانت أطوالها أعدادًا صحيحة صغيرة، فهو خطي تقريبًا.

استكشفها

افتح التطبيق واضغط «خطوة». الحواف التي لم تُجرَّب بعد مدرجة أسفل الرسم البياني، الأقصر أولًا. كل حافة تربط جزأين تصير خضراء؛ وكل حافة ستُغلق دورة تُرسم بخط أحمر متقطع. شاهد عدة أجزاء صغيرة تنمو في أنحاء مختلفة من الرسم البياني ثم تندمج، ولاحظ أن الحواف الأخيرة كثيرًا ما لا تُجرَّب أبدًا.

الأسئلة المتداولة

لماذا ترتّب خوارزمية كروسكال الحواف؟

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

ما بنية المجموعات المنفصلة؟

اسم آخر لبنية اتحاد-بحث: بنية تحفظ مجموعة من المجموعات المنفصلة، وهي هنا أجزاء الغابة النامية، وتستطيع أن تخبر بسرعة إلى أي مجموعة ينتمي عنصر ما، وأن تدمج مجموعتين.

هل تعمل خوارزمية كروسكال على رسم بياني غير متصل؟

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

هل تُستخدم خوارزمية كروسكال في شيء آخر؟

إيقافها مبكرًا، قبل أن تندمج الأجزاء الأخيرة، يجمع العقد في عناقيد، وهذا هو التجميع أحادي الارتباط. وتشغيلها على شبكة بأطوال حواف عشوائية يولّد متاهة.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

جرّب خوارزمية كروسكال