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

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

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

أولاً ، دعنا نرى ما هو الرسم البياني؟ إنه تمثيل للبيانات في بنية غير خطية تتكون من عقد (أو رؤوس) وحواف (أو مسارات).

يمكن تسمية الرسم البياني في بنية البيانات بهيكل بيانات يتكون من بيانات مخزنة بين العديد من مجموعات الحواف (المسارات) والرؤوس (العقد) ، المترابطة. هيكل بيانات الرسم البياني (N ، E) منظم بمجموعة من العقد والحواف. يجب أن تكون كل من العقد والرؤوس محدودة.

في تمثيل الرسم البياني أعلاه ، مجموعة العقد هي N = {0،1،2،3،4،5،6} ومجموعة الحواف هي

G = {01،12،23،34،45،05،03}

الآن دعنا ندرس أنواع الرسوم البيانية.

قراءة: أفضل 10 تقنيات لتصور البيانات

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

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

الرسوم البيانية التي تحتوي حوافها أو مساراتها على قيم. تسمى جميع القيم التي يتم رؤيتها المرتبطة بالحواف بالأوزان. يمكن أن تمثل قيمة الحواف الوزن / التكلفة / الطول.

قد تمثل القيم أو الأوزان أيضًا:

• المسافة المقطوعة بين نقطتين - مثال: للبحث عن أقصر طريق إلى المكتب ، المسافة بين محطتي عمل في شبكة مكتب.
• سرعة حزمة البيانات في الشبكة أو النطاق الترددي.

2. رسم بياني غير مرجح

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

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

حيث يتم توصيل مجموعة من الكائنات ، وتكون جميع الحواف ثنائية الاتجاه. الصورة أدناه توضح الرسم البياني غير المباشر ،

إنه مثل ارتباط اثنين من مستخدمي Facebook بعد الاتصال كصديق. يمكن لكلا المستخدمين الرجوع ومشاركة الصور والتعليق بين بعضهم البعض.

4. الرسم البياني الموجه

يُطلق عليه أيضًا اسم Digraph ، حيث يتم توصيل مجموعة من الكائنات (N ، E) ، ويتم توجيه جميع الحواف من عقدة إلى أخرى. تعرض الصورة أعلاه الرسم البياني الموجه.

الخروج: مشاريع تصور البيانات التي يمكنك تكرارها

تخزين الرسم البياني

كل طريقة تخزين لها مزاياها وعيوبها ، ويتم اختيار طريقة التخزين المناسبة بناءً على درجة التعقيد. هياكل البيانات الأكثر استخدامًا لتخزين الرسوم البيانية هما:

1. قائمة الجوار

هنا يتم تخزين العقد كفهرس للمصفوفة ذات البعد الواحد متبوعة بالحواف التي يتم تخزينها كقائمة.

2. مصفوفة الجوار

يتم هنا تمثيل العقد كمؤشر لصفيف ثنائي الأبعاد ، متبوعًا بحواف ممثلة كقيم غير صفرية لمصفوفة مجاورة.

تعرض كل من الصفوف والأعمدة العقد ؛ تمتلئ المصفوفة بأكملها إما بـ "0" أو "1" ، مما يمثل صواب أو خطأ. يمثل الصفر أنه لا يوجد مسار ، ويمثل الرقم 1 مسارًا.

اجتياز الرسم البياني

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

هناك نوعان من هياكل اجتياز الرسم البياني.

1. DFS (عمق البحث الأول): طريقة البحث المتعمق

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

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

الخطوات المتبعة لتنفيذ بحث DFS:

الخطوة 1 - يجب تحديد حجم المكدس بناءً على العدد الإجمالي للعقد.

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

الخطوة 3 - الآن ، قم بزيارة العقدة المجاورة التي لم تتم زيارتها من قبل وادفعها إلى المكدس.

الخطوة 4 - كرر الخطوة 3 حتى لا توجد عقدة مجاورة لم تتم زيارتها.

الخطوة 5 - استخدم التراجع وعقدة واحدة عندما لا تكون هناك عقد أخرى يمكن زيارتها.

الخطوة 6 - إفراغ المكدس بتكرار الخطوتين 3 و 4 و 5.

الخطوة 7 - عندما تكون المكدس فارغة ، يتم تشكيل شجرة ممتدة نهائية عن طريق التخلص من الحواف غير المستخدمة.

تطبيقات DFS هي:

• حل الألغاز بحل واحد فقط.
• لاختبار ما إذا كان الرسم البياني ثنائي الجزء.
• الفرز الطوبولوجي لجدولة العمل والعديد من الوظائف الأخرى.

2. BFS (بحث العرض الأول): يتم تنفيذ البحث باستخدام طريقة قائمة الانتظار

يتنقل بحث Breadth-First في الرسم البياني في حركة عرضية ويستخدم على أساس قائمة الانتظار للانتقال من عقدة إلى أخرى ، بعد مواجهة نهاية في المسار.

الخطوات المتبعة لتنفيذ بحث BFS ،

الخطوة 1 - بناءً على عدد العقد ، يتم تحديد قائمة الانتظار.

