โครงสร้างการจัดเก็บ
ในการจัดเก็บกราฟเรารู้ว่ากราฟมีทั้งโหนดและขอบ สำหรับกราฟขับเคลื่อนแต่ละขอบยังมีค่าน้ำหนัก มีสองประเภทหลักของโครงสร้างการจัดเก็บกราฟที่ใช้กันทั่วไป:
เมทริกซ์ที่อยู่ติดกัน
เมทริกซ์ที่อยู่ติดกัน
เรารู้ว่าเพื่อเป็นตัวแทนของโหนดเราสามารถเป็นตัวแทนของพวกเขาด้วยอาร์เรย์หนึ่งมิติ อย่างไรก็ตามสำหรับความสัมพันธ์ระหว่างโหนดเราไม่สามารถเป็นตัวแทนของพวกเขาด้วยอาร์เรย์หนึ่งมิติ เราสามารถเป็นตัวแทนของพวกเขาด้วยอาร์เรย์สองมิตินั่นคือวิธีการแสดงการขึ้นรูปเมทริกซ์
เราคิดว่า A คืออาร์เรย์สองมิตินี้จากนั้นองค์ประกอบ AIJ ใน A ไม่เพียง แต่สะท้อนถึงความสัมพันธ์ระหว่างโหนด VI และโหนด VJ แต่ยังรวมถึงค่าของ AIJ สามารถแสดงขนาดของน้ำหนักได้
นี่คือตัวอย่างของการแสดงเมทริกซ์ adjacency ของกราฟที่ไม่ได้บอกทิศทาง:
จากรูปด้านบนเราจะเห็นได้ว่าเมทริกซ์ adjacency ของกราฟที่ไม่ได้ทิศทางเป็นเมทริกซ์สมมาตรและต้องเป็นเมทริกซ์สมมาตร และค่าของเส้นทแยงมุมจากมุมซ้ายบนไปยังมุมล่างขวาคือศูนย์ (เส้นทแยงมุมหมายถึงโหนดเดียวกัน)
เมทริกซ์ adjacency ของกราฟกำกับคืออะไร?
สำหรับกราฟถ่วงน้ำหนักค่าของ AIJ สามารถใช้เพื่อแสดงขนาดของน้ำหนัก กราฟสองกราฟข้างต้นคือกราฟที่ไม่มีน้ำหนักดังนั้นค่าของพวกเขาคือทั้งคู่ 1
ตารางที่อยู่ติดกัน
เรารู้ว่าวิธีการจัดเก็บเมทริกซ์ adjacency ของกราฟใช้เมทริกซ์ n*n เมื่อเมทริกซ์นี้เป็นเมทริกซ์หนาแน่น (ตัวอย่างเช่นเมื่อกราฟเป็นกราฟที่สมบูรณ์) ดังนั้นแน่นอนว่าวิธีการจัดเก็บเมทริกซ์ adjacency จะถูกเลือก
แต่ถ้าเมทริกซ์นี้เป็นเมทริกซ์เบาบางโครงสร้างการจัดเก็บตารางที่อยู่ติดกันเป็นโครงสร้างการจัดเก็บพื้นที่ประหยัดพื้นที่มากขึ้น
สำหรับกราฟที่ไม่ได้กำกับข้างต้นเราสามารถใช้ตาราง adjacency เพื่อแสดงดังนี้:
โหนดที่เชื่อมต่อกับแต่ละโหนดคือโหนดที่อยู่ติดกัน
การเปรียบเทียบระหว่างเมทริกซ์ adjacency และตาราง adjacency
เมื่อจำนวนโหนดในกราฟมีขนาดเล็กและมีหลายด้านประสิทธิภาพของการใช้เมทริกซ์ adjacency จะสูงขึ้น
เมื่อจำนวนโหนดมีขนาดใหญ่มากและจำนวนขอบมีขนาดเล็กกว่าจำนวนขอบของกราฟที่สมบูรณ์ของโหนดเดียวกันมันจะมีประสิทธิภาพมากขึ้นในการใช้โครงสร้างการจัดเก็บตาราง adjacency
การใช้งาน Java ของ Matrix adjacency
คลาสรุ่นเมทริกซ์ที่อยู่ติดกัน
ชื่อคลาสของคลาสโมเดล Matrix adjacency คือ amwgraph.java มันสามารถสร้างกราฟที่แสดงโดยเมทริกซ์ adjacency ผ่านคลาสนี้และให้โหนดการแทรก, แทรกขอบและรับโหนด adjacency แรกและโหนด adjacency ถัดไปของโหนดที่แน่นอน
นำเข้า java.util.arraylist; นำเข้า java.util.linkedlist;/** * @description คลาสเมทริกซ์ที่อยู่ติดกันคลาสรุ่น * @author beanlam * @time 2015.4.17 */คลาสสาธารณะ amwgraph {ส่วนตัว ของ Edges Public AMWGRAPH (int n) {// เริ่มต้นเมทริกซ์, อาร์เรย์หนึ่งมิติและจำนวนขอบขอบ = ใหม่ int [n] [n]; VertexList = arrayList ใหม่ (n); numofedges = 0; } // รับจำนวนโหนดสาธารณะ int 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 edges [v1] [v2]; } // แทรกโมฆะสาธารณะโมฆะ insertvertex (วัตถุจุดสุดยอด) {vertexlist.add (vertexlist.size (), จุดสุดยอด); } // แทรกโมฆะสาธารณะ INSERTEDGE (int v1, int v2, น้ำหนัก int) {ขอบ [v1] [v2] = น้ำหนัก; numofedges ++; } // ลบโหนดโมฆะสาธารณะ deleteedge (int v1, int v2) {ขอบ [v1] [v2] = 0; Numofedges-; } // รับดัชนีของโหนดสาธารณะที่อยู่ติดกันครั้งแรก int int getFirstneighbor (INT ดัชนี) {สำหรับ (int j = 0; j <vertexlist.size (); j ++) {ถ้า (ขอบ [ดัชนี] [j]> 0) {return j; }} return -1; } // ดึงโหนด adjacency ถัดไปตามตัวห้อยของโหนด adjacency ก่อนหน้า public public int getNextneighbor (int v1, int v2) {สำหรับ (int j = v2+1; j <vertexlist.size (); j ++) {ถ้า (ขอบ [v1] [j]> 0) }} return -1; -การทดสอบคลาสโมเดลเมทริกซ์ adjacency
ถัดไปตั้งค่าคลาสโมเดลทดสอบตามกราฟที่กำกับต่อไปนี้
โปรแกรมทดสอบ testamwgraph.java มีดังนี้:
/** * @description คลาสทดสอบของคลาส AMWGRAPH * @author beanlam * @time 2015.4.17 */คลาสสาธารณะ testamwgraph {โมฆะคงที่สาธารณะหลัก (สตริง args []) {int n = 4, e = 4; // แสดงจำนวนโหนดและจำนวนของขอบตามลำดับตามลำดับ ป้ายกำกับ [] = {"v1", "v1", "v3", "v4"}; // การระบุโหนด amwgraph กราฟ = ใหม่ amwgraph (n); สำหรับ (ป้ายกำกับสตริง: ป้ายกำกับ) {graph.insertvertex (ป้ายกำกับ); // แทรกโหนด} // แทรกสี่ขอบกราฟกราฟ. ininsertedge (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); // ลบ <v1, v2> edge system.out.println ("หลังจากลบ <v1, v2> ขอบ ... "); System.out.println ("จำนวนโหนดคือ:"+graph.getNumofvertex ()); System.out.println ("จำนวนขอบคือ:"+graph.getNumofedges ()); -ผลลัพธ์ผลลัพธ์ของคอนโซลจะแสดงในรูปด้านล่าง:
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับคำอธิบายภาษา Java ของโครงสร้างการจัดเก็บและตัวอย่างรหัสเมทริกซ์ adjacency ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น