شرح خوارزمية Kruskal ببساطة: كيف تجد الشجرة الممتدة الصغرى خطوة بخطوة

خوارزمية Kruskal هي طريقة لإيجاد الشجرة الممتدة الصغرى (Minimum Spanning Tree) في رسم بياني متصل وغير موجَّه ومُوزَّن؛ أي أنها تختار مجموعة الحواف التي تربط جميع الرؤوس معاً بأقل تكلفة إجمالية ممكنة ودون تكوين أي دائرة مغلقة. فكرتها الأساسية بسيطة: رتِّب كل الحواف من الأرخص إلى الأغلى، ثم أضِف الحافة الأرخص في كل خطوة ما دامت لا تُغلق دائرة. تنتمي هذه الخوارزمية إلى عائلة الخوارزميات الجشعة (Greedy)، وطوّرها العالم جوزيف كروسكال عام 1956.

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

ما المقصود بالشجرة الممتدة الصغرى؟

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

خاصيتان تميّزان أي شجرة ممتدة في رسم به عدد رؤوس V:

• تحتوي على جميع الرؤوس الأصلية.
• تحتوي على V − 1 حافة بالضبط، ولا تحتوي على أي دائرة.

كيف تعمل خوارزمية Kruskal خطوة بخطوة

1. رتِّب كل الحواف تصاعدياً حسب وزنها (تكلفتها).
2. ابدأ بأصغر حافة وأضِفها إلى الشجرة إذا كان طرفاها ينتميان إلى مجموعتين مختلفتين (أي لن تُغلق دائرة).
3. إذا كان طرفا الحافة داخل المجموعة نفسها بالفعل، تجاهلها لأنها ستُنشئ دائرة.
4. انتقل إلى الحافة التالية الأكبر وكرِّر.
5. توقّف عندما تصل عدد الحواف المختارة إلى V − 1؛ عندها تكون الشجرة قد اكتملت.

النقطة الجوهرية التي يغفل عنها كثيرون: خوارزمية Kruskal تنظر إلى الحواف على مستوى الرسم كله، لا إلى رأس واحد. فقد تعمل في «جزر» منفصلة تنمو ثم تتّحد لاحقاً، وهذا يختلف عن خوارزمية Prim التي تنمو من رأس واحد.

مثال عملي محلول

لنأخذ رسماً برؤوس A و B و C و D و E وبالحواف التالية:

الحافة	الوزن
A–B	1
C–D	2
A–C	3
B–C	4
C–E	5
D–E	6
B–D	7

نرتّب الحواف تصاعدياً (وهي مرتّبة أصلاً هنا) ونمرّ عليها:

1. A–B (1): المجموعتان مختلفتان → نضيفها. المجموعات: {A, B}.
2. C–D (2): مختلفتان → نضيفها. المجموعات: {A, B}، {C, D}.
3. A–C (3): تربط المجموعتين → نضيفها. تصبح: {A, B, C, D}.
4. B–C (4): كلا الطرفين داخل المجموعة نفسها → نتجاهلها لأنها تُغلق دائرة.
5. C–E (5): E خارج المجموعة → نضيفها. تصبح: {A, B, C, D, E}.

الآن اخترنا 4 حواف = V − 1، فنتوقّف. الشجرة الممتدة الصغرى هي: A–B و C–D و A–C و C–E، ومجموع وزنها = 1 + 2 + 3 + 5 = 11. لاحظ أننا تخطّينا الحافة ذات الوزن 4 رغم أنها أرخص من التي اخترناها بوزن 5، لأن اختيارها كان سيُغلق دائرة.

دور بنية Union-Find

السؤال الحاسم في كل خطوة هو: «هل طرفا الحافة متصلان بالفعل؟». الطريقة الساذجة (البحث في المجموعة كلها في كل مرة) بطيئة. لذلك تُستخدم بنية Union-Find (تُعرف أيضاً بـ Disjoint Set Union) التي توفّر عمليتين سريعتين:

• Find: تحديد المجموعة التي ينتمي إليها الرأس.
• Union: دمج مجموعتين عند إضافة حافة تربطهما.

مع تحسينَي ضغط المسار (Path Compression) والدمج حسب الرتبة (Union by Rank) تصبح كل عملية شبه ثابتة عملياً، وهي ما يجعل الخوارزمية سريعة على الرسوم الكبيرة.

Kruskal أم Prim؟

كلتاهما تجدان الشجرة الممتدة الصغرى نفسها (بالوزن ذاته)، لكن تختلفان في الأسلوب والأنسب:

المعيار	Kruskal	Prim
الفكرة	تختار أرخص حافة في الرسم كله	تنمو من رأس واحد نحو الخارج
البنية المساعدة	Union-Find وترتيب الحواف	طابور أولوية (Priority Queue)
الأنسب للرسوم	المتفرقة (حواف قليلة)	الكثيفة (حواف كثيرة)
التعقيد الزمني	‏O(E log E)	‏O(E log V) مع كومة ثنائية

القاعدة العملية: إذا كان عدد الحواف صغيراً نسبياً استخدم Kruskal، وإذا كان الرسم كثيفاً فمِل إلى Prim.

التعقيد وأين تُستخدم

يهيمن على زمن التنفيذ ترتيبُ الحواف، فيكون التعقيد O(E log E)، وهو ما يكافئ O(E log V) لأن E لا يتجاوز V². أما استخداماتها الواقعية فتشمل تصميم شبكات الكهرباء والاتصالات والطرق بأقل تكلفة، وتحليل العناقيد (Clustering) في تعلُّم الآلة، وتقريب حلول بعض المسائل الأصعب.

نصيحة عملية: تعمل Kruskal بصورة سليمة فقط على الرسوم غير الموجَّهة. وإذا كان الرسم غير متصل فلن تحصل على شجرة واحدة بل على غابة ممتدة صغرى (Minimum Spanning Forest)، أي شجرة مستقلة لكل مكوِّن متصل.

الأسئلة الشائعة

هل تعطي Kruskal وPrim النتيجة نفسها؟ نعم، كلتاهما تنتجان شجرة بالوزن الإجمالي الأدنى نفسه. قد تختلف الحواف المختارة إذا كانت هناك أوزان متساوية، لكن مجموع الوزن يبقى واحداً.

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

هل تصلح للرسوم الموجَّهة؟ لا. مفهوم الشجرة الممتدة الصغرى معرَّف للرسوم غير الموجَّهة. المسائل المشابهة في الرسوم الموجَّهة (مثل Minimum Arborescence) تحتاج خوارزميات أخرى كخوارزمية Edmonds.

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