هيكل التخزين
لتخزين الرسم البياني ، نعلم أن الرسم البياني يحتوي على العقد والحواف. للحصول على رسم بياني مدعوم ، كل حافة لها أيضًا قيمة للوزن. هناك نوعان رئيسيان من هياكل تخزين الرسوم البيانية شائعة الاستخدام:
المصفوفة المجاورة الجدول المجاور
المصفوفة المجاورة
نحن نعلم أنه لتمثيل العقد ، يمكننا تمثيلها مع صفيف أحادي البعد. ومع ذلك ، بالنسبة للعلاقة بين العقد ، لا يمكننا ببساطة تمثيلها بمجموعة أحادية البعد. يمكننا تمثيلهم مع صفيف ثنائي الأبعاد ، أي طريقة تمثيل تشكيل المصفوفة.
نحن نفترض أن A هي هذه الصفيف ثنائي الأبعاد ، ثم العنصر AIJ في A لا يعكس فقط العلاقة بين العقدة VI و Node VJ ، ولكن أيضًا يمكن أن تمثل قيمة AIJ حجم الوزن.
فيما يلي مثال على تمثيل مصفوفة مجاورة لرسم بياني غير موجه:
من الشكل أعلاه ، يمكننا أن نرى أن المصفوفة المجاورة للرسم البياني غير الموجه عبارة عن مصفوفة متماثلة ، ويجب أن تكون مصفوفة متماثلة. والقيمة الموجودة على قطري من الزاوية اليسرى العليا إلى الزاوية اليمنى السفلى هي صفر (تشير القطري إلى نفس العقدة)
ما هي مصفوفة مجاورة للرسم البياني الموجه؟
بالنسبة للرسوم البيانية المرجحة ، يمكن استخدام قيمة AIJ لتمثيل حجم الوزن. الرسوم البيانية أعلاه هما الرسوم البيانية بدون أوزان ، وبالتالي فإن قيمهما كلاهما 1.
الجدول المجاور
نحن نعلم أن طريقة تخزين مصفوفة المجاورة للرسم البياني تستخدم مصفوفة n*n. عندما تكون هذه المصفوفة عبارة عن مصفوفة كثيفة (على سبيل المثال ، عندما يكون الرسم البياني عبارة عن رسم بياني كامل) ، فحينئذٍ يتم اختيار طريقة تخزين مصفوفة المجاورة.
ولكن إذا كانت هذه المصفوفة عبارة عن مصفوفة متناثرة ، فإن بنية تخزين الجدول المجاورة هي بنية تخزين أكثر توفير مساحة.
بالنسبة للرسم البياني غير الموجود أعلاه ، يمكننا استخدام جدول مجاور لتمثيله على النحو التالي:
العقدة المتصلة بكل عقدة هي العقدة المجاورة لها.
مقارنة بين مصفوفة المجاورة وجدول المجاور
عندما يكون عدد العقد في الرسم البياني صغيرًا وهناك العديد من الأطراف ، تكون كفاءة استخدام مصفوفة مجاورة أعلى.
عندما يكون عدد العقد كبيرًا جدًا ويكون عدد الحواف أصغر بكثير من عدد حواف الرسم البياني الكامل لنفس العقدة ، يكون من المفيد تبني بنية تخزين جدول مجاور.
تنفيذ Java لمصفوفة المجاورة
فئة نموذج المصفوفة المجاورة
اسم الفصل لفئة نموذج مصفوفة المجاورة هو amwgraph.java. يمكنه إنشاء رسم بياني يمثله مصفوفة متاخمة من خلال هذه الفئة ، وتوفير عقد إدراج ، وإدراج الحواف ، والحصول على عقدة مجاورة الأولى والعقدة المجاورة التالية لعقدة معينة.
استيراد java.util.arraylist ؛ استيراد java.util.linkedList ؛/** * description description فئة Matrix Model المجاورة * Author Beanlam * @ttim Amwgraph (int n) {// تهيئة المصفوفة ، صفيف أحادي البعد ، وعدد الحواف الحواف = new int [n] [n] ؛ VertexList = new ArrayList (n) ؛ numofedges = 0 ؛ } // الحصول على عدد العقد العامة int getNumofVertex () {return VertexList.size () ؛ } // احصل على عدد الحواف العامة int getNumofedges () {return numofedges ؛ } // إرجاع بيانات Node I الكائنات العامة getValuebyIndex (int i) {return vertexlist.get (i) ؛ } // إرجاع وزن V1 ، V2 public int getweight (int v1 ، int v2) {return redage [v1] [v2] ؛ } // أدخل العقدة public void insertvertex (كائن Vertex) {VertexList.add (VertexList.size () ، Vertex) ؛ } // insert node public void insertEdge (int v1 ، int v2 ، int weight) {الحواف [v1] [v2] = الوزن ؛ numofedges ++ ؛ } // delete node public void deleteedge (int v1 ، int v2) {الحواف [v1] [v2] = 0 ؛ numofedges-- ؛ } // احصل على فهرس أول عقدة مجاورة عامة int getFirstNeighbor (int index) {for (int j = 0 ؛ j <vertexlist.size () ؛ j ++) {if (الحواف [index] [j]> 0) {return j ؛ }} return -1 ؛ }. }} return -1 ؛ }}اختبار فئة نموذج مصفوفة مجاورة
بعد ذلك ، قم بإعداد فئة نموذج الاختبار استنادًا إلى الرسم البياني الموجه التالي
برنامج اختبار testamwgraph.java كما يلي:
/** * description test class من فئة amwgraph * author beanlam * ttime 2015.4.17 */public class testamwgraph {public static void main (string args []) {int n = 4 ، e = 4 ؛ تحديد Amwgraph الرسم البياني = جديد Amwgraph (N) ؛ لـ (تسمية السلسلة: التسميات) {graph.insertvertex (label) ؛ // insert node} // insert four edges graph.insertedge (0 ، 1 ، 2) ؛ graph.insertedge (0 ، 2 ، 5) ؛ graph.insertedge (2 ، 3 ، 8) ؛ graph.insertedge (3 ، 0 ، 7) ؛ System.out.println ("عدد العقد هو:"+graph.getnumofvertex ()) ؛ System.out.println ("عدد الحواف هو:"+graph.getnumofedges ()) ؛ graph.deleteedge (0 ، 1) ؛ // delete <v1 ، v2> edge system.out.println ("بعد الحذف <v1 ، v2> edge ...") ؛ System.out.println ("عدد العقد هو:"+graph.getnumofvertex ()) ؛ System.out.println ("عدد الحواف هو:"+graph.getnumofedges ()) ؛ }}يتم عرض نتائج الإخراج لوحدة التحكم في الشكل أدناه:
لخص
ما سبق هو كل محتوى هذه المقالة حول وصف لغة Java لهيكل التخزين وأمثلة رمز مصفوفة المجاورة. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها.