Pengantar Grafik Tidak Terreksi dari Tabel yang Berdekatan
Grafik yang tidak diarahkan dari tabel adjacency mengacu pada grafik yang tidak diarahkan yang diwakili oleh tabel yang berdekatan.
Gambar G1 di atas berisi 7 simpul "a, b, c, d, e, f, g", dan berisi 7 tepi "(a, c), (a, d), (a, f), (b, c), (c, d), (e, g), (f, g)".
Matriks di sebelah kanan gambar di atas adalah kedekatan G1 dalam memori yang menunjukkan niat. Setiap simpul berisi daftar tertaut yang merekam "nomor urutan titik yang berdekatan dari simpul". Misalnya, data node yang terkandung dalam daftar tertaut yang terkandung dalam simpul kedua (simpul C) masing -masing "0, 1, 3"; Dan "0, 1, 3" ini sesuai dengan angka urutan "a, b, d", dan "a, b, d" adalah semua titik yang berdekatan dari C. Ini adalah cara merekam informasi gambar.
Deskripsi Kode Grafik Tabel yang tidak diarahkan
1. Definisi Dasar
public class ListUDG {// The vertex that adjaces the table corresponding to the linked list private class ENode {int ivex;// The position of the vertex that the edge points to ENode nextEdge;// Pointer to the next arc}// The vertex that adjaces the table in the table private class VNode {char data;// Vertex information ENode firstEdge;// Pointer to the first arc that attaches to the vertex};private Vnode [] mvexs; // vertex array ...}(01) ListUDG adalah struktur yang sesuai dengan tabel kedekatan. MVEXS adalah array satu dimensi yang menyimpan informasi verteks.
(02) Vnode adalah struktur yang sesuai dengan simpul tabel yang berdekatan. Data adalah data yang terkandung dalam simpul, dan FirstEdge adalah penunjuk header dari daftar tertaut yang terkandung dalam simpul.
(03) Enode adalah struktur yang sesuai dengan node yang berdekatan dengan daftar tertaut yang terkandung dalam simpul tabel. IVEX adalah indeks simpul yang sesuai dengan node ini di VEXS, sementara NextEdge menunjuk ke simpul berikutnya.
2. Buat matriks
Berikut adalah dua metode untuk membuat matriks. Yang satu menggunakan data yang diketahui, dan yang lainnya mengharuskan pengguna untuk memasukkan data secara manual.
2.1 Buat grafik (menggunakan matriks yang disediakan)
/ * * Buat grafik (menggunakan matriks yang disediakan) * * Parameter Deskripsi: * VEXS - Vertex Array * Edges - Edge Array */Public ListUdg (char [] vexs, char [] [] edge) {// inisialisasi "vertex" dan "edge" int vlen = vexs.length; int elen = edges. ; tepi [i] [0]; char c2 = tepi [i] [1]; // Baca titik awal dan simpul akhir dari tepi int p1 = getPosition (tepi [i] [0]); int p2 = getPosition (edge [i] [1]); // inisialisasi node1enoda node1 = new enode (); node1. P1 terletak "if (mVEXS [p1] .firstedge == null) mvexs [p1] .firstedge = node1; else linkLast(mVexs[p1].firstEdge, node1);// Initialize node2ENode node2 = new ENode();node2.ivex = p1;// Link node2 to "the end of the linked list where p2 is located" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; Lain LinkLast (MVEXS [P2] .Firstedge, Node2);}}Fungsinya adalah untuk membuat grafik yang tidak diarahkan dari tabel yang berdekatan. Faktanya, grafik yang tidak diarahkan yang dibuat oleh metode ini adalah Gambar G1 di atas. Kode panggilan adalah sebagai berikut:
char [] vexs = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; char [] [] edges = new char [] [] {'a', 'c'}, {'a', 'd'}, {'a', 'f'}, {'a', 'd'}, {'a', 'f' f '},' c ' {'E', 'g'}, {'f', 'g'}}; listudg pg; pg = new listudg (vexs, edges);2.2 Buat grafik (masukkan diri Anda)
/ * * Buat grafik (masukkan data sendiri) */listudg publik () {// masukkan "nomor versi" dan "edge number" system.out.printf ("Input vertex number:"); int vlen = readInt (); System.out.printf ("Input Edge Number:"); int elen = readInt (); if (vlen <1 || 1))))) {System.out.printf ("Kesalahan input: parameter tidak valid!/N"); return;} // inisialisasi "versi" mvexs = vnode baru [vlen]; for (int i = 0; i <mvexs.length; i ++) {System.out.printf ("vertex (%d); i ++) {System.out.printf (" vertex (%d); i ++) {System.out.printf ("vertex (%d); Vnode (); mvexs [i] .data = readChar (); mvexs [i] .firstedge = null;} // inisialisasi "edge" // mmatrix = int int [vlen] [vlen]; untuk (int i = 0; i <elen; i ++) {// baca awal dan ending edge dari edge. ); char c1 = readChar (); char c2 = readChar (); int p1 = getPosition (c1); int p2 = getPosition (c2); // inisialisasi node1enode node1 = new enode (); node1.ivex = p2; // tautan node1 ke "akhir dari daftar terhubung di mana p1 link (node -node (p1 link node1 to" MVEXS [p1] .firstedge = node1; else linkLast(mVexs[p1].firstEdge, node1);// Initialize node2ENode node2 = new ENode();node2.ivex = p1;// Link node2 to "the end of the linked list where p2 is located" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; Lain LinkLast (MVEXS [P2] .Firstedge, Node2);}}Fungsi ini membaca input pengguna dan mengubah data input menjadi grafik yang tidak diarahkan.
Kode sumber lengkap dari grafik tidak terarah dari tabel adjacency
impor java.io.ioException; impor java.util.scanner; kelas publik listudg {// simpul yang berdekatan dengan daftar tertaut yang sesuai dengan tabel di tabel private class enode {int ivex; data;// Vertex information ENode firstEdge;// Pointer to the first arc that is attached to the vertex};private VNode[] mVexs;// Vertex array/* * Create a graph (input data by yourself) */public ListUDG() {// Enter "Vertex Number" and "Edge Number"System.out.printf("input vertex number: ");int vlen = readInt (); System.out.printf ("Nomor tepi input:"); int elen = readInt (); if (vlen <1 || elen <1 || (elen> (vlen*(mlen - 1)))) {System.out.printf ("Input Kesalahan: Parameter yang tidak valid!/N"); return; = ("verx" verx: Parameter tidak valid!/n "); retrib Vnode [vlen]; for (int i = 0; i <mvexs.length; i ++) {System.out.printf ("vertex (%d):", i); mvexs [i] = vnode baru (); mvexs = noDeP; nOLEDACE = readarchar (); mvExs [i]. int [vlen] [vlen]; for (int i = 0; i <elen; i ++) {// Baca titik awal dan akhir dari sistem tepi.out.printf ("edge (%d):", i); char c1 = readChar (); char c2 = readChar (); int p1 = getPosition (c1); int p2 = c2 = readChar (); int p1 = getPosition (c1); baru enode (); node1.ivex = p2; // tautan node1 ke "akhir dari daftar tertaut di mana p1 berada" if (mvexs [p1] .firstedge == null) mvexs [p1] .firstedge = node1; else linkLast(mVexs[p1].firstEdge, node1);// Initialize node2ENode node2 = new ENode();node2.ivex = p1;// Link node2 to "the end of the linked list where p2 is located" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; Lain LinkLast (MVEXS [P2] .Firstedge, node2);}}/ * * Buat grafik (menggunakan matriks yang disediakan) * * Deskripsi parameter: * vexs - array vertex * tepi - edge array */public listudg (char [] vexs, char [] [] edge) {// inisix public (vert "vert" ver "ver" ver "ver" ver "ver" ver "nomor" vert "ver" ver "nomor" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver "ver" ver edges.length; // inisialisasi "vertex" mvexs = vnode baru [vlen]; untuk (int i = 0; i <mvexs.length; i ++) {mvexs [i] = vnode baru (); mvexs [i] .data = vexs [i]; mvexs [i]. firsedge = nulled = neure [i]; mvexs [i] .firsede [i] .data = vexs [i]; mvexs [i]. firsedge [i]. neulge = neUxs [i]; mvexs [i]. i <elen; i ++) {// Baca titik awal dan simpul akhir dari edge char C1 = tepi [i] [0]; char c2 = tepi [i] [1]; // Baca verteks awal dan simpul edgosisi (edgosisi 1) (edge] [i] [0]); int p2 = getPosisi edgosisi = getPosisi (edges [i] [0]); int p2 = getposisi edgose = getPosition (edges [i] [0]); int p2 = getPosisi edgose = getPosition (edges [i] [0]); int p2 = getPosition Enode (); node1.ivex = p2; // tautan node1 ke "akhir dari daftar tertaut di mana p1 berada" if (mvexs [p1] .firstedge == null) mvexs [p1] .firstedge = node1; else linkLast(mVexs[p1].firstEdge, node1);// Initialize node2ENode node2 = new ENode();node2.ivex = p1;// Link node2 to "the end of the linked list where p2 is located" if(mVexs[p2].firstEdge == null) mVexs[p2].firstEdge = node2; Lain LinkLast (MVEXS [P2] .Firstedge, node2);}}/** tautkan simpul simpul ke daftar terakhir*/private void linkLast (daftar enode, enode node) {enode p = while; while (p.nextedge! = null) p = p.nextedge; p.nextedge = node; ; {E.PrintStackTrace ();}} while (! ((ch> = 'a' && ch <= 'z') || (ch> = 'a' && ch <= 'z'))); return ch;}/* Baca karakter input*/private int readint () {scanner scanner = scanner new scanner (System.in.in); grafik antrian*/public void print () {System.out.printf ("Daftar Grafik:/n"); untuk (int i = 0; i <mvexs.length; i ++) {System.out.printf ("%d (%c):", i, mvexs [i] .data); enode node = mvxsEdge [i. while (node! = null) {System.out.printf ("%d (%c)", node.ivex, mvexs [node.ivex] .data); node = node.nextEdge;} System.out.printf ("/n");}} public static void main (string [] '', '', ',', ',' '); 'D', 'e', 'f', 'g'}; char [] [] edges = new char [] [] {{'a', 'c'}, {'a', 'd'}, {'a', 'f'}, {'b', 'c'}, {'c', 'd'}, {'b', 'c' {'c', 'd', '{', 'G'}}; listudg pg; // "grafik" kustom (antrian matriks input) // pg = new listudg (); // gunakan "grafik" yang ada pg = ListUdg baru (vexs, edge); pg.print (); // cetak diagram}}}Meringkaskan
Di atas adalah semua konten dari artikel ini tentang mengimplementasikan kode sumber lengkap dari bahasa Java dari tabel yang berdekatan grafik yang tidak diarahkan. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke situs ini:
Penjelasan terperinci tentang Kode Ekspresi Matematika Java
Penjelasan terperinci tentang kode parameter panjang variabel di java
Solusi bahasa Java untuk analisis kode angka yang sempurna
Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!