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

تُحدد خوارزمية كروسكال ^{[ 1 ]} أصغر غابة ممتدة في رسم بياني غير موجه ذي حواف مُثقّلة . إذا كان الرسم البياني متصلاً ، فإنها تُحدد أصغر شجرة ممتدة . وهي خوارزمية جشعة تُضيف في كل خطوة إلى الغابة الحافة الأقل وزنًا التي لا تُشكّل دورة . ^{[ 2 ]} تتمثل الخطوات الرئيسية للخوارزمية في الفرز واستخدام بنية بيانات المجموعة المنفصلة لاكتشاف الدورات. ويُهيمن وقت فرز جميع حواف الرسم البياني حسب وزنها على وقت تشغيلها.

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

نُشرت هذه الخوارزمية لأول مرة بواسطة جوزيف كروسكال عام 1956، ^{[ 3 ]} وأُعيد اكتشافها بعد ذلك بوقت قصير بواسطة لوبرمان وواينبرغر (1957) . ^{[ 4 ]} تشمل الخوارزميات الأخرى لهذه المشكلة خوارزمية بريم ، وخوارزمية بوروفكا ، وخوارزمية الحذف العكسي .

الخوارزمية

تقوم الخوارزمية بالخطوات التالية:

قم بإنشاء غابة (مجموعة من الأشجار) تتكون في البداية من شجرة منفصلة ذات رأس واحد لكل رأس في الرسم البياني المدخل.
قم بترتيب حواف الرسم البياني حسب وزنها.
قم بالمرور على حواف الرسم البياني، بترتيب تصاعدي حسب وزنها. لكل حافة:
- اختبر ما إذا كانت إضافة الحافة إلى الغابة الحالية ستؤدي إلى إنشاء دورة.
- وإلا، فأضف الحافة إلى الغابة، واجمع شجرتين في شجرة واحدة.

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

الشفرة الزائفة

تم تنفيذ الكود التالي باستخدام بنية بيانات المجموعة المنفصلة . وهو يمثل الغابة F كمجموعة من الحواف غير الموجهة، ويستخدم بنية بيانات المجموعة المنفصلة لتحديد ما إذا كان رأسان جزءًا من نفس الشجرة بكفاءة.

دالة كروسكال ( الرسم البياني G ) هي F:= ∅ لكل رأس v في G.Vertices، قم بما يلي: MAKE-STET(v) لكل زوج {u, v} في G.Edges مرتبة حسب الوزن المتزايد ({u, v}) ، إذا كان FIND -SET(u) ≠ FIND-SET(v) F := F ∪ { {u, v} } UNION(FIND-SET(u), FIND-SET(v)) إرجاع F

تعقيد

بالنسبة لرسم بياني ذي $E$ حافة و $V$ رأس، يمكن إثبات أن خوارزمية كروسكال تعمل في زمن $O (E log E)$ ، باستخدام هياكل بيانات بسيطة. غالبًا ما يُكتب هذا الحد الزمني على أنه $O (E log V)$ ، وهو ما يُكافئ الرسوم البيانية التي لا تحتوي على رؤوس معزولة، لأن V/2 ≤ E < V² في هذه $الرسوم$ $البيانية ، ولوغاريتمات V و V²$ متقاربة $ضمن$ عامل $ثابت$ .

لتحقيق هذا الحد، يتم أولاً فرز الحواف حسب الوزن باستخدام فرز المقارنة في زمن قدره $O (E log E)$ . بعد الفرز، يمكن المرور على الحواف بالترتيب المفرز في زمن ثابت لكل حافة. بعد ذلك، يتم استخدام بنية بيانات مجموعة منفصلة ، مع مجموعة من الرؤوس لكل مكون، لتتبع الرؤوس الموجودة في كل مكون. يتطلب إنشاء هذه البنية، مع مجموعة منفصلة لكل رأس، $V$ عملية وزمن قدره $O (V)$ . تُجري الدورة الأخيرة على جميع الحواف عمليتي بحث، وربما عملية اتحاد واحدة لكل حافة. تستغرق هذه العمليات زمنًا مستهلكًا قدره $O (α (V)) لكل عملية، مما يعطي زمنًا إجماليًا$ $في$ أسوأ الحالات قدره $O (Eα (V))$ لهذه الحلقة، حيث $α$ هي دالة أكرمان العكسية بطيئة النمو للغاية . هذا الجزء من الحد الزمني أصغر بكثير من زمن خطوة الفرز، لذا يمكن تبسيط الزمن الإجمالي للخوارزمية إلى زمن خطوة الفرز.

في الحالات التي تكون فيها الحواف مرتبة بالفعل، أو عندما يكون لها وزن صحيح صغير بما يكفي للسماح لخوارزميات فرز الأعداد الصحيحة مثل فرز العد أو فرز الجذر بفرزها في وقت خطي، فإن عمليات المجموعة المنفصلة هي الجزء المتبقي الأبطأ من الخوارزمية ويكون إجمالي الوقت $O (E α (V))$ .

