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

في علم الحاسوب ، تُعرف خوارزمية كوساراجو-شارير (أو خوارزمية كوساراجو ) بأنها خوارزمية خطية لإيجاد المكونات المتصلة بقوة في الرسم البياني الموجه . يُنسب الفضل في تطويرها إلى إس. راو كوساراجو وميشا شارير ، وفقًا لآهو وهوبكروفت وأولمان . ^{[ 1 ] [ 2 ]} اقترح كوساراجو هذه الخوارزمية عام 1978 لكنه لم ينشرها، بينما اكتشفها شارير بشكل مستقل ونشرها عام 1981. ^{[ 3 ]} وتعتمد هذه الخوارزمية على حقيقة أن الرسم البياني المنقول (وهو نفس الرسم البياني مع عكس اتجاه جميع حوافه) يحتوي على نفس المكونات المتصلة بقوة الموجودة في الرسم البياني الأصلي.

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

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

1. لكل رأس u في الرسم البياني، ضع علامة على u بأنه غير مُزار. ولتكن L فارغة.
2. لكل رأس u من الرسم البياني Visit(u)، قم بما يلي: حيث Visit(u)يمثل الإجراء الفرعي التكراري:

   إذا لم تتم زيارة u، فماذا يحدث؟

   1. ضع علامة على زيارتك.
   2. لكل جار خارجي v لـ u ، قم بما يلي Visit(v):
   3. أضف حرف u إلى بداية حرف L.

   وإلا فلا تفعل شيئاً.

3. لكل عنصر u من L بالترتيب، قم Assign(u,u)بما يلي حيث Assign(u,root)يكون الروتين الفرعي التكراري:

   إذا لم يتم تعيين u لمكون، فعندئذٍ:

   1. قم بتعيين u على أنه ينتمي إلى المكون الذي جذره هو الجذر .
   2. لكل جار داخلي v للعنصر u ، قم بما يلي Assign(v,root):

   وإلا فلا تفعل شيئاً.

تتمثل الاختلافات البسيطة في تعيين رقم مكون لكل رأس، أو إنشاء قوائم لكل مكون بالرؤوس التي تنتمي إليه. قد تتشارك إشارة "غير مُزار/مُزار" موقع التخزين مع التعيين النهائي للجذر لرأس ما.

يكمن جوهر الخوارزمية في أنه خلال أول عملية اجتياز (أمامية) لحواف الرسم البياني، تُضاف الرؤوس إلى القائمة L بترتيب لاحق بالنسبة لشجرة البحث قيد الاستكشاف. هذا يعني أنه لا يهم ما إذا كان الرأس v قد تمت زيارته أولاً لأنه ظهر في تعداد جميع الرؤوس أو لأنه كان الجار الخارجي لرأس آخر u تمت زيارته؛ ففي كلتا الحالتين، سيُضاف v إلى L قبل u ، لذا إذا كان هناك مسار أمامي من u إلى v ، فسيظهر u قبل v في القائمة النهائية L (إلا إذا كان كل من u و v ينتميان إلى نفس المكون القوي، وفي هذه الحالة يكون ترتيبهما النسبي في L عشوائيًا).

