مقدمة
تبدو كثير من خوارزميات الرسوم البيانية معقدة في البداية، لكن معظمها يحل مشكلة يمكن فهمها بسهولة. خوارزمية Kosaraju مثال واضح على ذلك.
تُستخدم Kosaraju لإيجاد المكونات شديدة الاتصال أو Strongly Connected Components (SCCs) داخل رسم بياني موجه.
سنبدأ هنا من المشكلة نفسها قبل الانتقال إلى التفاصيل الرياضية أو البرمجية.
ما هو الرسم البياني؟
الرسم البياني يتكون من مجموعة من العقد أو الرؤوس ومجموعة من الروابط بينها.
مثلاً:
A --- B
| |
C --- Dيمكن استخدام الرسوم البيانية لتمثيل:
- الشبكات الاجتماعية
- الطرق بين المدن
- الاتصال بين الخوادم
- اعتماديات البرمجيات
- الروابط بين صفحات الويب
- تدفق تنفيذ البرامج
- العلاقات بين الخدمات المصغرة
ما هو الرسم البياني الموجه؟
في الرسم البياني الموجه يكون لكل رابط اتجاه.
مثلاً:
A → Bيعني أننا نستطيع الانتقال من A إلى B، لكن ليس بالضرورة من B إلى A.
في نظام برمجي قد يعني:
Service A → Service Bأن الخدمة A تعتمد على الخدمة B.
أين تظهر المشكلة؟
انظر إلى الرسم التالي:
A → B → C
↑ ↓
└───────┘
D → Eيمكننا الانتقال من A إلى B، ومن B إلى C، ثم من C إلى A.
إذن المجموعة:
{A, B, C}تتمتع بخاصية مهمة: كل عقدة تستطيع الوصول إلى العقد الأخرى.
لكن في الجزء:
D → Eيمكن الوصول من D إلى E، ولكن لا يمكن العودة من E إلى D.
ماذا يعني Strongly Connected؟
تكون العقدتان u وv شديدتي الاتصال إذا كان هناك مسار من u إلى v ومسار آخر من v إلى u.
أي:
u → ... → vو:
v → ... → uفي الوقت نفسه.
ما هو Strongly Connected Component؟
المكوّن شديد الاتصال أو SCC هو أكبر مجموعة من العقد بحيث تستطيع كل عقدة الوصول إلى جميع العقد الأخرى داخل المجموعة.
مثلاً:
A → B → C
↑ ↓
└───────┘
D → E → F
↑ ↓
└───────┘لدينا:
SCC 1 = {A, B, C}
SCC 2 = {D, E, F}ماذا تفعل خوارزمية Kosaraju؟
تقوم Kosaraju باكتشاف جميع المكونات شديدة الاتصال في الرسم البياني الموجه.
إذا كان لدينا:
A → B
B → C
C → A
C → D
D → E
E → Dفالنتيجة هي:
SCC 1 = {A, B, C}
SCC 2 = {D, E}يمكن تلخيص وظيفة الخوارزمية كالآتي:
تقسيم الرسم البياني الموجه إلى مجموعات تستطيع عقد كل مجموعة الوصول إلى بعضها بعضاً عبر مسارات موجهة.
لماذا نحتاج إلى SCC؟
اكتشاف الاعتماديات الدائرية
إذا كان لدينا:
Module A → Module B
Module B → Module C
Module C → Module Aفهذه الوحدات تشكل Circular Dependency ويمكن أن تظهر كمكوّن SCC واحد.
هندسة Microservices
إذا كانت الخدمات تعتمد على بعضها بشكل دائري، فإن تحليل SCC يساعد على اكتشاف هذه المجموعة بسرعة.
الشبكات الاجتماعية
يمكن اعتبار المستخدمين عقداً وعلاقات المتابعة حواف موجهة، ثم تحليل مجموعات المستخدمين التي يمكن الوصول بينها في الاتجاهين.
تحليل صفحات الويب
كل صفحة تمثل عقدة وكل رابط يمثل حافة موجهة. يمكن للمكونات شديدة الاتصال كشف مجموعات الصفحات المترابطة بقوة.
المترجمات وتحليل البرامج
تُستخدم SCCs في تحليل Control Flow Graph وCall Graph وDependency Graph لاكتشاف الهياكل الدورية.
أنظمة الحزم
يمكن استخدام SCC لتحليل الدورات في اعتماديات المكتبات والحزم البرمجية.
لماذا لا يكفي DFS العادي؟
لنفترض:
A → B → Cعند تنفيذ DFS من A سنزور A وB وC جميعاً.
لكن هذه العقد ليست SCC واحدة، لأن C لا تستطيع العودة إلى B أو A.
إذن:
Reachability ≠ Strong Connectivityوهنا تأتي أهمية Kosaraju.
الفكرة الأساسية لخوارزمية Kosaraju
تعمل الخوارزمية بصورة عامة في ثلاث مراحل:
- تنفيذ DFS على الرسم الأصلي وتسجيل ترتيب انتهاء معالجة العقد.
- عكس اتجاه جميع الحواف لإنشاء Transpose Graph.
- تنفيذ DFS مرة أخرى على الرسم المعكوس وفق ترتيب محدد.
يمكن تصورها هكذا:
Original Graph
↓
DFS
↓
Finish Order
↓
Transpose Graph
↓
DFS
↓
SCCsكل عملية DFS في المرحلة الثانية تكشف مكوّناً شديد الاتصال.
مثال بسيط
A → B → C
↑ ↓
└───────┘
C → D
D → E
E → Dلدينا:
SCC 1 = {A, B, C}
SCC 2 = {D, E}رغم إمكانية الانتقال من C إلى D، لا يمكن العودة من D أو E إلى A أو B أو C، لذلك تبقى المجموعتان منفصلتين.
التعقيد الزمني
عند استخدام Adjacency List تعمل Kosaraju في:
O(V + E)حيث:
Vعدد العقد.Eعدد الحواف.
وهذا يجعلها مناسبة حتى للرسوم البيانية الكبيرة.
هل توجد خوارزميات أخرى؟
نعم، من أشهر البدائل:
- Tarjan's Algorithm
- Gabow's Algorithm
خوارزمية Tarjan تعمل أيضاً في O(V + E)، ولكن Kosaraju غالباً أسهل للفهم عند تعلم SCC للمرة الأولى.
متى نفكر في Kosaraju؟
إذا ظهرت في مسألة كلمات مثل:
- Strong Connectivity
- Mutual Reachability
- Circular Dependency
- Directed Graph Components
- Cyclic Services
- Cyclic Modules
فمن المناسب التفكير في SCC وخوارزميات مثل Kosaraju.
الفرق بين Cycle وSCC
Cycle هو مسار مغلق مثل:
A → B → C → Aأما SCC فهي أكبر مجموعة من العقد التي يمكن لكل عقدة فيها الوصول إلى جميع العقد الأخرى.
يمكن أن يحتوي SCC واحد على عدة دورات مختلفة.
الخلاصة
خوارزمية Kosaraju تُستخدم لإيجاد Strongly Connected Components في الرسوم البيانية الموجهة.
وتظهر فائدتها في تحليل اعتماديات البرمجيات، وبنية Microservices، والشبكات الاجتماعية، والمترجمات، ورسوم الويب، والعديد من الأنظمة الأخرى.
تستخدم الخوارزمية عمليتي DFS ورسمًا معكوسًا، وتعمل في O(V + E) عند استخدام Adjacency List.
الفكرة الأهم هي:
Kosaraju لا تبحث فقط عن دورة، بل تكشف البنية الداخلية للرسم البياني الموجه وتقسمه إلى مجموعات قصوى من العقد التي يمكنها الوصول إلى بعضها بعضاً.
في المقال التالي سنتناول مفهوم Strongly Connected Components بمزيد من التفصيل قبل دراسة تنفيذ Kosaraju خطوة بخطوة.