الخطوة 2 - ابدأ من أي عقدة للاجتياز. قم بزيارة تلك العقدة وأضفها إلى قائمة الانتظار.

الخطوة 3 - تحقق الآن من العقدة المجاورة التي لم تتم زيارتها ، والتي توجد أمام قائمة الانتظار ، وأضفها إلى قائمة الانتظار ، وليس إلى البداية.

الخطوة 4 - ابدأ الآن في حذف العقدة التي لا تحتوي على أي حواف تحتاج إلى زيارتها وليست في قائمة الانتظار.

الخطوة 5 - إفراغ قائمة الانتظار بتكرار الخطوتين 4 و 5.

الخطوة 6 - قم بإزالة الحواف غير المستخدمة وشكل الشجرة الممتدة فقط بعد أن تصبح قائمة الانتظار فارغة.

تطبيقات BFS هي:

• شبكات نظير إلى نظير- كما هو الحال في Bittorrent ، يتم استخدامها للعثور على جميع العقد المجاورة.
• الزواحف في محرك البحث.
• مواقع الشبكات الاجتماعية وغيرها الكثير.

تطبيقات العالم الحقيقي للرسم البياني في بنية البيانات

تُستخدم الرسوم البيانية في العديد من التطبيقات اليومية مثل تمثيل الشبكة (الطرق ، ورسم خرائط الألياف الضوئية ، وتصميم لوحة الدوائر ، وما إلى ذلك). مثال: في شبكة بيانات Facebook ، تمثل العقد المستخدم ، وصورته أو تعليقه ، وتمثل الحواف الصور والتعليقات على الصورة.

يحتوي الرسم البياني في بنية البيانات على تطبيقات واسعة النطاق. ومن أبرزها:

• واجهات برمجة تطبيقات الرسم البياني الاجتماعي - إنها الطريقة الأساسية التي يتم بها توصيل البيانات داخل وخارج منصة التواصل الاجتماعي على Facebook. إنها واجهة برمجة تطبيقات تعتمد على HTTP ، وتُستخدم للاستعلام عن البيانات برمجيًا ، وتحميل الصور ومقاطع الفيديو ، وإنشاء قصص جديدة ، والعديد من المهام الأخرى. وهو يتألف من العقد والحواف والحقول. للاستعلام ، يتم استخدام عقد الكائن المحدد. حواف لمجموعة من الكائنات تخضع لكائن واحد والحقول تستخدم لجلب البيانات حول كل كائن بين المجموعة.
• واجهة برمجة تطبيقات GraphQL الخاصة بـ Yelp - إنها محرك توصيات يُستخدم لجلب البيانات المحددة من منصة Yelp. هنا ، تُستخدم الأوامر للعثور على الحواف ، وبعد ذلك يتم الاستعلام عن العقدة المحددة لجلب النتيجة الدقيقة. هذا يسرع عملية الاسترجاع.

على منصة Yelp ، تمثل العقد النشاط التجاري ، وتحتوي على المعرف والاسم والمغلق والعديد من خصائص الرسم البياني الأخرى.

• خوارزميات تحسين المسار- يتم استخدامها للعثور على أفضل اتصال يناسب معايير السرعة والأمان والوقود وما إلى ذلك. يتم استخدام BFS في هذه الخوارزمية. أفضل مثال على ذلك هو Google Maps Platform (الخرائط ، واجهات برمجة التطبيقات للطرق).
• شبكات الطيران- في شبكات الطيران ، يتم استخدام هذا للعثور على المسار الأمثل الذي يناسب بنية بيانات الرسم البياني . يساعد هذا أيضًا في النموذج ويحسن إجراءات المطار بكفاءة.

اقرأ أيضًا: فوائد تصور البيانات

خاتمة

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

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

لماذا تختار دورة مع upGrad ؟

نوصيك باختيار برنامج Executive PG في علوم البيانات الذي يقدمه معهد IIIT Bangalore المستضاف على upGrad لأنه يمكنك هنا الحصول على استفساراتك 1-1 مع مدربي الدورة التدريبية. لا يركز فقط على التعلم النظري ولكنه يعطي أهمية للمعرفة العملية ، وهو أمر ضروري لإعداد المتعلمين لمواجهة مشاريع العالم الحقيقي وتزويدك بشهادة NASSCOM الأولى في الهند ، والتي تساعدك في الحصول على وظائف عالية الأجر في علوم البيانات.

تم الاستشهاد بالأعمال

قسم الرياضيات / علوم الكمبيوتر - الصفحة الرئيسية ، www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/data-stru.html.

"الرياضيات إنسايت." تعريف الرسم البياني الموجه - الرياضيات إنسايت ، mathinsight.org/definition/directed_graph.

سينغ ، أمريتبال. "هيكل بيانات الرسم البياني." متوسطة ، متوسطة ، 29 مارس 2020 ، medium.com/@singhamritpal49/graph-data-structure-49427c81b3b3.

منفرد. "التطبيقات الواقعية لهياكل بيانات الرسم البياني التي يجب أن تعرفها." بيانات الرسم البياني و GraphQL API Development-Leap Graph ، leapgraph.com/graph-data-structures-applications.