هيكلة البيانات بواسطة الرسم البياني Graph

مفهوم الرسم البياني Graph:

وتعني الرسم البياني، وهي عبارة عن نوع شائع من أنواع هياكل البيانات، حيث تتكون من مجموعة محدودة من العقد (nodes) تربط بينها مجموعة من الحواف (edges)، حيث يربط بين كل اثنين من العقد (node)، برابط (edge) واحد، ما لم يتم تحديد خلاف ذلك. مثلا يُشار إلى الزوج (x,y) على أنه حافة (edge)، والتي تشير إلى أن العقدة (x) تتصل بالعقدة (y).

أنواع الرسوم البيانية Graph:

1. الرسم البياني الغير موجه والموجه (Undirected and Directed Graph): في رسم بياني غير موجه، ترتبط العقد (nodes) بحواف (edges) ثنائية الاتجاه. على سبيل المثال، إذا كانت الحافة تربط العقدة 1و2، فيمكننا الانتقال من العقدة 1 إلى العقدة 2، ومن العقدة 2 إلى 1. في الرسم البياني الموجه، ترتبط العقد بحواف موجهة (تذهب فقط في اتجاه واحد).على سبيل المثال، إذا كانت الحافة تربط العقدة 1 و 2، ولكن رأس السهم يشير إلى 2، يمكننا فقط الانتقال من العقدة 1 إلى العقدة 2 وليس في الاتجاه المعاكس.

2. الرسم البياني الموزون وغير الموزون (Weighted and Unweighted Graph):يسمى بالرسم البياني بالموزون عندما تعيين بعض الأوزان (الأرقام) على حوافه (edges). على سبيل المثال، لنفترض أننا نمثل مدن لدولة ما كعقد (node) وأن هذه العُقد متصلة بمساعدة الحواف.يمكننا هنا وضع المسافة بين هذه المدن على الحواف، أي أننا نضع بعض الوزن على حواف الرسم البياني. ويسمى الرسم البياني بالغير موزون، إذا لم يكن هناك وزن على الحواف.

3. الرسم البياني الدوري وغير الدوري(Cyclic and Acyclic Graph):يسمى الرسم البياني بالدوري إذا احتوي على دورة (إذا بدأت من عقدة وبعد اجتياز بعض العقد، تصل إلى نفس العقدة)، ويلزم وجود دورة واحدة على الأقل. ويسمى الرسم البياني بالغير دوري إذا لم تكن هناك دورة موجودة في الرسم البياني.

4. رسم بياني متصل وغير متصل (Connected and Disconnected Graph): في الرسم البياني المتصل، من كل عقدة يوجد مسار لجميع العقد الأخرى، أي من كل عقدة، يمكنك الوصول إلى جميع العقد الأخرى للرسم البياني.لكن في الرسم البياني غير المتصل، لا يمكنك الوصول إلى جميع العقد من عقدة معينة.

5. الرسم البياني الكثيف والمتفرق (Sparse and Dense Graph): الرسم البياني هو الرسم البياني الكثيف إذا كان عدد حواف الرسم البياني قريبًا من العدد الإجمالي للحواف المحتملة لذلك الرسم البياني، وإلا يُقال إنه رسم بياني متقطع.على سبيل المثال، إذا كان الرسم البياني عبارة عن رسم بياني غير موجه وكان هناك 5 عقد، فسيكون العدد الإجمالي للحواف الممكنة “n* (n-1) / 2” أي “5*(5-1)/ 2 = 10”. الآن، إذا كان الرسم البيانييحتوي على 4 حواف، فإنا نسميه بالرسم البياني المتفرق لأن 4 أقل من 10 جدًا. وإذا كان الرسم البياني يحتوي على 8 عقد، فإنا نسميه بالرسم البياني الكثيف لأن الرقم 8 قريب من 10 أي العدد الإجمالي للحواف المحتملة.

كيف يتم تمثيل الـ Graph برمجياً؟

• Adjacency List: ونقوم بأنشاء الرسم البياني باستخدام مصفوفة من نوع “list”، حيث يكون حجم المصفوفة يساوي عدد العقد (nodes). ويمثل ([array[i) قائمة العقد المجاورة للعقدة (i).

• Adjacency Matrix: ونقوم بأنشاء الرسم البياني باستخدام مصفوفة ثنائية الأبعاد بحجم (V x V)، حيث (V) هو عدد العقد في الرسم البياني كامل. تشير ([matrix[i][j) إلى وجود حافة (edges) من العقدة (i) إلى العقدة (j).

لماذا الرسوم البيانية مهمة؟

يمكن استخدام “graph” لتمثيل أي موقف يكون لدينا فيه أشياء مرتبطة ببعضها البعض في أزواج؛على سبيل المثال، يمكن تمثيل كل ما يلي برسوم بيانية:

أشجار العائلة: اجعل “nodes” هي افراد العائلة، “edge” من كل والد لكل طفل من أطفالهم.

شبكات النقل: اجعل “nodes” هي المطارات والتقاطعات والموانئ وما إلى ذلك. “edges” هي رحلات الطيران والطرق ذات الاتجاه الواحد ومسارات الشحن وما إلى ذلك.

تعيينات:اجعل “nodes” اما صف دراسي أو مجموعة الطلبة في الصف الواحد، وقم بوضع “edges” من صف دراسي إلى مجموعة الطلبة إذا تم تخصيص صف للطلبة.

العمليات على الرسوم البيانية Graph:

يمكننا استخراج المعلومات منها، مثل: هل هذه الـ “graph” متصلة؟، ما هو أقصر مسارفي هذه الـ “graph” من العقدة “s” إلى العقدة “t”؟، أو كم عدد “edges” التي يمكنني إزالتها من هذا الرسم البياني قبل أن يتعذر الوصول إلى بعض عقدة من عقدة أخرى؟، هناك خوارزميات قياسية لاستخدام الـ “graph” ولإجابة على كل هذه الأسئلة مثل خوارزميات (DFS, BFS) وغيرها.