إنشاء مصفوفة مجاورة من رسم بياني Jung

Question

Graph < Integer, Integer> g = new SparseMultigraph<Integer, Integer>();
    g.addVertex(1);g.addVertex(2);g.addVertex(3);
    g.addEdge(0,1,2 ,EdgeType.DIRECTED);g.addEdge(1,2,3 ,EdgeType.DIRECTED);g.addEdge(2,3,1 ,EdgeType.DIRECTED);g.addEdge(3,1,3 ,EdgeType.DIRECTED);

كيف يمكنني تحويل هذا الرسم البياني إلى مصفوفة مجاورة مع الأخذ في الاعتبار أنه رسم بياني موجه.

Answer 1

في هذا المنشور ، يمكنك العثور على مصفوفة متاخمة:

اتساع وعمق أول بحث - الجزء 3

كيف تنفذها؟

// Adjacency matrix
int map[21][21] = {

/*   A B C D E F G H I L M N O P R S T U V Z */
  {0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1}, // Arad
  {2,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0}, // Bucharest
  {3,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0}, // Craiova
  {4,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, // Dobreta
  {5,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, // Eforie
  {6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0}, // Fagaras
  {7,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, // Girgiu
  {8,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0}, // Hirsova
  {9,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0}, // Iasi
  {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0}, // Lugoj
  {1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, // Mehadia
  {2,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, // Neamt
  {3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1}, // Oradea
  {4,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}, // Pitesti
  {5,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0}, // Rimnicu Vilcea
  {6,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0}, // Sibiu
  {7,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, // Timisoara
  {8,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0}, // Urziceni
  {9,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0}, // Vaslui
  {0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0}  // Zerind
};

لاحظ أن الخط الأول الذي تم تعليقه يمثل الحرف الأولي لاسم كل مدينة. يشير التعيين الذي يتم مع مصفوفة المجاورة إلى هذه الرسائل بحيث يكون من الأسهل فهمها. على سبيل المثال ، الحصول على الإدخال الأول لمصفوفة المجاورة التي تشير إلى Arad: لدينا أن Arad لديه مسارات تقودنا إلى Sibiu و Timisoara و Zerind ، وبالتالي نضع قيمة 1 على الأعمدة التي تمثل تلك المدن ، في هذه الحالة ، الأعمدة الموجودة أسفل الحروف S و T و Z. هكذا يتم التعيين. وضعنا قيمة 0 على الأعمدة الأخرى لنذكر أنه لا يوجد مسار يقودنا إلى تلك المدن.

بالنظر إلى الرسم البياني الخاص بك ، قم بتكرار حوافه وإنشاء مصفوفة مجاورة.