Kami tahu bahwa untuk mewakili node, kami dapat mewakili mereka dengan array satu dimensi. Namun, untuk hubungan antara node, kita tidak bisa begitu saja mewakili mereka dengan array satu dimensi. Kita dapat mewakili mereka dengan array dua dimensi, yaitu, metode representasi pembentuk matriks.
Kami berasumsi bahwa A adalah array dua dimensi ini, kemudian elemen AIJ dalam A tidak hanya mencerminkan hubungan antara simpul VI dan Node VJ, tetapi juga nilai AIJ dapat mewakili ukuran berat.
Kelas model matriks yang berdekatan
Nama kelas dari kelas model matriks adjacency adalah amwgraph.java. Ini dapat membangun grafik yang diwakili oleh matriks adjacency melalui kelas ini, dan memberikan node penyisipan, memasukkan tepi, dan mendapatkan simpul adjaksensi pertama dan simpul adjacency berikutnya dari node tertentu.
impor java.util.arraylist;
impor java.util.linkedlist;
kelas publik amwgraph {
Vertexlist Private ArrayList;
// Tabel tautan titik penyimpanan
private int [] [] tepi;
// Alamat matriks, digunakan untuk menyimpan tepi
numfedges int pribadi;
// Jumlah tepi
Amwgraph publik (int n) {
// Inisialisasi matriks, array satu dimensi, dan jumlah tepi
edges = int new [n] [n];
vertexList = new arraylist (n);
numofedges = 0;
}
// Dapatkan jumlah node
public int getNumOfVerTex () {
return vertexlist.size ();
}
// Dapatkan jumlah tepi
publik int getNumofedges () {
pengembalian numofedges;
}
// Kembalikan data node i
Objek publik getValueByIndex (int i) {
return vertexlist.get (i);
}
// Kembalikan berat V1 dan V2
public int getweight (int v1, int v2) {
tepi pengembalian [v1] [v2];
}
// Masukkan simpul
public void insertVertex (objek vertex) {
vertexlist.add (vertexlist.size (), vertex);
}
// Masukkan simpul
public void insertEdge (int v1, int v2, int bobot) {
tepi [v1] [v2] = berat;
numofedges ++;
}
// Hapus simpul
public void deleteedge (int v1, int v2) {
tepi [v1] [v2] = 0;
numofedges--;
}
// Dapatkan subskrip dari simpul yang berdekatan pertama
Public int getFirstneighbor (int index) {
untuk (int j = 0; j <vertexList.size (); j ++) {
if (edges [index] [j]> 0) {
mengembalikan j;
}
}
kembali -1;
}
// Dapatkan simpul adjacency berikutnya berdasarkan subskrip dari node adjacency sebelumnya
Public int getNextneighbor (int v1, int v2) {
untuk (int j = v2+1; j <vertexlist.size (); j ++) {
if (tepi [v1] [j]> 0) {
mengembalikan j;
}
}
kembali -1;
}
}Mari kita lihat kode yang mengimplementasikan matriks kedekatan untuk mewakili grafik padat:
paket com.dataStructure.graph;
///// grafik padat - Gunakan matriks adjacency untuk mewakili
// kelas publik Densegraph {
//
// int n; // Jumlah node
// int m; // Nomor tepi
// Private Boolean diarahkan; // Apakah itu grafik yang diarahkan
// boolean pribadi [] [] g; // Data spesifik gambar
//
// // Konstruktor
// Public Densegraph (int n, boolean diarahkan) {
// menegaskan n> = 0;
// this.n = n;
// this.m = 0; // Inisialisasi tidak memiliki tepi
// this.directed = diarahkan;
// // G diinisialisasi ke matriks boolean n*n. Setiap g [i] [j] salah, menunjukkan bahwa tidak ada dan tepi.
// // false adalah nilai default variabel tipe boolean
// g = boolean baru [n] [n];
//}
//
// public int v () {
// return n;
//} // kembalikan jumlah node
//
// public int e () {
// return m;
//} // mengembalikan jumlah tepi
//
// // tambahkan tepi ke grafik
// public void ditambahkan (int v, int w) {
//
// Assert v> = 0 && v <n;
// tegaskan w> = 0 && w <n;
//
// if (hastre (v, w))
// kembali;
//
// // hubungkan v dan w
// g [v] [w] = true;
// if (! Diarahkan)
// g [w] [v] = true;
//
// // Jumlah tepi ++
// m ++;
//}
//
// // Verifikasi apakah ada tepi dari v ke w dalam grafik
// boolean hastre (int v, int w) {
// Assert v> = 0 && v <n;
// tegaskan w> = 0 && w <n;
// return g [v] [w];
//}
//
// // mengembalikan semua tetangga dari titik di grafik
// // Karena Java menggunakan mekanisme referensi, mengembalikan vektor tidak akan membawa overhead tambahan.
// publik iterable <Integer> adj (int v) {
// Assert v> = 0 && v <n;
// vektor <Integer> adjv = vektor baru <integer> ();
// untuk (int i = 0; i <n; i ++)
// if (g [v] [i])
// adjv.add (i);
// kembalikan adjv;
//}
//}
impor java.util.arraylist;
impor java.util.list;
// Gunakan matriks adjacency untuk mewakili grafik padat
Densegraph kelas publik {
int n;
// Jumlah node dalam gambar
int m;
// Jumlah tepi dalam gambar
boolean pribadi [] [] g;
// matriks yang berdekatan
diarahkan boolean pribadi;
// Apakah itu grafik yang diarahkan
Public Densegraph (int n, boolean diarahkan) {
this.n = n;
// Jumlah node dalam grafik inisialisasi
this.m = 0;
// Jumlah tepi dalam gambar diinisialisasi ke 0
this.directed = diarahkan;
g = boolean baru [n] [n];
// Matriks adjaksensi G diinisialisasi ke dalam matriks dua dimensi n*n
// Indeks mewakili simpul dalam grafik, dan nilai yang disimpan dalam G adalah apakah simpul memiliki tepi
}
// Kembalikan jumlah tepi dalam grafik
int e () {
kembali m;
}
// Kembalikan jumlah node dalam grafik
Public int v () {
kembali n;
}
// Tambahkan tepi antara dua node yang ditentukan dalam gambar
public void ditambahkan (int v, int w) {
if (! hastre (v, w)) {
// hubungkan [v] [w]
g [v] [w] = true;
// grafik yang tidak diarahkan
if (! diarahkan)
g [w] [v] = true;
// Jumlah sisi dalam gambar +1
M ++;
}
}
// Tentukan apakah ada tepi antara kedua node
private boolean hastre (int v, int w) {
return g [v] [w];
}
// Mengembalikan node kedekatan dari semua node v
Publik iterable <Integer> adjacentNode (int v) {
// adjacentl digunakan untuk menyimpan simpul V yang berdekatan
Daftar <Integer> adjacentl = ArrayList baru <> ();
// Temukan semua node yang berdekatan dengan V dan tambahkan mereka di sebelahnya
untuk (int i = 0; i <n; i ++) {
if (g [v] [i])
adjacentl.add (i);
}
kembali berdekatan;
}
}
Meringkaskan
Di atas adalah semua konten dari artikel ini tentang pemrograman Java untuk mengimplementasikan contoh kode representasi grafik padat dari matriks adjacency, dan saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke situs ini:
Analisis Konsep Dasar dan Contoh Kode Pohon Struktur Data Java
Java Common Data Struktur Wawancara Pertanyaan (dengan jawaban)
Prinsip Algoritma Pencocokan String Multimode dan Kode Implementasi Java
Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!