أنواع الرسوم البيانية في بنية البيانات مع الأمثلة

أنواع الرسوم البيانية في بنية البيانات

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

يمكن أن تكون الرسوم البيانية من أنواع متعددة، اعتمادًا على موضع العقد والحواف. فيما يلي بعض الأنواع المهمة من الرسوم البيانية:

مخطط موجه

تحتوي حواف الرسم البياني الموجه على أسهم تشير إلى الاتجاه. يحدد السهم المكان الذي تشير إليه الحافة أو تنتهي.

فيما يلي مثال على الرسم البياني الموجه.

مخطط موجه
مخطط موجه
  • يمكننا الانتقال من العقدة A إلى D.
  • ومع ذلك، لا يمكننا الانتقال من العقدة D إلى العقدة A حيث تشير الحافة من A إلى D.
  • نظرًا لأن الرسم البياني لا يحتوي على أوزان، فإن السفر من الرأس A إلى D سيكلف نفس تكلفة السفر من D إلى F.

رسم بياني غير موجه

الرسم البياني غير الموجه يحتوي على حواف بدون مؤشرات. وهذا يعني أنه يمكننا السفر بالعكس بين قمتين.

فيما يلي مثال بسيط على الرسم البياني غير الموجه.

رسم بياني غير موجه
رسم بياني غير موجه

في الرسم البياني أعلاه،

  • يمكننا الانتقال من (أ) إلى (ب).
  • يمكننا أيضًا الانتقال من B إلى A
  • الحواف لا تحتوي على اتجاهات.

إنه مثال على رسم بياني غير موجه يحتوي على عدد محدود من القمم والحواف بدون أوزان.

الرسم البياني المرجح

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

فيما يلي مثال على الرسم البياني الموزون (الموجه).

الرسم البياني الموجه مع الوزن
الرسم البياني الموجه مع الوزن
  • من A إلى B، هناك حافة، والوزن هو 5، مما يعني أن الانتقال من A إلى B سيكلفنا 5.
  • نقطة إلى B، ولكن في هذا الرسم البياني، B ليس لها حافة مباشرة على A. لذلك، لا يمكننا السفر من B إلى A.
  • ومع ذلك، إذا أردنا الانتقال من A إلى F، فهناك مسارات متعددة. المسارات هي ADF، ABF. تبلغ تكلفة وحدة تغذية المستندات التلقائية (10+11) أو 21.
  • هنا، سيكلف المسار ABF (5+15) أو 20. هنا نقوم بإضافة وزن كل حافة في المسار.

فيما يلي مثال على الرسم البياني غير الموجه مع الأوزان:

الرسم البياني غير الموجه مع الوزن
الرسم البياني غير الموجه مع الوزن

هنا، الحافة لها وزن ولكن ليس لها اتجاه. وهذا يعني أن السفر من الرأس A إلى D سيكلف 10 والعكس صحيح.

الرسم البياني ثنائي الاتجاه

الرسوم البيانية ثنائية الاتجاه وغير الموجهة لها خاصية مشتركة. إنه

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

فمثلا:

الرسم البياني ثنائي الاتجاه

  • هنا، الانتقال من A إلى D أو D إلى A سيكلف 10.
  • في الرسم البياني ثنائي الاتجاه، يمكن أن يكون لدينا حافتان بين رأسين.

وإليك مثال على ذلك:

الرسم البياني ثنائي الاتجاه
الرسم البياني ثنائي الاتجاه

سيكلفنا السفر من A إلى D 17 دولارًا، لكن السفر من D إلى A سيكلفنا 12 دولارًا. لذا، لا يمكننا تخصيص وزنين مختلفين إذا كان الرسم البياني غير موجه.

رسم لانهائي

سيحتوي الرسم البياني على عدد لا نهائي من الحواف والعقد. إذا كان الرسم البياني لا نهائيًا وهو أيضًا رسم بياني متصل، فإنه سيحتوي على عدد لا نهائي من الحواف أيضًا. هنا، تعني الحواف الممتدة أنه قد يتم توصيل المزيد من الحواف بهذه العقد عبر الحواف.

فيما يلي مثال على الرسم البياني اللانهائي:

رسم لانهائي
رسم لانهائي

