ما معنى Graph (الجراف) في الخوارزميات وهياكل البيانات؟ شرح عملي مبسّط
الـGraph (ويُترجم غالبًا إلى «الجراف» أو «المخطط» أو «البيان») هو هيكل بيانات يُستخدم لتمثيل مجموعة من العناصر والعلاقات بينها. يتكوّن من نوعين من المكوّنات فقط: العُقد (Vertices أو Nodes) التي تمثّل الكيانات، والحواف (Edges) التي تمثّل الروابط أو العلاقات بين هذه العُقد. ببساطة: كلما كان لديك «أشياء» و«علاقات تربط بينها»، فأنت أمام جراف — سواء كانوا أصدقاء على فيسبوك، أو مدنًا تربطها طرق، أو صفحات ويب يربط بينها روابط.
ما يجعل الجراف مميزًا عن باقي هياكل البيانات (مثل المصفوفات والقوائم) هو أنه لا يفرض ترتيبًا خطيًا أو هرميًا؛ فالعلاقات فيه حرة تمامًا، وأي عقدة يمكن أن ترتبط بأي عدد من العُقد الأخرى.
من أي شيء يتكوّن الجراف؟
- العقدة (Vertex): تمثّل عنصرًا واحدًا، مثل شخص أو مدينة أو مهمة.
- الحافة (Edge): تمثّل علاقة تربط بين عقدتين. قد تكون هذه العلاقة بسيطة (صداقة) أو تحمل معلومة إضافية (المسافة بين مدينتين).
من هذين المكوّنين البسيطين تُبنى شبكات معقّدة للغاية، وهذا سرّ قوة الجراف.
أنواع الجراف
اختيار نوع الجراف المناسب هو نصف حلّ المسألة، ولذلك من المهم التمييز بينها:
- موجّه (Directed): للحافة اتجاه واحد، مثل «فلان يتابع فلانًا» على منصة X دون أن يكون العكس صحيحًا بالضرورة.
- غير موجّه (Undirected): العلاقة متبادلة في الاتجاهين، مثل الصداقة على فيسبوك.
- موزون (Weighted): لكل حافة قيمة (وزن) تعبّر عن مسافة أو تكلفة أو زمن، وهو أساس تطبيقات الخرائط.
- غير موزون (Unweighted): الحواف متساوية القيمة، ويهمّنا فيها فقط وجود الرابط أو غيابه.
كما يُوصف الجراف بأنه دوري (Cyclic) إذا أمكن العودة إلى نقطة البداية عبر مسار من الحواف، أو لا دوري (Acyclic) إذا لم يكن ذلك ممكنًا. ومن أشهر الأنواع العملية «الجراف الموجّه اللادوري» (DAG) المستخدم في جدولة المهام وأنظمة إدارة الاعتماديات.
كيف يُمثَّل الجراف داخل الكود؟
هذه النقطة يغفلها كثير من الشروح رغم أنها الأهم عمليًا. لا يوجد «شكل» للجراف داخل الحاسوب، بل طريقتان شائعتان لتخزينه، ولكلٍّ منهما موضع مناسب:
| المعيار | مصفوفة التجاور (Adjacency Matrix) | قائمة التجاور (Adjacency List) |
|---|---|---|
| الفكرة | جدول مربّع يوضّح وجود حافة بين كل زوج من العقد | لكل عقدة قائمة بجيرانها المباشرين |
| استهلاك الذاكرة | مرتفع (يتناسب مع مربّع عدد العقد) | منخفض (يتناسب مع عدد الحواف الفعلية) |
| الأنسب لـ | الجراف الكثيف (حواف كثيرة) | الجراف المتناثر (حواف قليلة) |
| فحص وجود حافة | سريع جدًا | أبطأ نسبيًا |
القاعدة العملية: معظم مسائل العالم الحقيقي (شبكات التواصل، الخرائط) تكون متناثرة، لذا تُفضَّل قائمة التجاور في الغالب لأنها أوفر في الذاكرة.
أشهر خوارزميات الجراف
قوة الجراف تظهر عند تطبيق الخوارزميات عليه، ومن أهمها:
- البحث بالعرض (BFS): يستكشف العُقد طبقةً طبقة، ومثالي لإيجاد أقصر مسار في جراف غير موزون.
- البحث بالعمق (DFS): يتوغّل في مسار واحد حتى نهايته قبل التراجع، ويُستخدم لكشف الدورات وترتيب الاعتماديات.
- خوارزمية ديكسترا (Dijkstra): تجد أقصر مسار في جراف موزون بأوزان موجبة، وهي قلب تطبيقات الملاحة.
- خوارزميتا كروسكال وبريم: لإيجاد «شجرة التغطية الصغرى» التي تربط كل العقد بأقل تكلفة ممكنة، كما في مدّ شبكات الكهرباء.
الجراف أم الشجرة؟ التمييز الذي يخلط فيه المبتدئون
من أكثر الأخطاء شيوعًا الخلط بين الجراف والشجرة (Tree). في الحقيقة الشجرة ما هي إلا حالة خاصة من الجراف: جراف متصل وغير موجّه ولا يحتوي على أي دورات. أي أن كل شجرة جراف، لكن ليس كل جراف شجرة. فإذا سمحت لعُقدك بأن ترتبط بحرّية وتكوّن حلقات مغلقة، فقد خرجت من نطاق الشجرة إلى نطاق الجراف الأوسع.
أين نستخدم الجراف في الواقع؟
- شبكات التواصل الاجتماعي: كل مستخدم عقدة، وكل صداقة أو متابعة حافة، ومنه تُبنى اقتراحات «أشخاص قد تعرفهم».
- الخرائط والملاحة: المدن والتقاطعات عقد، والطرق حواف موزونة بالمسافة أو الزمن.
- محركات البحث: تُمثَّل صفحات الويب والروابط بينها كجراف ضخم لترتيب النتائج.
- أنظمة التوصية والاعتماديات: من اقتراح المنتجات إلى ترتيب تثبيت الحزمات البرمجية.
نصيحة عملية
عند حلّ أي مسألة برمجية، اسأل نفسك أولًا: «هل بياناتي عبارة عن كيانات تربط بينها علاقات؟». إن كانت الإجابة نعم، فالأرجح أن نمذجتها كجراف ستبسّط المسألة كثيرًا. الخطأ الشائع هو محاولة حلّ مسائل الشبكات بحلقات متداخلة معقّدة، بينما خوارزمية جراف واحدة (مثل BFS) كانت ستؤدي الغرض بوضوح وكفاءة أعلى.
الأسئلة الشائعة
هل الجراف هو نفسه الرسم البياني (Chart)؟ لا. الكلمة الإنجليزية Graph تحمل معنيين مختلفين: الرسم البياني للبيانات (مثل المخطط الأعمدة)، وهيكل البيانات محلّ حديثنا. في سياق الخوارزميات يُقصد به دائمًا هيكل العُقد والحواف.
ما الفرق بين الحافة الموجّهة وغير الموجّهة؟ الموجّهة اتجاهها واحد (من A إلى B فقط)، بينما غير الموجّهة تعني أن العلاقة متبادلة بين الطرفين تلقائيًا.
متى أختار مصفوفة التجاور بدل قائمة التجاور؟ اختر المصفوفة عندما يكون الجراف كثيف الحواف وتحتاج إلى فحص وجود حافة بين عقدتين بسرعة، وإلا فقائمة التجاور أوفر في الذاكرة.
هل أحتاج إلى معرفة الجراف لاجتياز مقابلات العمل البرمجية؟ نعم، فمسائل الجراف (خصوصًا BFS وDFS) من أكثر الأسئلة تكرارًا في المقابلات التقنية، ويُنصح بإتقان أساسياتها قبل التقدّم.