Struktur penyimpanan
Untuk menyimpan grafik, kita tahu bahwa grafik memiliki node dan tepi. Untuk grafik bertenaga, setiap tepi juga memiliki nilai berat. Ada dua jenis utama dari struktur penyimpanan grafik yang umum digunakan:
Tabel yang berdekatan dengan matriks yang berdekatan
Matriks yang berdekatan
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.
Berikut adalah contoh representasi matriks adjacency dari grafik yang tidak diarahkan:
Dari gambar di atas kita dapat melihat bahwa matriks adjacency dari grafik yang tidak diarahkan adalah matriks simetris, dan harus menjadi matriks simetris. Dan nilai pada diagonal dari sudut kiri atas ke sudut kanan bawah adalah nol (diagonal menunjukkan simpul yang sama)
Apa matriks adjacency dari grafik terarah?
Untuk grafik tertimbang, nilai AIJ dapat digunakan untuk mewakili ukuran berat. Dua grafik di atas adalah grafik tanpa bobot, sehingga nilainya 1.
Tabel yang berdekatan
Kita tahu bahwa metode penyimpanan matriks adjacency dari grafik menggunakan matriks n*n. Ketika matriks ini adalah matriks padat (misalnya, ketika grafik adalah grafik lengkap), maka tentu saja, metode penyimpanan matriks adjacency dipilih.
Tetapi jika matriks ini adalah matriks yang jarang, struktur penyimpanan tabel yang berdekatan adalah struktur penyimpanan yang lebih hemat ruang.
Untuk grafik yang tidak diarahkan di atas, kita dapat menggunakan tabel yang berdekatan untuk mewakilinya sebagai berikut:
Node yang terhubung ke setiap node adalah simpul yang berdekatan.
Perbandingan antara matriks kedekatan dan tabel kedekatan
Ketika jumlah node dalam grafik kecil dan ada banyak sisi, efisiensi menggunakan matriks adjacency lebih tinggi.
Ketika jumlah node sangat besar dan jumlah tepi jauh lebih kecil dari jumlah tepi grafik lengkap dari node yang sama, lebih efisien untuk mengadopsi struktur penyimpanan tabel yang berdekatan.
Implementasi Java dari matriks kedekatan
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;/** * @description Kelas model matriks yang berdekatan * @author beanlam * @Time 2015.4.17 */kelas publik amwgraph {private arraylist vertexlist; // poin penyimpanan int [] [] edges;//num -noMRACENT PERTINGGIAN; tepi amwgraph publik (int n) {// inisialisasi matriks, array satu dimensi, dan jumlah tepi tepi = int int [n] [n]; vertexList = new arraylist (n); numofedges = 0; } // Dapatkan jumlah node int int getNumofVertex () {return vertexList.size (); } // Dapatkan jumlah tepi int getNumofedges publik () {return numofedges; } // mengembalikan data node i objek publik getValueByIndex (int i) {return vertexList.get (i); } // mengembalikan berat v1, v2 public int getweight (int v1, int v2) {edge return [v1] [v2]; } // Masukkan node public void insertVertex (objek vertex) {vertexList.add (vertexList.size (), vertex); } // Masukkan simpul public void insertEdge (int v1, int v2, int bobot) {edges [v1] [v2] = berat; numofedges ++; } // Hapus simpul public void deleteedge (int v1, int v2) {edges [v1] [v2] = 0; numofedges--; } // Dapatkan indeks node pertama yang berdekatan int int getFirstneighbor (int index) {for (int j = 0; j <vertexList.size (); j ++) {if (edges [index] [j]> 0) {return j; }} return -1; } // Ambil simpul adjacency berikutnya sesuai dengan subskrip dari node adjacency sebelumnya int getNextneighbor (int v1, int v2) {for (int j = v2+1; j <vertexlist.size (); j ++) {if (tepi [v1] [j]> 0) {return j; }} return -1; }}Pengujian kelas model matriks adjasensi
Selanjutnya, atur kelas model uji berdasarkan grafik terarah berikut
Program tes testamwgraph.java adalah sebagai berikut:
/** * @Description Tes kelas AMWGRAPH Kelas * @Author beanlam * @Time 2015.4.17 */kelas publik testamwgraph {public static void main (string args []) {int n = 4, e = 4; // mewakili jumlah node dan jumlah tepi masing -masing label string [] = {"" "" "" "" "" "" "" identifikasi amwgraph grafik = amwgraph baru (n); untuk (label string: label) {graph.insertVertex (label); // masukkan node} // masukkan empat edge graph.insertedge (0, 1, 2); graph.insertedge (0, 2, 5); graph.insertedge (2, 3, 8); graph.insertedge (3, 0, 7); System.out.println ("Jumlah node adalah:"+graph.getNumofVertex ()); System.out.println ("Jumlah tepi adalah:"+graph.getNumofedges ()); graph.deleteedge (0, 1); // hapus <v1, v2> edge system.out.println ("Setelah penghapusan <v1, v2> edge ..."); System.out.println ("Jumlah node adalah:"+graph.getNumofVertex ()); System.out.println ("Jumlah tepi adalah:"+graph.getNumofedges ()); }}Hasil output konsol ditunjukkan pada gambar di bawah ini:
Meringkaskan
Di atas adalah semua konten artikel ini tentang deskripsi bahasa Java dari struktur penyimpanan dan contoh kode matriks adjacency. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya.