هيكل بيانات الرسم البياني و Algorithms (مثال)
فريق التحرير
⚡ ملخص ذكي
تُعدّ بنية بيانات الرسم البياني مجموعة غير خطية من الرؤوس والحواف، حيث تربط كل حافة زوجًا من الرؤوس. تُستخدم الرسوم البيانية لنمذجة الشبكات الواقعية مثل الخرائط والروابط الاجتماعية وصفحات الويب، وتدعم العديد من الخوارزميات القوية.
ما هو الرسم البياني في بنية البيانات؟
الرسم البياني هو بنية بيانات غير خطية تتكون من رؤوس وحواف، حيث تحتوي الرؤوس على المعلومات أو البيانات، وتعمل الحواف كرابط بين زوج من الرؤوس.
يُستخدم هذا النظام لحلّ مشاكل واقعية، مثل إيجاد أفضل مسار للوصول إلى الوجهة المطلوبة، وتحديد مسار الاتصالات وشبكات التواصل الاجتماعي. يُعتبر المستخدمون بمثابة عقدة في الرسم البياني، والأسلاك هي الحواف التي تربطهم.
إذا تم تمثيل الحواف كـ E والرءوس كـ V، فيمكن كتابة الرسم البياني G كمجموعة من القمم والحواف، مثل G (V, E).
مثال على الرسم البياني في بنية البيانات
إليك مثال بسيط على بنية بيانات الرسم البياني:
هو رسم بياني بسيط غير موجه (أحد أنواع الرسوم البيانية). مجموعة الرؤوس هنا هي: {أ، ب، ج، د، هـ، و}. يشكل كل رأسين حافة. على سبيل المثال، يرتبط الرأسان أ و ب بحافة. بينما لا يرتبط الرأسان أ و و بأي حافة.
مصطلحات الرسم البياني في بنية البيانات
فيما يلي بعض المصطلحات المهمة المستخدمة في بنية بيانات الرسم البياني:
| مصطلح | الوصف |
|---|---|
| قمة الرأس | يُطلق على كل عنصر من عناصر البيانات اسم رأس أو عقدة. في الصورة أعلاه، A وB وC وD وE هي الرؤوس. |
| الحافة (القوس) | تُسمى الروابط التي تربط بين عقدتين أو رأسين بالحافة (القوس). ولها طرفان ويتم تمثيلها على النحو التالي: (الرأس البادئ، الرأس النهائي). |
| الحافة غير الموجهة | إنها حافة ثنائية الاتجاه. |
| الحافة الموجهة | إنها حافة أحادية الاتجاه. |
| الحافة المرجحة | حافة ذات قيمة. |
| الدرجة العلمية | في الرسم البياني، يُطلق على عدد الحواف المتصلة برأس ما اسم الدرجة. |
| داخل درجة | إجمالي عدد الحواف الواردة المتصلة بالقمة. |
| درجة خارجية | إجمالي عدد الحواف الصادرة المتصلة بالقمة. |
| حلقة ذاتية | تسمى الحافة بالحلقة الذاتية إذا تطابقت نقطتا النهاية. |
| الملاصقة | يقال إن الرؤوس متجاورة إذا كان هناك ضلع متصل بينها. |
أنواع الرسوم البيانية في بنية البيانات
وهنا قائمة الأكثر شيوعا أنواع الرسوم البيانية في بنية البيانات:
- مخطط موجه
- رسم بياني غير موجه
- الرسم البياني المرجح
- الرسم البياني ثنائي الاتجاه
- رسم لانهائي
- رسم بياني فارغ
- الرسم البياني تافهة
- رسم بياني متعدد
- الرسم البياني الكامل
- الرسم البياني المتصل
- الرسم البياني الدوري
- رسم بياني دوري موجه (DAG)
- الرسم البياني للدورة
- رسم بياني ثنائي
- الرسم البياني أويلر
- هاميلتون الرسم البياني
كيفية تمثيل الرسم البياني في بنية البيانات؟
يُخزَّن الرسم البياني عادةً في الذاكرة باستخدام أحد تمثيلين. ويؤثر هذا الاختيار على مقدار الذاكرة التي يستخدمها الرسم البياني وسرعة تنفيذ العمليات الشائعة.
- مصفوفة التجاور: مصفوفة ثنائية الأبعاد V × V، حيث تكون قيمة الخلية [i][j] تساوي 1 (أو وزن الحافة) إذا كانت هناك حافة بين الرأس i والرأس j، و0 فيما عدا ذلك. تسمح هذه المصفوفة بالبحث عن الحواف في زمن ثابت O(1)، ولكنها تستخدم مساحة O(V²)، مما يجعلها الأنسب للرسوم البيانية الكثيفة.
- قائمة الجوار: مصفوفة من القوائم حيث يخزن كل رأس قائمة برؤوسه المجاورة. تستخدم مساحة O(V + E) وهي فعالة للرسوم البيانية المتفرقة، ولهذا السبب تستخدمها معظم الرسوم البيانية في العالم الحقيقي.
يمكنك قراءة المزيد عن هذه المواضيع في قائمة التجاور وتمثيل المصفوفة للرسم البياني البرنامج التعليمي.
تطبيقات هيكل بيانات الرسم البياني
للرسم البياني استخدامات عديدة، وهناك الكثير من الخوارزميات التي تستخدمه. فيما يلي بعض تطبيقات الرسم البياني:
- Google تستخدم الخرائط الرسوم البيانية لإيجاد تقاطع طريقين وحساب المسافة بين موقعين. على سبيل المثال، ديكسترا، لإيجاد أقصر مسافة بين موقع المصدر وموقع الوجهة.
- يستخدم فيسبوك الرسوم البيانية للعثور على الأصدقاء المشتركين للمستخدمين. وتعتبر خوارزميته كل مستخدم بمثابة عقدة في الرسم البياني.
- لتخصيص الموارد، يتم استخدام الرسم البياني الموجه غير الدوري (DAG). وهو يتحقق من تبعية الموارد.
- استخدم Google تستخدم محركات البحث الرسوم البيانية لإنشاء ترتيب المواقع الإلكترونية.
- خريطةping يستخدم الجهاز بنية بيانات الرسم البياني.
- A راوتر ويستخدم بروتوكوله الرسم البياني لتعلم المسار إلى الوجهة.