مثال

صورة	وصف
	AD و CE هما أقصر الحواف، بطول 5، وقد تم اختيار AD بشكل عشوائي ، لذلك تم تمييزه.
	أصبح CE الآن أقصر ضلع لا يشكل دورة، بطول 5، لذلك تم تمييزه على أنه الضلع الثاني.
	يتم تمييز الحافة التالية، DF بطول 6، باستخدام نفس الطريقة تقريبًا.
	الضلعان التاليان الأقصر هما AB و BE ، وكلاهما بطول 7. تم اختيار AB عشوائيًا وتم تمييزه. تم تمييز الضلع BD باللون الأحمر، لأنه يوجد مسار بالفعل (باللون الأخضر) بين B و D ، لذا سيشكل دورة ( ABD ) إذا تم اختياره.
	تستمر العملية في تسليط الضوء على الحافة الأصغر التالية، BE بطول 7. يتم تمييز العديد من الحواف الأخرى باللون الأحمر في هذه المرحلة: BC لأنها ستشكل الحلقة BCE ، وDE لأنها ستشكل الحلقة DEBA ، و FE لأنها ستشكل FEBAD .
	وأخيرًا، تنتهي العملية بالحافة EG ذات الطول 9، ويتم العثور على الشجرة الممتدة الدنيا.

إثبات صحة النتائج

يتألف البرهان من جزأين. أولاً، يُثبت أن الخوارزمية تُنتج شجرة ممتدة . ثانياً، يُثبت أن الشجرة الممتدة المُنشأة ذات وزن أدنى.

شجرة ممتدة

يترك $G$ ليكن رسمًا بيانيًا متصلًا وموزونًا، وليكن $Y$ ليكن الرسم البياني الفرعي لـ $G$ تم إنتاجه بواسطة الخوارزمية. $Y$ لا يمكن أن يكون هناك دورة، لأنه بحسب التعريف لا تتم إضافة حافة إذا نتج عنها دورة. $Y$ لا يمكن فصلها، لأن الحافة الأولى التي يتم مواجهتها والتي تربط مكونين من $Y$ كان من المفترض أن تتم إضافتها بواسطة الخوارزمية. وبالتالي، $Y$ هي شجرة ممتدة من $G$ .

الحد الأدنى

نبين أن الاقتراح التالي P صحيح بالاستقراء : إذا كانت F هي مجموعة الحواف المختارة في أي مرحلة من مراحل الخوارزمية، فهناك شجرة امتداد دنيا تحتوي على F ولا تحتوي على أي من الحواف التي رفضتها الخوارزمية.

من الواضح أن P صحيح في البداية، عندما تكون F فارغة: أي شجرة ممتدة دنيا ستفي بالغرض، وهناك شجرة ممتدة دنيا موجودة لأن الرسم البياني المتصل الموزون يحتوي دائمًا على شجرة ممتدة دنيا.
والآن افترض أن P صحيح لمجموعة حواف غير نهائية F ولتكن T شجرة ممتدة دنيا تحتوي على F.
- إذا كانت الحافة المختارة التالية e موجودة أيضًا في T ، فإن P صحيحة بالنسبة لـ F + e .
- وإلا، إذا لم يكن e موجودًا في T، فإن T + e تحتوي على دورة C. تحتوي الدورة C على حواف لا تنتمي إلى F + e ، لأن e لا تُشكّل دورة عند إضافتها إلى F، ولكنها تُشكّل دورة في T. لنفترض أن f حافة موجودة في C ولكنها ليست في F + e . لاحظ أن f تنتمي أيضًا إلى T ، لأنها تنتمي إلى T + e ولكنها ليست في F + e . وفقًا لـ P ، لم يأخذ الخوارزمية f في الاعتبار. لذلك، يجب أن يكون وزن f على الأقل مساويًا لوزن e . إذن ، T − f + e شجرة، ولها نفس وزن T أو أقل منه . مع ذلك، بما أن T شجرة امتداد دنيا، فإن T − f + e لها نفس وزن T ، وإلا سنحصل على تناقض ولن تكون T شجرة امتداد دنيا. لذا، فإن T − f + e شجرة امتداد دنيا تحتوي على F + e ، ومرة أخرى، تتحقق P.
لذلك، وبحسب مبدأ الاستقراء، فإن P صحيحة عندما تصبح F شجرة ممتدة، وهو أمر ممكن فقط إذا كانت F شجرة ممتدة دنيا في حد ذاتها.

خوارزمية متوازية

