
_START_ARTICLE_
خوارزمية كروسكال
_START_PARAGRAPH_
خوارزمية كروسكال (بالإنجليزية: Kruskal Algorithm) هي خوارزمية لإيجاد الطريق ذو الوزن الأقل أو الأقل كلفة، وهي خوارزمية شرهة في نظرية المخططات حيث تجد الطريق الأقل وزن لمخطط متصل موزون ، بإضافة الكلفة في كل مرحلة، وهذا يعني أنها توجد المجموعات الجزئية التي تحتوي على الخط الواصل بين عقدتين الذي يكون الشجرة التي تحتوي على جميع العقد، حيث يتم تقليل المجموع الكلي لأوزان الخطوط الواصلة بين العقد في هذه الشجرة لأقل ما يمكن. اذا كان المخطط غير متصل سيقوم بإيجاد الشجرة التي تحتوي على اقل كلفة لكل شجرة في الغابة._NEWLINE_ظهرت هذه الخوارزمية لأول مرة في وقائع المجتمع الأمريكي للرياضيين  عام 1956 وكتبها جوزيف كروسكال.
_START_SECTION_
وصف
_START_PARAGRAPH_
1-صناعة غابة f تحتوي على مجموعة من الأشجار حيث كل عقدة عبارة عن شجرة منفصلة_NEWLINE__NEWLINE_2-صناعة مجموعة s تحتوي على كل الخطوط الواصلة بين العقد_NEWLINE__NEWLINE_3-طالما s ليست فارغة وf ليست ممتدة _NEWLINE__NEWLINE_        •احذف الخط ذو الأقل وزن _NEWLINE_        •اذا كان الخط المحذوف يوصل بين شجرتين مختلفتين إذًا تضاف إلى الغابة f ويتم دمج الشجرتين في شجرة واحدة _NEWLINE_عند اختتام الخوارزمية، تكون الغابة تحتوي على الشجرة ذات الطريق الأقل كلفة في المخطط.
_START_SECTION_
السودوكود
_START_PARAGRAPH_
الرمز التالي مكتوب مكتوب بهيكلة المجموعة المنفصلة:_NEWLINE_KRUSKAL(G):_NEWLINE_1 A = ∅_NEWLINE_2 foreach v ∈ G.V:_NEWLINE_3    MAKE-SET(v)_NEWLINE_4 foreach (u, v) in G.E ordered by weight(u, v), increasing:_NEWLINE_5    if FIND-SET(u) ≠ FIND-SET(v):_NEWLINE_6       A = A ∪ {(u, v)}_NEWLINE_7       UNION(u, v)_NEWLINE_8 return A
_START_SECTION_
التعقيد
_START_PARAGRAPH_
اذا فرضنا E عدد الخطوط الواصلة بين العقد و v هو عدد العقد حيث من الممكن ان تعمل خوارزمية كروسكال بElogE من المرات او ما يكافئ O(ElogV) مع هيكلة بيانات بسيطة وهي متكافئة لسببين رأيسيين هما:_NEWLINE_•E على الأكثر ستصل ل V^2 و   وهذا يعني انها O(logv)_NEWLINE_•كل عقدة معزولة هي عنصر منفصل من الغابة فإذا تجاهلنا العقدة المعزولة فان V<=2E_NEWLINE_يمكننا الوصول إلى هذا اذا تتبعنا هذه الخطوات: الأولى ترتيب الخطوط الواصلة بين العقد حسب وزنها بتعقيد يساوي O(ElogE)  وهذا يتيح لعملية الحذف بحذ الخط ذو الأقل وزن بوقت ثابت ثم نستخدم هيكلة المجموعات المنفصلة (الإتحاد و الإيجاد ) ونحتاج هنا لO(V) من العمليات._NEWLINE_سواء كانت الخطوط مرتبة ام لم تكن مرتبة وسيتم ترتيبها بوقت ينمو خطيًا على سبيل المثال ترتيب راديكس، كما يمكن استخدام هيكلة مجموعات منفصلة معقدة أكثر لتشغيل الخوارزمية ب O(E α(V)) مرة.
_START_SECTION_
اثبات صحة الخوارزمية
_START_PARAGRAPH_
اثبات صحة الخوارزمية ينقسم إلى قسمين الأول اثبات انها شجرة امتداد وثاني انها تملك الطريق الأقل وزنًا
_START_SECTION_
الشجرة الممتدة
_START_PARAGRAPH_
لنفرض ان P مخطط موزون وموصول ولنفرض ان Y  مخطط جزئي من P صنعت عن طريق الخوارزمية. Y لا يمكن ان تحتوي على دائرة تكون في شجرة جزئية لا في شجرتين مختلقتين كما أن Y لا يمكن ان تكون منفصلة لأن الخط الواصل بين عقدتين يتم اضافته عبر الخوارزمية مما يعني انها شجرة ممتدة
_START_SECTION_
امتلاك اقل وزن
_START_PARAGRAPH_
سنثبت ان فرضيتنا صحيحة عبر الإستقراء : إذا كانت F مجموعة من الخطوط الواصلة بين العقد مختارة في أحد المراحل من الخوارزمية اذا هنا بعض من الشجر الممتد الذي يحتوي على F _NEWLINE__NEWLINE_•P صحيحة في البداية عندما تكون F  فارغة : أي شجرة ممتدة تملك اقل وزن تخضع لهذا لأن كل مخطط موزون متصل يحتي على شجرة ممتدة تملك اقل وزن في المخطط _NEWLINE__NEWLINE_•لنفرض الان ان P صحيحة ل بعض الخطوط الواصلة بين العقد اللا نهائية ولنفرض ان T  شجرة ممتدة تمتلك الوزن الأقل وتحتوي على F اذا كان الخط التالي المختار ايضًا في T اذا P صحيحة اذا عندما تكون F+e اما اذا كان T+e يحتوي على دائرة C وهناك خط اخر f  موجود في C لكن ليس موجود في F فإن T-f+e شجرة وهي تملك وزن مساوي لوزن T وبما أن T  تملك الوزن الأقل وf لا يمكن ان يكون أقل من e والا كانت اختارت الخوارزمية f بدلا من e اذا T-f+e  هي شجرة ممتدة تحتوي على أقل وزن في المخطط _NEWLINE_•لهذا السبب جوهر الإستقراء P تثبت عندما تكون F شجرة ممتدة  بحيق تكون F الإحتمال الوحيد لتكون شجرة ممتدة تملك الوزن الأقل