رسم بياني فارغ

يحتوي الرسم البياني Null Graph على العقد أو القمم فقط ولكن بدون حواف. إذا تم إعطاء رسم بياني G = (V, E)، حيث V هي القمم وE هي الحواف، فسيكون فارغًا إذا كان عدد الحواف E هو صفر.

فيما يلي مثال على الرسم البياني الفارغ:

رسم بياني فارغ
رسم بياني فارغ

الرسم البياني تافهة

تعتبر بنية بيانات الرسم البياني تافهة في حالة وجود قمة أو عقدة واحدة فقط بدون حواف.

فيما يلي مثال على الرسم البياني التافه:

الرسم البياني تافهة

رسم بياني متعدد

يُسمى الرسم البياني رسمًا بيانيًا متعددًا عند وجود حواف متعددة بين رأسين، أو عندما يكون للرأس حلقة. المصطلح "حلقة" في بنية بيانات الرسم البياني يعني حافة تشير إلى نفس العقدة أو الرأس. يمكن توجيه Multigraph أو غير موجه.

فيما يلي مثال على الرسم البياني المتعدد:

رسم بياني متعدد

هناك حافتان من B إلى A. علاوة على ذلك، فإن الرأس E لديه حلقة ذاتية. الرسم البياني أعلاه هو رسم بياني موجه بدون أوزان على الحواف.

الرسم البياني الكامل

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

لنفترض أن هناك إجمالي عدد V من القمم وكل قمة لها حواف V-1 بالضبط. بعد ذلك، سيتم تسمية هذا الرسم البياني بالرسم البياني الكامل. في هذا النوع من الرسم البياني، يتم توصيل كل قمة بجميع القمم الأخرى عبر الحواف.

فيما يلي مثال على رسم بياني كامل بخمسة رؤوس:

الرسم البياني الكامل

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

الرسم البياني المتصل

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

فيما يلي مثال على الرسم البياني المتصل:

الرسم البياني المتصل

فيما يلي بعض التوضيحات للرسم البياني "مثال الرسم البياني الكامل" أعلاه:

  • بافتراض عدم وجود حافة بين C وF، لا يمكننا السفر من A إلى G. ومع ذلك، فإن الحافة C إلى F تمكننا من السفر إلى أي عقدة من عقدة معينة.
  • الرسم البياني الكامل هو رسم بياني متصل لأنه يمكننا الانتقال من عقدة إلى أي عقدة أخرى في الرسم البياني المحدد.

الرسم البياني الدوري

يقال أن الرسم البياني دوري إذا كانت هناك دورة واحدة أو أكثر موجودة في الرسم البياني.

فيما يلي مثال على الرسم البياني الدوري:

الرسم البياني الدوري

هنا تشكل الرؤوس A وB وC دورة.

يمكن أن يحتوي الرسم البياني على دورات متعددة بداخله.

رسم بياني دوري موجه (DAG)

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

فيما يلي مثال بسيط للرسم البياني الحلقي الموجه (DAG):

رسم بياني دوري موجه (DAG)

الرسم البياني للدورة

الرسم البياني للدورة ليس هو نفسه الرسم البياني الدوري. في Cycle Graph، سيكون لكل عقدة حافتان متصلتان تمامًا، مما يعني أن كل عقدة سيكون لها درجتان بالضبط.

فيما يلي مثال على الرسم البياني للدورة:

الرسم البياني للدورة

رسم بياني ثنائي

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

يجب أن يتبع الرسم البياني الثنائي القاعدة:

  • يجب أن تكون مجموعتان من القمم متميزتين، مما يعني أنه يجب تقسيم جميع القمم إلى مجموعتين أو مجموعتين.
  • يجب ألا تشكل القمم نفسها أي حواف.

رسم بياني ثنائي

الرسم البياني أويلر

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

وفيما يلي مثال على الرسم البياني أويلر:

الرسم البياني أويلر

جميع القمم لها درجات زوجية. تحتوي Vertex A وD وE وH على درجتين. هنا، العقدة C لها أربع درجات، وهي زوجية.

هاميلتون الرسم البياني

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

فيما يلي مثال بياني بسيط لهاملتون:

هاميلتون الرسم البياني

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