الرسم البياني (نوع البيانات المجردة)

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 22 صور
الموسوعة الحرة
رسم بياني موجه بثلاثة رؤوس (دوائر زرقاء) وثلاثة حواف (أسهم سوداء).

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

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

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

العمليات

مخطط فئات UML للرسم البياني (نوع بيانات مجرد)
مخطط فئات UML للرسم البياني (نوع بيانات مجرد)

تتضمن العمليات الأساسية التي توفرها بنية بيانات الرسم البياني G عادةً ما يلي: [ 1 ]

  • المتجاور ( G ، x ، y ) : يختبر ما إذا كان هناك حافة من الرأس x إلى الرأس y ؛
  • neighbors( G , x ) : lists all vertices y such that there are a edge from the vertex x to the vertex y ;
  • add_vertex( G , x ) : يضيف الرأس x ، إذا لم يكن موجودًا؛
  • remove_vertex( G , x ) : يزيل الرأس x ، إذا كان موجودًا؛
  • add_edge( G , x , y , z ) : يضيف الحافة z من الرأس x إلى الرأس y ، إذا لم تكن موجودة؛
  • remove_edge( G , x , y ) : يزيل الحافة من الرأس x إلى الرأس y ، إذا كانت موجودة؛
  • get_vertex_value( G , x ) : تُرجع القيمة المرتبطة بالرأس x ؛
  • set_vertex_value( G , x , v ) : تعيين القيمة المرتبطة بالرأس x إلى v .

عادةً ما توفر الهياكل التي تربط القيم بالحواف أيضًا ما يلي: [ 1 ]

  • get_edge_value( G , x , y ) : تُرجع القيمة المرتبطة بالحافة ( x , y );
  • set_edge_value( G , x , y , v ) : تعيين القيمة المرتبطة بالحافة ( x , y ) إلى v .

هياكل البيانات الشائعة لتمثيل الرسوم البيانية

قائمة الجوار [ 2 ]
تُخزَّن الرؤوس كسجلات أو كائنات، ويخزن كل رأس قائمة بالرؤوس المجاورة له. يسمح هذا الهيكل بتخزين بيانات إضافية على الرؤوس. ويمكن تخزين بيانات إضافية إذا تم تخزين الحواف أيضًا ككائنات، وفي هذه الحالة يخزن كل رأس حوافه المتصلة به، وتخزن كل حافة رؤوسها المتصلة بها.
مصفوفة التجاور [ 3 ]
مصفوفة ثنائية الأبعاد، حيث تمثل الصفوف رؤوس المصدر وتمثل الأعمدة رؤوس الوجهة. يجب تخزين بيانات الحواف والرؤوس خارجيًا. لا يمكن تخزين سوى تكلفة حافة واحدة بين كل زوج من الرؤوس.
مصفوفة الحدوث [ 4 ]
مصفوفة ثنائية الأبعاد، حيث تمثل الصفوف الرؤوس وتمثل الأعمدة الحواف. تشير القيم إلى علاقة التداخل بين الرأس في صف معين والحافة في عمود معين.

يوضح الجدول التالي تكلفة التعقيد الزمني لإجراء عمليات مختلفة على الرسوم البيانية، لكل تمثيل من هذه التمثيلات، حيث يمثل | V | عدد الرؤوس و| E | عدد الحواف. في تمثيلات المصفوفة، تُمثل المدخلات تكلفة تتبع حافة. ​​أما تكلفة الحواف غير الموجودة فتُفترض أنها ∞.

