عرض توضيحي: خوارزمية كروسكال لإيجاد الشجرة الممتدة الدنيا – Algorithms

يعرض هذا المستند تطبيقا توضيحيا لخوارزمية كروسكال (Kruskal's Algorithm) المستخدمة في مادة الخوارزميات لإيجاد الشجرة الممتدة الدنيا (Minimum Spanning Tree - MST) في رسم بياني موزون. تبدأ الفكرة الأساسية بترتيب جميع الحواف تصاعديا حسب أوزانها، ثم فحص كل حافة بالترتيب وإضافتها إلى الشجرة الجزئية T إذا كانت لا تؤدي إلى إنشاء دورة. الهدف هو اختيار مجموعة حواف تربط جميع العقد بأقل مجموع ممكن للأوزان.

يوضح المثال رسما بيانيا موزونا يحتوي على مجموعة من العقد والحواف ذات الأوزان المختلفة، ثم يعرض مراحل اختيار الحواف. يتم قبول الحواف مثل 0-7 بوزن 0.16 و2-3 بوزن 0.17 و1-7 بوزن 0.19 عندما لا تسبب دورات، بينما يتم رفض بعض الحواف عندما يؤدي إدخالها إلى تكوين دورة داخل الشجرة الحالية. تعتمد الخوارزمية عمليا على بنية Union-Find للتحقق بكفاءة من اتصال العقد ومنع الدورات.

تكمن أهمية هذا الموضوع في أنه يمثل أحد التطبيقات الأساسية لخوارزميات الرسوم البيانية، ويظهر في تمارين الامتحانات المتعلقة بالشجرة الممتدة الدنيا، ترتيب الحواف، وتحليل التعقيد. يجب على الطالب فهم سبب قبول أو رفض كل حافة وليس فقط حفظ ترتيب الاختيارات.

في الخلاصة، يقدم المستند مثالا مرئيا يساعد على ربط الجانب النظري لخوارزمية كروسكال بالتنفيذ العملي، مما يسهل فهم كيفية بناء MST بطريقة تدريجية ومنظمة.