เรารู้ว่าเพื่อเป็นตัวแทนของโหนดเราสามารถเป็นตัวแทนของพวกเขาด้วยอาร์เรย์หนึ่งมิติ อย่างไรก็ตามสำหรับความสัมพันธ์ระหว่างโหนดเราไม่สามารถเป็นตัวแทนของพวกเขาด้วยอาร์เรย์หนึ่งมิติ เราสามารถเป็นตัวแทนของพวกเขาด้วยอาร์เรย์สองมิตินั่นคือวิธีการแสดงการขึ้นรูปเมทริกซ์
เราคิดว่า A คืออาร์เรย์สองมิตินี้จากนั้นองค์ประกอบ AIJ ใน A ไม่เพียง แต่สะท้อนถึงความสัมพันธ์ระหว่างโหนด VI และโหนด VJ แต่ยังรวมถึงค่าของ AIJ สามารถแสดงขนาดของน้ำหนักได้
คลาสรุ่นเมทริกซ์ที่อยู่ติดกัน
ชื่อคลาสของคลาสโมเดล Matrix adjacency คือ amwgraph.java มันสามารถสร้างกราฟที่แสดงโดยเมทริกซ์ adjacency ผ่านคลาสนี้และให้โหนดการแทรก, แทรกขอบและรับโหนด adjacency แรกและโหนด adjacency ถัดไปของโหนดที่แน่นอน
นำเข้า java.util.arraylist;
นำเข้า java.util.linkedList;
ชั้นเรียนสาธารณะ amwgraph {
arraylist ส่วนตัว vertexlist;
// ตารางลิงค์ของจุดจัดเก็บข้อมูล
private int [] [] ขอบ;
// ที่อยู่เมทริกซ์ใช้เพื่อจัดเก็บขอบ
INT NUMOFEDGES ส่วนตัว;
// จำนวนขอบ
สาธารณะ amwgraph (int n) {
// เริ่มต้นเมทริกซ์อาร์เรย์หนึ่งมิติและจำนวนขอบ
Edges = new int [n] [n];
VertexList = arrayList ใหม่ (n);
numofedges = 0;
-
// รับจำนวนโหนด
สาธารณะ int getNumofvertex () {
return vertexlist.size ();
-
// รับจำนวนขอบ
สาธารณะ int getNumofedges () {
กลับ numofedges;
-
// ส่งคืนข้อมูลของโหนด i
วัตถุสาธารณะ getValueByIndex (int i) {
return vertexlist.get (i);
-
// ส่งคืนน้ำหนักของ V1 และ V2
สาธารณะ int getweight (int v1, int v2) {
ส่งคืนขอบ [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 getFirstneighbor (ดัชนี int) {
สำหรับ (int j = 0; j <vertexlist.size (); j ++) {
if (edges [index] [j]> 0) {
กลับ j;
-
-
กลับ -1;
-
// รับโหนด adjacency ถัดไปตามตัวห้อยของโหนด adjacency ก่อนหน้า
สาธารณะ int getNextneighbor (int v1, int v2) {
สำหรับ (int j = v2+1; j <vertexlist.size (); j ++) {
ถ้า (ขอบ [v1] [j]> 0) {
กลับ j;
-
-
กลับ -1;
-
-มาดูรหัสที่ใช้เมทริกซ์ adjacency เพื่อแสดงกราฟหนาแน่น:
แพ็คเกจ com.datastructure.graph;
////// dense กราฟ - ใช้ matrix adjacency เพื่อเป็นตัวแทน
// ชั้นเรียนสาธารณะ Densegraph {
-
// ส่วนตัว int n; // จำนวนโหนด
// ส่วนตัว int m; // หมายเลขขอบ
// บูลีนส่วนตัวกำกับ; // มันเป็นกราฟกำกับหรือไม่
// บูลีนส่วนตัว [] [] G; // ข้อมูลเฉพาะของรูปภาพ
-
// // ตัวสร้าง
// Densegraph สาธารณะ (int n, บูลีนกำกับ) {
// ยืนยัน n> = 0;
// this.n = n;
// this.m = 0; // การเริ่มต้นไม่มีขอบ
// this.directed = กำกับ;
// // g เริ่มต้นเป็นเมทริกซ์บูลีนของ n*n แต่ละ g [i] [j] เป็นเท็จแสดงว่าไม่มีและขอบ
// // false เป็นค่าเริ่มต้นของตัวแปรประเภทบูลีน
// g = บูลีนใหม่ [n] [n];
-
-
// public int v () {
// return n;
//} // ส่งคืนจำนวนโหนด
-
// public int e () {
// return m;
//} // ส่งคืนจำนวนขอบ
-
// // เพิ่มขอบลงในกราฟ
// โมฆะสาธารณะเพิ่ม (int v, int w) {
-
// ยืนยัน v> = 0 && v <n;
// ยืนยัน w> = 0 && w <n;
-
// ถ้า (hasedge (v, w))
// กลับ;
-
// // เชื่อมต่อ V และ W
// g [v] [w] = true;
// ถ้า (! กำกับ)
// g [w] [v] = true;
-
// // จำนวนขอบ ++
// m ++;
-
-
// // ตรวจสอบว่ามีขอบจาก V ถึง W ในกราฟ
// บูลีน HasEdge (int v, int w) {
// ยืนยัน v> = 0 && v <n;
// ยืนยัน w> = 0 && w <n;
// return g [v] [w];
-
-
// // ส่งคืนเพื่อนบ้านทั้งหมดของจุดสุดยอดในกราฟ
// // เนื่องจาก Java ใช้กลไกการอ้างอิงการส่งคืนเวกเตอร์จะไม่นำค่าใช้จ่ายเพิ่มเติมใด ๆ
// public iterable <integer> adj (int v) {
// ยืนยัน v> = 0 && v <n;
// Vector <Integer> adjv = เวกเตอร์ใหม่ <จำนวนจำนวนเต็ม> ();
// สำหรับ (int i = 0; i <n; i ++)
// ถ้า (g [v] [i])
// adjv.add (i);
// return adjv;
-
-
นำเข้า java.util.arraylist;
นำเข้า java.util.list;
// ใช้ matrix adjacency เพื่อแสดงกราฟหนาแน่น
Densegraph ชั้นเรียนสาธารณะ {
ส่วนตัว int n;
// จำนวนโหนดในรูป
ส่วนตัว int m;
// จำนวนขอบในภาพ
บูลีนส่วนตัว [] [] G;
// เมทริกซ์ที่อยู่ติดกัน
บูลีนส่วนตัวกำกับ;
// มันเป็นกราฟกำกับหรือไม่
Densegraph สาธารณะ (int n, บูลีนกำกับ) {
this.n = n;
// จำนวนโหนดในกราฟการเริ่มต้น
this.m = 0;
// จำนวนขอบในรูปจะเริ่มต้นเป็น 0
this.directed = กำกับ;
g = บูลีนใหม่ [n] [n];
// เมทริกซ์ adjacency g ถูกเริ่มต้นเป็นเมทริกซ์สองมิติของ n*n
// ดัชนีแสดงถึงโหนดในกราฟและค่าที่เก็บไว้ใน G คือว่าโหนดมีขอบหรือไม่
-
// ส่งคืนจำนวนขอบในกราฟ
สาธารณะ int e () {
กลับ M;
-
// ส่งคืนจำนวนโหนดในกราฟ
สาธารณะ int v () {
กลับ n;
-
// เพิ่มขอบระหว่างสองโหนดที่ระบุในรูป
เพิ่มโมฆะสาธารณะ (int v, int w) {
if (! hasedge (v, w)) {
// เชื่อมต่อ [V] [W]
g [v] [w] = true;
// กราฟที่ไม่ได้กำกับ
ถ้า (! กำกับ)
g [w] [v] = true;
// จำนวนด้านในรูปภาพ +1
M ++;
-
-
// ตรวจสอบว่ามีขอบระหว่างสองโหนด
Boolean ส่วนตัว Hasedge (int v, int w) {
กลับ g [v] [w];
-
// ส่งคืนโหนด adjacency ของโหนดทั้งหมด v
สาธารณะ iterable <teeger> ที่อยู่ติดกัน (int v) {
// ที่อยู่ติดกันใช้เพื่อจัดเก็บโหนดที่อยู่ติดกันของ V
รายการ <จำนวนเต็ม> อยู่ติดกัน = new ArrayList <> ();
// ค้นหาโหนดทั้งหมดที่อยู่ติดกับ v และเพิ่มลงในติดกับที่อยู่ติดกัน
สำหรับ (int i = 0; i <n; i ++) {
ถ้า (g [v] [i])
อยู่ติดกัน (I);
-
กลับมาอยู่ติดกัน;
-
-
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการเขียนโปรแกรม Java เพื่อใช้ตัวอย่างรหัสของการแสดงกราฟหนาแน่นของเมทริกซ์ adjacency และฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงเว็บไซต์นี้ต่อไปได้:
การวิเคราะห์แนวคิดพื้นฐานและตัวอย่างรหัสของแผนผังโครงสร้างข้อมูล Java
Java Common Data โครงสร้างคำถามสัมภาษณ์ (พร้อมคำตอบ)
หลักการอัลกอริทึมการจับคู่สตริง Multimode และรหัสการใช้งาน Java
หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!