Introducción a gráficos no dirigidos de tablas adyacentes
Un gráfico no dirigido de una tabla de adyacencia se refiere a un gráfico no dirigido representado por una tabla de adyacencia.
La figura G1 anterior contiene 7 vértices de "A, B, C, D, E, F, G", y contiene 7 bordes de "(A, C), (D), (A, F), (B, C), (C, D), (E, G), (F, G)".
La matriz a la derecha de la figura anterior es la adyacencia de G1 en la memoria que indica la intención. Cada vértice contiene una lista vinculada que registra el "número de secuencia de los puntos adyacentes del vértice". Por ejemplo, los datos de los nodos contenidos en la lista vinculada contenida en el segundo vértice (vértice c) son respectivamente "0, 1, 3"; y estos "0, 1, 3" corresponden a los números de secuencia de "A, B, D" y "A, B, D" son todos puntos adyacentes de C. Esto es cómo registrar la información de la imagen.
Descripción del código del gráfico no dirigido de la tabla de adyacencia
1. Definición básica
clase pública listudg {// El vértice que adjunta la tabla correspondiente a la lista de la lista vinculada Enode de clase privada {int ivex; // La posición del vértice que el borde apunta a enode nextEdge; // puntero a la siguiente arc} // el vértice que adjunta la tabla en la tabla de la tabla VNODE {char data; // Vértex información primero en ENODE; // Puntador de puntero a la primera a la tabla de la tabla VNODE VNODE {DATA CHAR; // VERTEX INFORMACIÓN FIRMEDE; // Puntador de puntero; vértice}; private vnode [] mvexs; // vértice array ...}(01) Listudg es la estructura correspondiente a la tabla de adyacencia. MVEXS es una matriz unidimensional que almacena información de vértices.
(02) VNode es la estructura correspondiente a los vértices de la tabla adyacente. Los datos son los datos contenidos en el vértice, y FirstEdge es el puntero de encabezado de la lista vinculada contenida en el vértice.
(03) ENODE es la estructura correspondiente a los nodos que están adyacentes a la lista vinculada contenida en los vértices de la tabla. IVEX es el índice del vértice correspondiente a este nodo en VEXS, mientras que NextEdge apunta al siguiente nodo.
2. Crea una matriz
Aquí hay dos métodos para crear una matriz. Uno usa datos conocidos, y el otro requiere que el usuario ingrese los datos manualmente.
2.1 Crear un gráfico (usando la matriz proporcionada)
/ * * Crear un gráfico (usando la matriz proporcionada) * * Descripción del parámetro: * vexs - vértice matriz * bordes - matriz de borde */public listudg (char [] vexs, char [] [] edges) {// inicialize "vértice" y "borde" int vlen = vexs.length; int elen = edges.length;//inicialize "Vexs" MVEXS "MVEXS" MVEXS "MVEXS" MVEXS "MVEXS" MVEXS "MVEXS" Vnode [vlen]; for (int i = 0; i <mvexs.length; i ++) {mvexs [i] = new vnode (); mVExs [i] .data = vexs [i]; mVexs [i] .firstedge = null;} // Inicializar "anillos" para (int i = 0; i <elen; i++) finalización del vértice del borde char c1 = bordes [i] [0]; char c2 = bordes [i] [1]; // Lea el vértice inicial y el vértice final del borde int p1 = getposition (bordes [i] [0]); int p2 = getPosition (bordes [i] [1]); // nodo1enode node1 = neweode ();); node1.//////////////////////////////////////////////P2; Nodo de enlace1 al "el final de la lista vinculada donde se encuentra P1" if (mVEXS [p1] .firstedge == null) mVEXS [P1] .firstedge = node1; else LinkLast (mVEXS [p1] .firstedge, node1); // inicializar node2Enode node2 = new enode (); node2.ivex = p1; // enlace node2 al "final de la lista vinculada donde p2 está ubicado" if (mVexs [p2] .firstedge == null) mVExs [p2] .first enghedge else Linklast (MVEXS [P2] .Firstedge, Node2);}}La función es crear un gráfico no dirigido de una tabla de adyacencia. De hecho, el gráfico no dirigido creado por este método es la Figura G1 anterior. El código de llamada es el siguiente:
char [] vexs = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; char [] [] edges = new char [] [] {{{'a', 'c'}, {'a', 'd'}, {'a', 'f'}, {'b', 'c'},},},},}, d '},, d',,, d, ', d', ', d,'}, ', d,',}, 'c',,,,,,},, d ',,},,},},},},},,},},,},,},},,},,},,},},},,,}. {'E', 'g'}, {'f', 'g'}}; listudg pg; pg = new Listudg (vexs, bordes);2.2 Crear un gráfico (ingrese usted mismo)
/* * Create a graph (enter the data yourself) */public ListUDG() {// Enter "Version Number" and "Edge Number" System.out.printf("input vertex number: ");int vlen = readint();System.out.printf("input edge number: ");int elen = readint();if (vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))))) {System.out.printf ("Error de entrada: Parámetros no válidos!/N"); return;} // Inicializar "Versión" mVEXS = new vnode [vlen]; for (int i = 0; i <mvexs.length; i ++) {system.out.preintf ("vertex (%d):", i); mvexs [i] Vnode (); mvexs [i] .data = readchar (); mVExs [i] .firstedge = null;} // inicializar "borde" // mmatrix = new int [vlen] [vlen]; for (int i = 0; i <elen; i ++) {// leer el vértice inicial y final del vértex de borde. i); char c1 = readchar (); char c2 = readchar (); int p1 = getPosition (c1); int p2 = getPosition (c2); // inicializar node1Enode node1 = new enode (); node1.ivex = p2; // enlace node1 a "el end de la lista vinculada cuando p1 se encuentra" if (mvexs [p1]. mvexs [p1] .firstedge = node1; else LinkLast (mVEXS [p1] .firstedge, node1); // inicializar node2Enode node2 = new enode (); node2.ivex = p1; // enlace node2 al "final de la lista vinculada donde p2 está ubicado" if (mVexs [p2] .firstedge == null) mVExs [p2] .first enghedge else Linklast (MVEXS [P2] .Firstedge, Node2);}}Esta función lee la entrada del usuario y convierte los datos de entrada en el gráfico no dirigido correspondiente.
El código fuente completo del gráfico no dirigido de la tabla de adyacencia
import java.io.ioException; import java.util.scanner; public class Listudg {// El vértice que está adyacente a la lista vinculada correspondiente a la tabla en la tabla privada de clase privada enode {int ivex; // la posición de la vertex que el borde apunta a enode nextEdge ;// el pozo del siguiente pozo arc} // el vértice que es adjacente a la tabla de la tabla en la tabla en la tabla en la tabla en la tabla de endeode; {char data; // Vertex Information Enode FirstEdge; // puntero al primer arco que se adjunta al vértice}; private vnode [] mVExs; // vértice array/ * * crea un gráfico (datos de entrada por usted) */public listG () {// Ingrese "número de vertex" y "edge Number". readInt (); system.out.printf ("Número de entrada de entrada:"); int elen = readInt (); if (vlen <1 || elen <1 || (elen> (vlen*(vlen - 1))))) {System.out.printf ("Error de entrada: Parámetros no válidos!/N"); return;} // Initialize "VERTEX" "Mvexs" Vnode [vlen]; for (int i = 0; i <mvexs.length; i ++) {system.out.printf ("vértice (%d):", i); mVExs [i] = new vnode (); mVExs [i] .data = readchar (); mvexs [i] .firstedge = null;} // inicialize " int [vlen] [vlen]; for (int i = 0; i <elen; i ++) {// lea el vértice inicial y final del borde system.out.printf ("borde (%d):", i); char c1 = readchar (); char c2 = readchar (); int p1 = getPosition (c1); int p2 = getPosition (c2); = new Enode (); node1.ivex = p2; // enlace node1 a "el final de la lista vinculada donde p1 está ubicado" if (mVEXS [p1] .firstedge == null) mvexs [p1] .firstedge = node1; else LinkLast (mVEXS [p1] .firstedge, node1); // inicializar node2Enode node2 = new enode (); node2.ivex = p1; // enlace node2 al "final de la lista vinculada donde p2 está ubicado" if (mVexs [p2] .firstedge == null) mVExs [p2] .first enghedge else Linklast (mVEXS [p2] .firstedge, node2);}}/ * * Crear un gráfico (usando la matriz proporcionada) * * Descripción del parámetro: * VEXS - Vertex Array * Edges - Edge Array */Public Listudg (Char [] VEXS, char [] [] bordes) {//100 = edges.length; // inicializar "vértice" mVExs = new vnode [vlen]; for (int i = 0; i <mvexs.length; i ++) {mvexs [i] = new vnode (); mvexs [i] .Data = vexs [i]; mvexs [i] .frirst ida 0; node1 = new eNode (); node1.ivex = p2; // enlace node1 a "el final de la lista vinculada donde p1 está ubicado" if (mVEXS [p1] .firstedge == null) mVEXS [p1] .firstedge = node1; else LinkLast (mVEXS [p1] .firstedge, node1); // inicializar node2Enode node2 = new enode (); node2.ivex = p1; // enlace node2 al "final de la lista vinculada donde p2 está ubicado" if (mVexs [p2] .firstedge == null) mVExs [p2] .first enghedge más linklast (mVExs [p2] .firstedge, node2);}}/** enlace el nodo del nodo a la última de la lista*/private void linklast (enode list, enode node) {enode p = list; while (p.nextedge! = null) p = p.nextedge; p.nextedge = node;}/** return the la lista; (int i = 0; i <mvexs.length; i ++) if (mVExs [i] .data == ch) return i; return -1;}/** lea un carácter de entrada*/private char readchar () {char ch = '0'; do {try {ch = (char) system.in.read ();} captura (ioexception e) {E.PrintStackTrace ();}} while (! ((ch> = 'a' && ch <= 'z') || (ch> = 'a' && ch <= 'z')); return ch;}/** leer un carácter de entrada*/private int readint () {Scanner Scanner = new Scanner (System.in); return Scanner.nextInt ();}/}/* Graph*/public void print () {System.out.printf ("List Graph:/n"); for (int i = 0; i <mvexs.length; i ++) {System.out.printf ("%d (%c):", i, mvexs [i] .data); Enode Node = mVexs [i] .fredge; while (node! = null) {system.out.printf ("%d (%c)", node.ivex, mVExs [node.ivex] .data); node = node.nextedge;} system.out.printf ("/n");}} public estática principal (string [] string [] vexs 'D', 'e', 'f', 'g'}; char [] [] edges = new char [] [] {{{a ',' c '}, {' a ',' d '}, {' a ',' f '}, {' b ',' c '}, {' c ',' d '}, {' e ',' g '},},},},},},}, f' f 'f' f ', 'G'}}; listudg pg; // personalizado "gráfico" (cola de matriz de entrada) // pg = new Listudg (); // Use el "gráfico" existente PG = nuevo Listudg (Vexs, Edges); pg.print (); // Imprimir diagrama}}Resumir
Lo anterior es todo el contenido de este artículo sobre la implementación del código fuente completo del lenguaje Java del gráfico no dirigido a la tabla de adyacencia. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a este sitio:
Explicación detallada del código de expresión matemática de cálculo Java
Explicación detallada del código de parámetro de longitud variable en Java
Solución de lenguaje Java para un análisis de código de número perfecto
Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!