مرحبا.
في هذه المذكرة، قررت أن أدرج هياكل البيانات الرئيسية المستخدمة لتخزين الرسوم البيانية في علوم الكمبيوتر، وسأتحدث أيضًا عن اثنين من هذه الهياكل التي "تبلورت" بطريقة أو بأخرى بالنسبة لي.
لذلك، دعونا نبدأ. ولكن ليس منذ البداية - أعتقد أننا جميعًا نعرف بالفعل ما هو الرسم البياني وما هو (موجه، غير موجه، مرجح، غير مرجح، مع أو بدون حواف وحلقات متعددة).
إذا هيا بنا. ما هي خيارات هياكل البيانات "لتخزين الرسم البياني" المتوفرة لدينا؟
1. هياكل البيانات المصفوفية
1.1 مصفوفة المجاورة. مصفوفة الجوار هي مصفوفة تتوافق فيها عناوين الصفوف والأعمدة مع أرقام رؤوس الرسم البياني، ويتم تحديد قيمة كل عنصر من عناصرها a(i,j) من خلال وجود أو عدم وجود حواف بين القمم i و j (من الواضح أنه بالنسبة للرسم البياني غير الموجه، ستكون هذه المصفوفة متناظرة، أو يمكننا الاتفاق على تخزين جميع القيم فقط فوق القطر الرئيسي). بالنسبة للرسوم البيانية غير الموزونة، يمكن تعيين a(i,j) بعدد الحواف من i إلى j (إذا لم يكن هناك مثل هذه الحافة، ثم a(i,j)= 0)، وبالنسبة للرسوم البيانية الموزونة، أيضًا حسب الوزن (الوزن الإجمالي) للحواف المذكورة.
1.2 مصفوفة الإصابة. في هذه الحالة، يتم تخزين الرسم البياني الخاص بنا أيضًا في جدول، كقاعدة عامة، تتوافق أرقام الصفوف مع أرقام رؤوسه، وتتوافق أرقام الأعمدة مع الحواف المرقمة مسبقًا. إذا كانت قمة الرأس والحافة عرضية لبعضهما البعض، فسيتم كتابة قيمة غير صفرية في الخلية المقابلة (بالنسبة للرسوم البيانية غير الموجهة، تتم كتابة 1 إذا كانت القمة والحافة حادثة، وبالنسبة للرسوم البيانية الموجهة - "1" إذا كانت الحافة "يخرج" من قمة الرأس و "-1" إذا كان "متضمنًا" فيه (من السهل تذكره، لأن علامة "ناقص" تبدو أيضًا "مضمنة" في الرقم "-1")). بالنسبة للرسوم البيانية المرجحة، مرة أخرى، بدلاً من 1 و-1، يمكنك تحديد الوزن الإجمالي للحافة.
2. هياكل بيانات التعداد
2.1 قائمة المجاورة. حسنًا، يبدو أن كل شيء بسيط هنا. يمكن بشكل عام ربط كل قمة في الرسم البياني بأي بنية تعداد (قائمة، متجه، مصفوفة، ...)، والتي ستخزن أرقام جميع الرؤوس المجاورة للواحدة المعطاة. بالنسبة للرسوم البيانية الموجهة، سنضيف إلى هذه القائمة فقط تلك القمم التي توجد لها حافة "موجهة" من قمة الميزة. بالنسبة للرسوم البيانية الموزونة، سيكون التنفيذ أكثر تعقيدًا.
2.2 قائمة الأضلاع. بنية بيانات شائعة جدًا. قائمة الحواف، كما يخبرنا Captain Obviousness، هي في الواقع قائمة من حواف الرسم البياني، يتم تحديد كل منها بواسطة قمة البداية، قمة النهاية (بالنسبة للرسوم البيانية غير الموجهة، الترتيب ليس مهمًا هنا، على الرغم من أنه يمكنك التوحيد استخدم قواعد مختلفة، على سبيل المثال، تحديد القمم بالترتيب المتزايد) والوزن (للرسوم البيانية المرجحة فقط).
يمكنك إلقاء نظرة على قوائم المصفوفات المذكورة أعلاه بمزيد من التفاصيل (ومع الرسوم التوضيحية)، على سبيل المثال، .
2.3 مصفوفة الجوار. ليس الهيكل الأكثر شيوعا. في جوهره، هو شكل من أشكال "تعبئة" القوائم المتجاورة في بنية تعداد واحدة (مصفوفة، متجهة). تحتوي عناصر n الأولى (وفقًا لعدد رؤوس الرسم البياني) لمثل هذه المصفوفة على مؤشرات البداية لنفس المصفوفة، بدءًا من كتابة جميع القمم المجاورة للواحد المحدد على التوالي.
لقد وجدت هنا التفسير الأكثر مفهومة (لنفسي):
3. ناقل الجوار ومصفوفة الجوار الترابطي
اتضح أن مؤلف هذه السطور، وليس كونه مبرمجًا محترفًا، ولكنه كان يتعامل بشكل دوري مع الرسوم البيانية، غالبًا ما كان يتعامل مع قوائم الحواف. في الواقع، يكون الأمر مناسبًا إذا كان الرسم البياني يحتوي على حلقات وحواف متعددة. وهكذا، في تطوير قوائم الحواف الكلاسيكية، أقترح الانتباه إلى "تطويرها/فرعها/تعديلها/طفرةها"، أي: ناقل الجوار ومصفوفة الجوار الترابطي.
3.1 متجه الجوار
الحالة (أ1): رسم بياني غير مرجح
سوف نطلق على متجه الجوار للرسم البياني غير الموزون مجموعة مرتبة من عدد زوجي من الأعداد الصحيحة (a[2i]، a[2i+1]،...، حيث i مرقمة c 0)، حيث يكون كل زوج من الأرقام هو a[2i]، a[2i+1 ] يحدد حافة الرسم البياني بين القمم a[2i] وa[2i+1]، على التوالي.
لا يحتوي تنسيق التسجيل هذا على معلومات حول ما إذا كان الرسم البياني موجهًا (كلا الخيارين ممكنان). عند استخدام تنسيق digraph، تعتبر الحافة موجهة من a[2i] إلى a[2i+1]. هنا وأدناه: بالنسبة للرسوم البيانية غير الموجهة، إذا لزم الأمر، يمكن تطبيق متطلبات ترتيب تسجيل القمم (على سبيل المثال، أن تأتي القمة ذات القيمة الأقل للرقم المخصص لها أولاً).
في لغة C++، يُنصح بتحديد متجه مجاور باستخدام std::vector، ومن هنا جاء اسم بنية البيانات هذه.
الحالة (أ2): رسم بياني غير مرجح، وأوزان الحواف عدد صحيح
قياسًا على الحالة (a1)، نطلق على متجه الجوار للرسم البياني الموزون مع أوزان حافة صحيحة مجموعة مرتبة (صفيف ديناميكي) من الأرقام (a[3i]، a[3i+1]، a[3i+2]، ...، حيث يتم ترقيم i c 0)، حيث يحدد كل "ثلاثي" من الأرقام a[3i]، a[3i+1]، a[3i+2] حافة الرسم البياني بين القمم المرقمة a[3i] وa[3i+1] على التوالي، والقيمة a [3i+2] هي وزن هذه الحافة. يمكن أيضًا توجيه مثل هذا الرسم البياني أم لا.
الحالة (ب): رسم بياني غير مرجح، وأوزان حافة غير صحيحة
نظرًا لأنه من المستحيل تخزين العناصر غير المتجانسة في مصفوفة واحدة (متجه)، على سبيل المثال، فمن الممكن التنفيذ التالي. يتم تخزين الرسم البياني في زوج من المتجهات، حيث يكون المتجه الأول هو متجه الجوار للرسم البياني دون تحديد الأوزان، ويحتوي المتجه الثاني على الأوزان المقابلة (التنفيذ المحتمل لـ C++: std::pair ). وبالتالي، بالنسبة لحافة محددة بزوج من القمم تحت الفهارس 2i، 2i+1 للمتجه الأول، سيكون الوزن مساويًا للعنصر الموجود تحت الفهرس i للمتجه الثاني.
حسنا، لماذا هذا ضروري؟
حسنًا، وجد مؤلف هذه السطور أنها مفيدة جدًا لحل عدد من المشكلات. حسنًا، من وجهة نظر رسمية، ستكون هناك المزايا التالية:
- إن متجه الجوار، مثل أي بنية "تعدادية" أخرى، مضغوط تمامًا، ويستهلك ذاكرة أقل من مصفوفة الجوار (للرسوم البيانية المتفرقة)، وسهل التنفيذ نسبيًا.
- يمكن أيضًا تمييز رؤوس الرسم البياني، من حيث المبدأ، بأرقام سالبة. ماذا لو كانت هناك حاجة لمثل هذا "الانحراف"؟
- يمكن أن تحتوي الرسوم البيانية على حواف متعددة وحلقات متعددة، بأوزان مختلفة (موجبة، سالبة، حتى صفر). لا توجد قيود هنا.
- يمكنك أيضًا تعيين خصائص مختلفة للحواف - ولكن لمعرفة المزيد حول ذلك، راجع القسم 4.
ومع ذلك، يجب الاعتراف بأن هذه "القائمة" لا تعني الوصول السريع إلى الحافة. وهنا يأتي مصفوفة المجاورة الترابطية للإنقاذ، والتي سيتم مناقشتها أدناه.
3.2 مصفوفة الجوار الترابطي
لذا، إذا كان الوصول إلى حافة معينة ووزنها وخصائصها الأخرى أمرًا بالغ الأهمية بالنسبة لنا، ولا تسمح لنا متطلبات الذاكرة باستخدام مصفوفة الجوار، فلنفكر في كيفية تغيير متجه الجوار لحل هذه المشكلة. لذلك، المفتاح هو حافة الرسم البياني، والتي يمكن تحديدها كزوج مرتب من الأعداد الصحيحة. ماذا يعني هذا تبدو؟ أليس هو مفتاح في مجموعة النقابي؟ وإذا كان الأمر كذلك، فلماذا لا ننفذه؟ دعونا نحصل على مصفوفة ترابطية حيث يرتبط كل مفتاح - زوج مرتب من الأعداد الصحيحة - بقيمة - عدد صحيح أو رقم حقيقي يحدد وزن الحافة. في C++، يُنصح بتنفيذ هذه البنية بناءً على حاوية std::map (std::map أو int> أو std::map ، double>)، أو std::multimap إذا كان من المتوقع وجود حواف متعددة. حسنًا، لدينا بنية لتخزين الرسوم البيانية التي تشغل ذاكرة أقل من هياكل "المصفوفة"، ويمكنها تحديد الرسوم البيانية ذات الحلقات والحواف المتعددة، وليس لديها حتى متطلبات صارمة لعدم سلبية أرقام القمة (لا أعرف من يحتاج هذا، ولكن لا يزال).
4. هياكل البيانات ممتلئة، ولكن هناك شيء مفقود
وهذا صحيح: عند حل عدد من المسائل، قد نحتاج إلى تعيين بعض الخصائص لحواف الرسم البياني، وبالتالي تخزينها. إذا كان من الممكن تقليل هذه الميزات بشكل لا لبس فيه إلى أعداد صحيحة، فمن الممكن تخزين مثل هذه "الرسوم البيانية ذات الميزات الإضافية" باستخدام الإصدارات الموسعة من ناقل الجوار ومصفوفة الجوار الترابطية.
لذلك، دعونا نحصل على رسم بياني غير مرجح، لكل حافة من الضروري تخزينها، على سبيل المثال، ميزتين إضافيتين محددتين بواسطة الأعداد الصحيحة. في هذه الحالة، من الممكن تعريف متجه الجوار الخاص به على أنه مجموعة مرتبة ليس من "أزواج"، ولكن من "رباعيات" من الأعداد الصحيحة (a[2i]، a[2i+2]، a[1i+2]، a [2i+2]...)، حيث a[3i+2] و a[2i+2] سيحددان خصائص الحافة المقابلة. بالنسبة للرسم البياني الذي يحتوي على عدد صحيح من أوزان الحواف، يكون الترتيب مشابهًا بشكل عام (الفرق الوحيد هو أن السمات ستتبع وزن الحافة وسيتم تحديدها بواسطة العناصر a[3i+2] وa[3i+2] ، وسيتم تحديد الحافة نفسها ليس 4، ولكن 4 أرقام مرتبة). وبالنسبة للرسم البياني الذي يحتوي على أوزان حواف غير صحيحة، يمكن كتابة الميزات في مكونه غير الموزون.
عند استخدام مصفوفة مجاورة ترابطية للرسوم البيانية ذات أوزان الحواف الصحيحة، من الممكن تحديد ليس رقمًا واحدًا كقيمة، ولكن مصفوفة (متجه) من الأرقام التي تحدد، بالإضافة إلى وزن الحافة، جميع العناصر الأخرى الضرورية سمات. في الوقت نفسه، سيكون الإزعاج في حالة الأوزان غير الصحيحة هو الحاجة إلى تحديد علامة برقم الفاصلة العائمة (نعم، هذا إزعاج، ولكن إذا لم يكن هناك الكثير من هذه العلامات، وإذا لم تقم بذلك لا تقم بتعيينها بشكل مزدوج "صعب" للغاية، فقد لا يكون هناك شيء). هذا يعني أنه في C++، يمكن تعريف المصفوفات المجاورة الترابطية الموسعة على النحو التالي: std::map أو std::vector> أو std::map ، std::vector، حيث تكون القيمة الأولى في "ناقل القيمة الرئيسية" هي وزن الحافة، ومن ثم يتم تحديد التسميات الرقمية لخصائصها.
المراجع:
حول الرسوم البيانية والخوارزميات بشكل عام:
1. كورمين، توماس هـ.، ليسرسون، تشارلز آي.، ريفست، رونالد إل.، ستاين، كليفورد. الخوارزميات: البناء والتحليل، الطبعة الثانية: Trans. من الانجليزية – م: دار ويليامز للنشر، 2.
2. هراري فرانك. نظرية الرسم البياني. م: مير، 1973.
تقرير المؤلف عن نفس المجموعة المتجاورة والمتجهة من التقاربات:
3. تشيرنوخوف إس. المتجهات المجاورة ومصفوفة الجوار الترابطية كطرق لتمثيل الرسوم البيانية وتخزينها / SA Chernouhov. ناقلات المجاورة وخريطة المجاورة كهياكل بيانات لتمثيل الرسم البياني // مجموعة مقالات المؤتمر العلمي والعملي الدولي "مشكلات تنفيذ نتائج التطورات المبتكرة وطرق حلها" (ساراتوف، 14.09.2019 سبتمبر 2019). – سترليتاماك: AMI، 65، ص. 69-XNUMX
مصادر مفيدة على الانترنت حول هذا الموضوع:
4.
5.
المصدر: www.habr.com