تنفيذ قائمة الإصابة بالرسوم البيانية

Question

أنا أفكر في تطبيقات هيكل بيانات الرسم البياني وأبحث في تمثيل "قائمة الإصابة". هناك وصف موجز لها هنا:

قائمة الإصابة

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

بالنظر إلى أن الرسم البياني الخاص بي هو رسم بياني موجه ، لست واضحًا جدًا من هذا الوصف في بضع نقاط:

1. هل يخزن الرسم البياني نفسه أيضًا قائمة بجميع الحواف؟
2. هل تخزين القمم فقط الحواف الصادرة ، أو الواردة والصادرة؟
3. إذا كلاهما ، هل هم في قوائم منفصلة؟

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

إن أي مؤشرات محل تقدير كبير.

Answer 1

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

أرماند

Answer 2

أعلم أنني ربما أطرح سؤالًا قديمًا من الأموات ، لكنني شعرت أنه من المناسب التعليق.

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

النظر في LinkedList<Vertex> كائن و LinkedList<Edge> هدف. هذا من شأنه أن يتيح لك التكرار على جميع الحواف وجميع القمم ، ولكن لا يحتوي على معلومات حول كيفية اتصال كل شيء.

قل أننا نضيف ، ثم ، عدة LinkedList<Connection> أشياء. في الواقع ، واحد لكل منهما Vertex. أ Connection هو ببساطة حيث Edge و Vertex يجتمع. وهكذا Edge سيكون اثنين Connection الكائنات (للحصول على رسم بياني غير موجه) ، و Vertex سوف يكون لها واحد LinkedList<Connection> كائن ، يمثل الاتصالات مع كل Edge هذا متصل به. هذه ، في جوهرها ، قائمة حالات.

يمكنك تعديل هذا لتمثيل Digraph إذا قمت بحذف بعض هؤلاء Connection أشياء. وبشكل أكثر تحديداً ، سيتعين عليك اختيار مكان عدم الحصول على هذه المراجع. قد تختار حذف أ Connectionمن المرتبطة LinkedList<Connection> إذا كنت لا تريد أن تكون قادرًا على رؤية Edge من Vertex (على سبيل المثال أعلاه ، سيكون N2 فارغًا LinkedList<Connection>). يمكنك بدلاً من ذلك اختيار جعل المراجع اختيارية على Edge(على سبيل المثال أعلاه ، سيكون لدى E1 واحد Connection مشيرا إلى N2 وواحد Connection NULL ، مما يسمح بالتجاوز من E1 إلى N2 ، ولكن ليس العودة إلى N1. إن اختيارك لكيفية تنفيذ هذا سيكون متروكًا لك تمامًا. أحدهما أكثر سهولة - يتم توجيه الحواف ، لذا فإن إزالة الاتصالات على الحواف لإملاء الطريقة التي تبدو منطقية. قد يبدو الآخر أكثر تعقيدًا في البداية ، لكنه سيتوقف عن التنقل دون داع على الحواف التي لا تؤدي إلى أي مكان عند إجراء عمليات البحث الأولى والعمق الأولى.

في شكل النقطة:

1. في تطبيقاتي لقائمة الإصابة ، لدي. هل تحتاج إلى تنفيذك؟

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

3. إذا قمت بذلك ، فربما تحتاج إلى طريقة لتمييز ما إذا كان واردًا أو صادرًا. ما إذا كان هذا من خلال وجود اثنين LinkedList<Connection> الكائنات على قمة الرأس ، أو عن طريق وجود ملف boolean pointingToVertex بدائية على Connection, ، أو أيا كان. ربما الخاص بك Edge سيتم توجيهها ، وسيتم تصنيع حواف غير موجهة اثنين الحواف تشير إلى طرق معاكسة. الاعتبارات التي يتعين اتخاذها اعتمادا على احتياجات الهيكل الخاص بك.

Answer 3

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

HashMap<VertexT, HashSet<EdgeT>> incidenceMap;

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

تعديل:

لقد قمت بتحديث محادثات على ويكيبيديا لموضوع "قائمة الإصابة".