قائمة الجوارمصفوفة التجاورمصفوفة الحدوث
مخطط المتجريا(|V|+|هـ|){\displaystyle O(|V|+|E|)}يا(|V|2){\displaystyle O(|V|^{2})}يا(|V|⋅|هـ|){\displaystyle O(|V|\cdot |E|)}
إضافة رأسيا(1){\displaystyle O(1)}يا(|V|2){\displaystyle O(|V|^{2})}يا(|V|⋅|هـ|){\displaystyle O(|V|\cdot |E|)}
إضافة حافةيا(1){\displaystyle O(1)}يا(1){\displaystyle O(1)}يا(|V|⋅|هـ|){\displaystyle O(|V|\cdot |E|)}
إزالة الرأسيا(|هـ|){\displaystyle O(|E|)}يا(|V|2){\displaystyle O(|V|^{2})}يا(|V|⋅|هـ|){\displaystyle O(|V|\cdot |E|)}
إزالة الحافةيا(|V|){\displaystyle O(|V|)}يا(1){\displaystyle O(1)}يا(|V|⋅|هـ|){\displaystyle O(|V|\cdot |E|)}
هل الرؤوس x و y متجاورة (بافتراض أن مواقع تخزينها معروفة)؟يا(|V|){\displaystyle O(|V|)}يا(1){\displaystyle O(1)}يا(|هـ|){\displaystyle O(|E|)}
ملاحظاتعملية إزالة الرؤوس والحواف بطيئة، لأنها تحتاج إلى إيجاد جميع الرؤوس أو الحواف.بطيء في إضافة أو إزالة الرؤوس، لأن المصفوفة يجب تغيير حجمها/نسخها.بطيء في إضافة أو إزالة الرؤوس والحواف، لأن المصفوفة يجب تغيير حجمها/نسخها.

تُفضّل قوائم التجاور عمومًا لتمثيل الرسوم البيانية المتفرقة ، بينما تُفضّل مصفوفة التجاور إذا كان الرسم البياني كثيفًا؛ أي عدد الحواف|هـ|{\displaystyle |E|}يقترب من مربع عدد الرؤوس،|V|2{\displaystyle |V|^{2}}أو إذا كان من الضروري أن يكون المرء قادراً على البحث بسرعة عما إذا كان هناك ضلع يربط بين رأسين. [ 5 ] [ 6 ]

تمثيل أكثر كفاءة لمجموعات التجاور

يمكن تحسين التعقيد الزمني للعمليات في تمثيل قائمة التجاور عن طريق تخزين مجموعات الرؤوس المتجاورة في هياكل بيانات أكثر كفاءة، مثل جداول التجزئة أو أشجار البحث الثنائية المتوازنة (يتطلب التمثيل الأخير تحديد الرؤوس بواسطة عناصر مجموعة مرتبة خطيًا، مثل الأعداد الصحيحة أو السلاسل النصية). يؤدي تمثيل الرؤوس المتجاورة عبر جداول التجزئة إلى متوسط ​​تعقيد زمني مُستهلك قدرهيا(1){\displaystyle O(1)}لاختبار تجاور رأسين معطيين ولإزالة حافة ومتوسط ​​تعقيد زمني مستهلك [ 7 ] لـيا(درجة⁡(x)){\displaystyle O(\deg(x))}لإزالة رأس معين x من الدرجةدرجة⁡(x){\displaystyle \deg(x)}. لا يتغير التعقيد الزمني للعمليات الأخرى ولا متطلبات المساحة التقاربية.

التمثيلات المتوازية

يواجه توازي مسائل الرسوم البيانية تحديات كبيرة، منها: الحسابات القائمة على البيانات، والمسائل غير المهيكلة، وضعف التوطين، وارتفاع نسبة الوصول إلى البيانات إلى الحساب. [ 8 ] [ 9 ] يلعب تمثيل الرسم البياني المستخدم في البنى المتوازية دورًا هامًا في مواجهة هذه التحديات. قد تؤدي التمثيلات المختارة بشكل سيئ إلى زيادة تكلفة الاتصال للخوارزمية دون داعٍ، مما يقلل من قابليتها للتوسع . فيما يلي، نتناول بنى الذاكرة المشتركة والموزعة.

الذاكرة المشتركة

في حالة نموذج الذاكرة المشتركة ، تكون تمثيلات الرسم البياني المستخدمة للمعالجة المتوازية هي نفسها كما في الحالة التسلسلية، [ 10 ] لأن الوصول المتوازي للقراءة فقط إلى تمثيل الرسم البياني (على سبيل المثال قائمة التجاور ) فعال في الذاكرة المشتركة.

الذاكرة الموزعة