خوارزمية كروسكال متسلسلة بطبيعتها ويصعب موازاتها. مع ذلك، من الممكن إجراء الفرز الأولي للحواف بالتوازي، أو بدلاً من ذلك، استخدام تطبيق متوازٍ للكومة الثنائية لاستخراج الحافة ذات الوزن الأدنى في كل تكرار. ^{[ 5 ]} بما أن الفرز المتوازي ممكن في وقت $O(n)$ على $O(\log n)$ المعالجات، ^{[ 6 ]} يمكن تقليل وقت تشغيل خوارزمية كروسكال إلى O ( E α( V ))، حيث α مرة أخرى هو معكوس دالة أكرمان أحادية القيمة .

وصف أوسيبوف وآخرون ^{[ 7 ]} نسخةً معدلةً من خوارزمية كروسكال، تُسمى كروسكال المرشح، وهي أكثر ملاءمةً للمعالجة المتوازية. تقوم فكرة كروسكال المرشح على تقسيم الحواف بطريقة مشابهة لخوارزمية الفرز السريع ، ثم استبعاد الحواف التي تربط رؤوس الشجرة نفسها لتقليل تكلفة الفرز. يوضح الكود الزائف التالي هذه الفكرة.

دالة filter_kruskal(G) هي: إذا كان |GE| < kruskal_threshold: إرجاع kruskal(G) pivot = choose_random(GE) E _≤ , E _> = partition(GE, pivot) A = filter_kruskal(E _≤ ) E _> = filter(E _> ) A = A ∪ filter_kruskal(E _> ) return A دالة التقسيم (E، محور) هي E _≤ = ∅، E _> = ∅ لكل (u، v) في E، إذا كان وزن (u، v) ≤ محور، فإن E _≤ = E _≤ ∪ {(u، v)} وإلا فإن E _> = E _> ∪ {(u، v)}، تُرجع E _≤ ، E _>دالة filter(E) هي E _f = ∅ لكل (u, v) في E ، إذا كان find_set(u) ≠ find_set(v)، فإن E _f = E _f ∪ {(u, v)}، ثم تُرجع E _f

تُعدّ خوارزمية Filter-Kruskal أكثر ملاءمةً للمعالجة المتوازية، حيث يمكن إجراء عمليات الفرز والتصفية والتقسيم بسهولة بالتوازي عن طريق توزيع الحواف بين المعالجات. ^{[ 7 ]}

أخيرًا، تم استكشاف متغيرات أخرى لتنفيذ متوازي لخوارزمية كروسكال. تشمل الأمثلة مخططًا يستخدم خيوطًا مساعدة لإزالة الحواف التي لا تُعد جزءًا من الشجرة الممتدة الدنيا في الخلفية، ^{[ 8 ]} ومتغيرًا آخر يُشغّل الخوارزمية التسلسلية على p من الرسوم البيانية الفرعية، ثم يدمج تلك الرسوم البيانية الفرعية حتى يتبقى رسم بياني فرعي واحد فقط، وهو الشجرة الممتدة الدنيا النهائية. ^{[ 9 ]}

انظر أيضاً

مراجع

^ كلاينبرج ، جون (2006). تصميم الخوارزمية . إيفا تاردوس. بوسطن: بيرسون / أديسون ويسلي. ص 142 – 151. ISBN 0-321-29535-8. OCLC 57422612 .
^ كورمين، توماس. تشارلز إي ليسرسون، رونالد إل ريفست، كليفورد شتاين (2009). مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا. ص 631 . رقم ISBN 978-0262258104.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
↑ كروسكال، ج. ب. (1956). "حول أقصر شجرة فرعية ممتدة للرسم البياني ومسألة البائع المتجول" . وقائع الجمعية الرياضية الأمريكية . 7 (1): 48-50 . doi : 10.1090/S0002-9939-1956-0078686-7 . JSTOR 2033241 .
↑ لوبرمان، هـ.؛ واينبرغر، أ. (أكتوبر 1957). "إجراءات رسمية لتوصيل الأطراف بأقل طول إجمالي للسلك" . مجلة ACM . 4 (4): 428-437 . doi : 10.1145/320893.320896 . S2CID 7320964 .
^ كوين ، مايكل ج. ديو، نارسينغ (1984). "خوارزميات الرسم البياني المتوازي" . مسوحات الحوسبة ACM . 16 (3): 319-348 . دوى : 10.1145 / 2514.2515 . S2CID 6833839 .
^ جراما ، أنانث. غوبتا، أنشول؛ كاريبيس، جورج؛ كومار، فيبين (2003). مقدمة في الحوسبة المتوازية . أديسون ويسلي. ص 412 – 413. ISBN 978-0201648652.
1 2 أوسيبوف، فيتالي؛ ساندرز، بيتر؛ سينجلر، يوهانس (2009). "خوارزمية شجرة الامتداد الأدنى لمرشح كروسكال" . وقائع ورشة العمل الحادية عشرة حول هندسة الخوارزميات والتجارب (ALENEX). جمعية الرياضيات الصناعية والتطبيقية : 52-61 . doi : 10.1137/1.9781611972894.5 . ISBN 978-0-89871-930-7.
^ كاتسيجيانيس، أناستاسيوس. أناستوبولوس، نيكوس؛ كونستانتينوس، نيكاس؛ كوزيريس، نكتاريوس (2012). “نهج لموازنة خوارزمية كروسكال باستخدام الخيوط المساعدة”. ندوة IEEE الدولية السادسة والعشرون للمعالجة المتوازية والموزعة لعام 2012 ومنتدى الدكتوراه (PDF) . الصفحات من 1601 إلى 1610. دوى : 10.1109/IPDPSW.2012.201 . رقم ISBN 978-1-4673-0974-5. S2CID 14430930 .
↑ لونكار، فلاديمير؛ شكربيتش، سرديان؛ بالاز، أنتون (2014). "توازي خوارزميات الشجرة الممتدة الدنيا باستخدام بنى الذاكرة الموزعة" . معاملات في التقنيات الهندسية . ص 543-554 . doi : 10.1007/978-94-017-8832-8_39 . ISBN 978-94-017-8831-1.

توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7القسم 23.2: خوارزميات كروسكال وبريم، الصفحات 567-574 .
مايكل تي. جودريتش وروبرتو تاماسيا . هياكل البيانات والخوارزميات في جافا ، الطبعة الرابعة. جون وايلي وأولاده، 2006. ISBN 0-471-73884-0القسم 13.7.1: خوارزمية كروسكال، ص 632.

روابط خارجية

[1] كلاينبرج ، جون (2006). تصميم الخوارزمية . إيفا تاردوس. بوسطن: بيرسون / أديسون ويسلي. ص 142 – 151. ISBN 0-321-29535-8. OCLC 57422612 .

[:0-2] كورمين، توماس. تشارلز إي ليسرسون، رونالد إل ريفست، كليفورد شتاين (2009). مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا. ص 631 . رقم ISBN 978-0262258104.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

[3] كروسكال، ج. ب. (1956). "حول أقصر شجرة فرعية ممتدة للرسم البياني ومسألة البائع المتجول" . وقائع الجمعية الرياضية الأمريكية . 7 (1): 48-50 . doi : 10.1090/S0002-9939-1956-0078686-7 . JSTOR 2033241 .

[4] لوبرمان، هـ.؛ واينبرغر، أ. (أكتوبر 1957). "إجراءات رسمية لتوصيل الأطراف بأقل طول إجمالي للسلك" . مجلة ACM . 4 (4): 428-437 . doi : 10.1145/320893.320896 . S2CID 7320964 .

[5] كوين ، مايكل ج. ديو، نارسينغ (1984). "خوارزميات الرسم البياني المتوازي" . مسوحات الحوسبة ACM . 16 (3): 319-348 . دوى : 10.1145 / 2514.2515 . S2CID 6833839 .

[6] جراما ، أنانث. غوبتا، أنشول؛ كاريبيس، جورج؛ كومار، فيبين (2003). مقدمة في الحوسبة المتوازية . أديسون ويسلي. ص 412 – 413. ISBN 978-0201648652.

[osipov2009-7] 1 2 أوسيبوف، فيتالي؛ ساندرز، بيتر؛ سينجلر، يوهانس (2009). "خوارزمية شجرة الامتداد الأدنى لمرشح كروسكال" . وقائع ورشة العمل الحادية عشرة حول هندسة الخوارزميات والتجارب (ALENEX). جمعية الرياضيات الصناعية والتطبيقية : 52-61 . doi : 10.1137/1.9781611972894.5 . ISBN 978-0-89871-930-7.

[8] كاتسيجيانيس، أناستاسيوس. أناستوبولوس، نيكوس؛ كونستانتينوس، نيكاس؛ كوزيريس، نكتاريوس (2012). “نهج لموازنة خوارزمية كروسكال باستخدام الخيوط المساعدة”. ندوة IEEE الدولية السادسة والعشرون للمعالجة المتوازية والموزعة لعام 2012 ومنتدى الدكتوراه (PDF) . الصفحات من 1601 إلى 1610. دوى : 10.1109/IPDPSW.2012.201 . رقم ISBN 978-1-4673-0974-5. S2CID 14430930 .

[9] لونكار، فلاديمير؛ شكربيتش، سرديان؛ بالاز، أنتون (2014). "توازي خوارزميات الشجرة الممتدة الدنيا باستخدام بنى الذاكرة الموزعة" . معاملات في التقنيات الهندسية . ص 543-554 . doi : 10.1007/978-94-017-8832-8_39 . ISBN 978-94-017-8831-1.

[ 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