هذا يعني أنه يمكن ربط كل عنصر n في القائمة بكتلة L[ in _{- 1} : in _] ، حيث تتكون الكتلة من جميع الرؤوس التي يمكن الوصول إليها من الرأس n باستخدام الحواف الخارجية فقط عند كل عقدة في المسار. لا يوجد رأس في الكتلة التي تبدأ من n له رابط داخلي من أي من الكتل التي تبدأ من رأس ما على يمينه، أي الكتل المقابلة للرؤوس in _، in _{+ 1} ، ... N في القائمة. هذا صحيح، لأنه لولا ذلك، لكان الرأس الذي له الرابط الداخلي (مثلاً من الكتلة التي تبدأ من n' ≥ in _{+ 1} ) قد تمت زيارته بالفعل وإضافته إلى L في كتلة n' ، وهو ما يُعد تناقضًا. من ناحية أخرى، يمكن أن تحتوي الرؤوس في الكتلة التي تبدأ من n على حواف تشير إلى الكتل التي تبدأ من رأس ما في { in _، in + ₁ ، ... _N } .

تبدأ الخطوة الثالثة من الخوارزمية من L[0] ، حيث تُخصص جميع الرؤوس التي تشير إليها نفس مكون L[0] . لاحظ أن هذه الرؤوس لا يمكن أن تقع إلا في الكتلة التي تبدأ بـ L[0]، إذ لا يمكن أن تحتوي الكتل الأعلى على روابط تشير إلى رؤوس في كتلة L[0] . لنفترض أن مجموعة جميع الرؤوس التي تشير إلى L[0] هي In(L[0]) . بعد ذلك، تُضاف جميع الرؤوس التي تشير إلى هذه الرؤوس، In(In(L[0])) ، وهكذا حتى لا يمكن إضافة المزيد من الرؤوس.

يوجد مسار إلى L[0] من جميع الرؤوس المضافة إلى المكون الذي يحتوي على L[0] . كما يوجد مسار إلى جميع الرؤوس المضافة من L[0] ، حيث تقع جميعها في الكتلة التي تبدأ من L[0] (والتي تحتوي على جميع الرؤوس التي يمكن الوصول إليها من L[0] باتباع الحواف الخارجية في كل خطوة من المسار). وبالتالي، تُشكل هذه جميعها مكونًا واحدًا متصلًا بقوة. علاوة على ذلك، لا يبقى أي رأس، لأنه لكي يكون الرأس ضمن هذا المكون المتصل بقوة، يجب أن يكون قابلًا للوصول من L[0] وأن يكون قادرًا على الوصول إلى L[0] . تقع جميع الرؤوس القادرة على الوصول إلى L[0] ، إن وُجدت، في الكتلة الأولى فقط، وجميع الرؤوس في الكتلة الأولى قابلة للوصول من L[0] . لذلك، تختار الخوارزمية جميع الرؤوس في المكون المتصل لـ L[0] .

عند الوصول إلى الرأس v = L[ i ] في حلقة الخطوة 3، وقبل أن يُسند الرأس v إلى أي مكون، يمكننا التأكد من أن جميع الرؤوس على يساره قد شكلت مكوناتها المتصلة؛ وأن v لا ينتمي إلى أي من هذه المكونات؛ وأنه لا يشير إلى أي من الرؤوس على يساره. كذلك، بما أنه لا توجد حافة من الكتل الأعلى إلى كتلة v ، يبقى البرهان كما هو.

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

يمكن فهم الخوارزمية على أنها تحديد المكون القوي للرأس u كمجموعة الرؤوس التي يمكن الوصول إليها من u عن طريق كل من المرور الأمامي والخلفي. وبكتابة F ( u ) لمجموعة الرؤوس التي يمكن الوصول إليها من u عن طريق المرور الأمامي، و B ( u ) لمجموعة الرؤوس التي يمكن الوصول إليها من u عن طريق المرور الخلفي، و P ( u ) لمجموعة الرؤوس التي تظهر قبل u مباشرةً في القائمة L بعد المرحلة الثانية من الخوارزمية، فإن المكون القوي الذي يحتوي على الرأس u المعين كجذر هو

${\displaystyle B(u)\cap F(u)=B(u)\setminus (B(u)\setminus F(u))=B(u)\setminus P(u).}$

تقاطع المجموعات مكلف حسابيًا، ولكنه مكافئ منطقيًا لفرق مجموعتين ، ولأن${\displaystyle B(u)\setminus F(u)\subseteq P(u)}$يصبح كافياً اختبار ما إذا كان العنصر الذي تمت مواجهته حديثًا من B ( u ) قد تم تعيينه بالفعل لمكون أم لا.

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

إذا تم تمثيل الرسم البياني كمصفوفة تجاور ، فإن الخوارزمية تتطلب وقتًا قدره O(V ² ) .

• الرياضيات الجيدة، الرياضيات السيئة: حساب المكونات المترابطة بقوة