نحن نعلم أنه لتمثيل العقد ، يمكننا تمثيلها مع صفيف أحادي البعد. ومع ذلك ، بالنسبة للعلاقة بين العقد ، لا يمكننا ببساطة تمثيلها بمجموعة أحادية البعد. يمكننا تمثيلهم مع صفيف ثنائي الأبعاد ، أي طريقة تمثيل تشكيل المصفوفة.
نحن نفترض أن A هي هذه الصفيف ثنائي الأبعاد ، ثم العنصر AIJ في A لا يعكس فقط العلاقة بين العقدة VI و Node VJ ، ولكن أيضًا يمكن أن تمثل قيمة AIJ حجم الوزن.
فئة نموذج المصفوفة المجاورة
اسم الفصل لفئة نموذج مصفوفة المجاورة هو amwgraph.java. يمكنه إنشاء رسم بياني يمثله مصفوفة متاخمة من خلال هذه الفئة ، وتوفير عقد إدراج ، وإدراج الحواف ، والحصول على عقدة مجاورة الأولى والعقدة المجاورة التالية لعقدة معينة.
استيراد java.util.arraylist ؛
استيراد java.util.linkedList ؛
الطبقة العامة amwgraph {
arraylist private vertexlist ؛
// جدول ارتباط نقاط التخزين
private int [] [] الحواف ؛
// مصفوفة العنوان ، تستخدم لتخزين الحواف
private int numofedges ؛
// عدد الحواف
Amwgraph العامة (int n) {
// تهيئة المصفوفة ، صفيف أحادي البعد ، وعدد الحواف
الحواف = new int [n] [n] ؛
VertexList = new ArrayList (n) ؛
numofedges = 0 ؛
}
// احصل على عدد العقد
العام int getNumofvertex () {
إرجاع VertexList.size () ؛
}
// احصل على عدد الحواف
الجمهور int getNumofedges () {
إرجاع numofedges.
}
// إرجاع بيانات العقدة i
كائن عام getValueByIndex (int i) {
إرجاع vertexlist.get (i) ؛
}
// إرجاع وزن V1 و V2
Public Int Getweight (int v1 ، int v2) {
عودة حواف [v1] [v2] ؛
}
// إدراج العقدة
void public insertvertex (كائن قمة) {
VertexList.add (VertexList.size () ، Vertex) ؛
}
// إدراج العقدة
insertedge public void (int v1 ، int v2 ، int) {
الحواف [v1] [v2] = الوزن ؛
numofedges ++ ؛
}
// حذف العقدة
public void deleteedge (int v1 ، int v2) {
الحواف [v1] [v2] = 0 ؛
numofedges-- ؛
}
// احصل على مجموعة العقدة المجاورة الأولى
العام int getFirstNeighbor (int index) {
لـ (int j = 0 ؛ j <vertexlist.size () ؛ j ++) {
if (الحواف [index] [j]> 0) {
العودة ي.
}
}
العودة -1 ؛
}
// احصل على العقدة المجاورة التالية بناءً على مجموعة العقدة المجاورة السابقة
public int getNextNeighbor (int v1 ، int v2) {
لـ (int j = v2+1 ؛ j <vertexlist.size () ؛ j ++) {
if (الحواف [v1] [j]> 0) {
العودة ي.
}
}
العودة -1 ؛
}
}دعونا نلقي نظرة على الكود الذي ينفذ مصفوفة مجاورة لتمثيل الرسوم البيانية الكثيفة:
حزمة com.datubitructure.graph ؛
///// الرسم البياني الكثيف - استخدم مصفوفة مجاورة لتمثيل
// الطبقة العامة Densegraph {
//
// private int n ؛ // عدد العقد
// private int m ؛ // رقم الحافة
// الموجه المنطقي الخاص ؛ // هل هو رسم بياني موجه
// boolean private [] [] g ؛ // بيانات محددة للصورة
//
// // المنشئ
// Public Densegraph (int n ، Boolean Direction) {
// تأكيد n> = 0 ؛
// this.n = n ؛
// this.m = 0 ؛ // التهيئة ليس لها حواف
// this.direged = موجه ؛
تتم تهيئة // g إلى مصفوفة منطقية من n*n. كل g [i] [j] خطأ ، مما يشير إلى أنه لا يوجد أي وحواف.
// // false هي القيمة الافتراضية لمتغير النوع المنطقي
// g = new Boolean [n] [n] ؛
//}
//
// public int v () {
// return n ؛
//} // إرجاع عدد العقد
//
// public int e () {
// العودة م ؛
//} // إرجاع عدد الحواف
//
// // أضف حافة إلى الرسم البياني
// public void adderge (int v ، int w) {
//
// assert v> = 0 && v <n ؛
// تأكيد w> = 0 && w <n ؛
//
// if (hasedge (v ، w))
// يعود؛
//
// // connect v و w
// g [v] [w] = true ؛
// إذا (! موجهة)
// g [w] [v] = true ؛
//
// // عدد الحواف ++
// M ++ ؛
//}
//
// // تحقق مما إذا كانت هناك حواف من V إلى W في الرسم البياني
// boolean hasedge (int v ، int w) {
// assert v> = 0 && v <n ؛
// تأكيد w> = 0 && w <n ؛
// return g [v] [w] ؛
//}
//
// // إرجاع جميع جيران قمة الرأس في الرسم البياني
// // بما أن Java تستخدم آلية مرجعية ، فإن إرجاع المتجه لن يجلب أي عام إضافي.
// public itervable <Integer> adj (int v) {
// assert v> = 0 && v <n ؛
// ناقل <integer> adjv = new vector <integer> () ؛
// لـ (int i = 0 ؛ i <n ؛ i ++)
// if (g [v] [i])
// adjv.add (i) ؛
// return adjv ؛
//}
//}
استيراد java.util.arraylist ؛
استيراد java.util.list ؛
// استخدم مصفوفة مجاورة لتمثيل الرسوم البيانية الكثيفة
الطبقة العامة الكثافة {
الخاص int n ؛
// عدد العقد في الشكل
الخاص int m ؛
// عدد الحواف في الصورة
منطقية خاصة [] [] G ؛
// المصفوفة المجاورة
وجهات منطقية خاصة.
// هل هو رسم بياني موجه
Public Densegraph (int n ، Boolean Direction) {
this.n = n ؛
// عدد العقد في الرسم البياني للتهيئة
this.m = 0 ؛
// تتم تهيئة عدد الحواف في الشكل إلى 0
هذا.
G = New Boolean [n] [n] ؛
// تتم تهيئة مصفوفة متاخمة G إلى مصفوفة ثنائية الأبعاد من n*n
// يمثل الفهرس العقدة في الرسم البياني ، والقيمة المخزنة في G هي ما إذا كانت العقدة تحتوي على حواف
}
// إرجاع عدد الحواف في الرسم البياني
العام int e () {
العودة م ؛
}
// إرجاع عدد العقد في الرسم البياني
العام int v () {
العودة ن ؛
}
// أضف حواف بين العقدتين المحددتين في الشكل
Void public adderge (int v ، int w) {
if (! hasedge (v ، w)) {
// connect [v] [w]
g [v] [w] = true ؛
// رسم بياني غير موجه
إذا (! موجهة)
g [w] [v] = true ؛
// عدد الجوانب في الصورة +1
M ++ ؛
}
}
// تحديد ما إذا كانت هناك حواف بين العقدتين
عازف منطقي خاص (int v ، int w) {
العودة g [v] [w] ؛
}
// إرجاع العقد المجاورة لجميع العقد v
public itelfable <integer> المجاور (int v) {
// يستخدم المجاور لتخزين العقدة المجاورة لـ V.
قائمة <integer> المجاورة = new ArrayList <> () ؛
// ابحث عن جميع العقد المجاورة لـ V وإضافتها إلى المجاور
لـ (int i = 0 ؛ i <n ؛ i ++) {
إذا (g [v] [i])
المجاور.
}
العودة المجاورة ؛
}
}
لخص
ما ورد أعلاه هو كل محتوى هذه المقالة حول برمجة Java لتنفيذ مثال الكود لتمثيل الرسم البياني الكثيف لمصفوفة المجاورة ، وآمل أن يكون مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى هذا الموقع:
تحليل المفاهيم الأساسية وأمثلة رمز لشجرة بنية بيانات جافا
أسئلة مقابلة بنية البيانات الشائعة في Java (مع إجابات)
مبدأ خوارزمية مطابقة السلسلة متعددة الأرقام ورمز تنفيذ Java
إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!