في نموذج الذاكرة الموزعة ، يتمثل النهج المعتاد في تقسيم مجموعة الرؤوسV{\displaystyle V}من الرسم البياني إلىص{\displaystyle p}مجموعاتV0،...،Vص-1{\displaystyle V_{0},\dots ,V_{p-1}}. هنا،ص{\displaystyle p}يمثل هذا عدد عناصر المعالجة المتاحة (PE). تُوزَّع أقسام مجموعة الرؤوس على عناصر المعالجة ذات الفهرس المطابق، بالإضافة إلى الحواف المقابلة. لكل عنصر معالجة تمثيله الخاص في الرسم البياني الفرعي ، حيث تتطلب الحواف ذات نقطة النهاية في قسم آخر عناية خاصة. بالنسبة لواجهات الاتصال القياسية مثل MPI ، يجب أن يكون معرّف عنصر المعالجة الذي يمتلك نقطة النهاية الأخرى قابلاً للتحديد. أثناء الحساب في خوارزميات الرسم البياني الموزع، يُعدّ تمرير المعلومات على طول هذه الحواف بمثابة اتصال. [ 10 ]

يتطلب تقسيم الرسم البياني عناية فائقة، إذ توجد مفاضلة بين انخفاض مستوى الاتصال وتقسيم البيانات إلى أجزاء متساوية الحجم [ 11 ]. إلا أن تقسيم الرسم البياني يُعدّ مسألة صعبة الحل (NP-hard)، لذا لا يمكن حسابها. وبدلاً من ذلك، تُستخدم الطرق الاستدلالية التالية.

التقسيم أحادي البعد: يحصل كل معالج علىن/ص{\displaystyle n/p}الرؤوس والحواف الخارجة المقابلة لها. يمكن فهم ذلك على أنه تفكيك صفّي أو عمودي لمصفوفة التجاور. بالنسبة للخوارزميات التي تعمل على هذا التمثيل، يتطلب ذلك خطوة اتصال شاملة (All-to-All) بالإضافة إلىيا(م){\displaystyle {\mathcal {O}}(m)}أحجام مخزن الرسائل، حيث أن كل وحدة معالجة (PE) لديها حواف صادرة محتملة إلى كل وحدة معالجة أخرى. [ 12 ]

التقسيم ثنائي الأبعاد: يحصل كل معالج على مصفوفة فرعية من مصفوفة التجاور. افترض أن المعالجات محاذية في مستطيل.ص=صر×صج{\displaystyle p=p_{r}\times p_{c}}، أينصر{\displaystyle p_{r}}وصج{\displaystyle p_{c}}يمثل كل صف وعمود عدد عناصر المعالجة، على التوالي. ثم يحصل كل معالج على مصفوفة فرعية من مصفوفة التجاور ذات البعد(ن/صر)×(ن/صج){\displaystyle (n/p_{r})\times (n/p_{c})}يمكن تصور ذلك كنمط رقعة الشطرنج في مصفوفة. [ 12 ] لذلك، لا يمكن أن يكون لكل وحدة معالجة إلا حواف صادرة إلى وحدات المعالجة في نفس الصف والعمود. هذا يحد من عدد شركاء الاتصال لكل وحدة معالجة.صر+صج-1{\displaystyle p_{r}+p_{c}-1}من خارجص=صر×صج{\displaystyle p=p_{r}\times p_{c}}من الممكن.

تمثيلات مضغوطة

تُستخدم الرسوم البيانية التي تحتوي على تريليونات الحواف في مجالات التعلم الآلي ، وتحليل الشبكات الاجتماعية ، وغيرها. وقد طُوّرت تمثيلات مضغوطة للرسوم البيانية لتقليل متطلبات الإدخال/الإخراج والذاكرة. تُطبّق تقنيات عامة مثل ترميز هوفمان ، ولكن يمكن معالجة قائمة التجاور أو مصفوفة التجاور بطرق محددة لزيادة الكفاءة. [ 13 ]

تطبيقات الرسوم البيانية

يُعدّ كلٌّ من البحث بالعرض أولًا (BFS) والبحث بالعمق أولًا (DFS) منهجين مترابطين يُستخدمان لاستكشاف جميع العُقد في مُكوِّن مُتصل مُحدد . يبدأ كلاهما بعقدة عشوائية، تُسمى " الجذر ". [ 14 ] يُمكن أيضًا إيجاد المُكوِّنات المُتصلة بقوة باستخدام عمليات اجتياز الرسم البياني بواسطة خوارزميات مثل خوارزمية كوساراجو ، وهي نسخة مُعدّلة من خوارزمية البحث بالعمق أولًا.

إيجاد المسار

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

انظر أيضاً

مراجع

  1. ١ ٢ انظر، على سبيل المثال، Goodrich & Tamassia (2015) ، القسم 13.1.2: العمليات على الرسوم البيانية، صفحة 360. لمزيد من التفاصيل حول العمليات، انظر Mehlhorn, K. ; Näher, S. (1999). "الفصل 6: الرسوم البيانية وهياكل بياناتها". LEDA: منصة للحوسبة التوافقية والهندسية (ملف PDF) . مطبعة جامعة كامبريدج. الصفحات 240-282 . 
  2. ^ كورمين وآخرون. (2001) ، ص 528-529؛ جودريتش وتاماسيا (2015) ، الصفحات من 361 إلى 362.
  3. ^ كورمين وآخرون. (2001) ، ص 529-530؛ جودريتش وتاماسيا (2015) ، ص. 363.
  4. ↑ كورمن وآخرون (2001) ، التمرين 22.1-7، ص 531.
  5. ↑ كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001). "القسم 22.1: تمثيلات الرسوم البيانية". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 527-531 . ISBN   0-262-03293-7.
  6. ↑ غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2015). "القسم 13.1: مصطلحات الرسوم البيانية وتمثيلاتها". تصميم الخوارزميات وتطبيقاتها . وايلي. ص 355-364 . ISBN  978-1-118-33591-8.
  7. ↑ كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2009). مقدمة في الخوارزميات ( الطبعة الثالثة). معهد ماساتشوستس للتكنولوجيا. الصفحات 253-280 . ISBN   978-0-262-03384-8.
  8. ↑ بادر، ديفيد؛ مايرهينكه، هينينغ؛ ساندرز، بيتر؛ فاغنر، دوروثيا (يناير 2013). تقسيم الرسوم البيانية وتجميعها . الرياضيات المعاصرة. المجلد 588. الجمعية الرياضية الأمريكية. doi : 10.1090/conm/588/11709 . ISBN  978-0-8218-9038-7.
  9. ↑ لومسدين، أندرو؛ غريغور، دوغلاس؛ هندريكسون، بروس؛ بيري، جوناثان (مارس 2007). "تحديات في معالجة الرسوم البيانية المتوازية". رسائل المعالجة المتوازية . 17 (1): 5-20 . doi : 10.1142/s0129626407002843 . ISSN 0129-6264 . 
  10. 1 2 ساندرز، بيتر؛ ميلهورن، كورت؛ ديتزفيلبينجر، مارتن؛ ديمينتييف، رومان (2019). الخوارزميات المتسلسلة والمتوازية وهياكل البيانات: مجموعة الأدوات الأساسية . دار نشر سبرينغر الدولية. ISBN 978-3-030-25208-3.
  11. ↑ "المعالجة المتوازية للرسوم البيانية" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 25 أغسطس 2021. تم الاطلاع عليه بتاريخ 9 مارس 2020 .
  12. 1 2 بولوتش، أ.؛ مادوري، كاميش (2011). "التطبيقات". البحث المتوازي بالعرض أولاً على أنظمة الذاكرة الموزعة . المؤتمر الدولي لعام 2011 للحوسبة عالية الأداء والشبكات والتخزين والتحليل. CiteSeerX 10.1.1.767.5248 . doi : 10.1145/2063384.2063471 . ISBN  978-1-4503-0771-0. S2CID 6540738 . 
  13. ↑ بيستا، ماسيج؛ هوفلر، تورستن (27 أبريل 2019). "مسح وتصنيف لضغط الرسوم البيانية بدون فقدان البيانات وتمثيلات الرسوم البيانية ذات الكفاءة المكانية". arXiv : 1806.01799 [ cs.DS ].
  14. ↑ بورتي (يوليو–سبتمبر 2018). "اجتيازات الرسوم البيانية وتطبيقاتها" (ملف PDF) . المجلة الدولية للبحوث والمراجعات التحليلية . 5 (3): 2.