Estructura de almacenamiento
Para almacenar un gráfico, sabemos que el gráfico tiene nodos y bordes. Para un gráfico alimentado, cada borde también tiene un valor de peso. Hay dos tipos principales de estructuras de almacenamiento de gráficos de uso común:
Matriz adyacente Tabla adyacente
Matriz adyacente
Sabemos que para representar nodos, podemos representarlos con una matriz unidimensional. Sin embargo, para la relación entre nodos, no podemos simplemente representarlos con una matriz unidimensional. Podemos representarlos con una matriz bidimensional, es decir, un método de representación de formación de matriz.
Suponemos que A es esta matriz bidimensional, entonces un elemento AIJ en A no solo refleja la relación entre el nodo VI y el nodo VJ, sino también el valor de AIJ puede representar el tamaño del peso.
Aquí hay un ejemplo de una representación de matriz de adyacencia de un gráfico no dirigido:
De la figura anterior podemos ver que la matriz de adyacencia del gráfico no dirigido es una matriz simétrica, y debe ser una matriz simétrica. Y el valor en la diagonal desde la esquina superior izquierda hasta la esquina inferior derecha es cero (la diagonal indica el mismo nodo)
¿Cuál es la matriz de adyacencia de un gráfico dirigido?
Para gráficos ponderados, el valor de AIJ se puede usar para representar el tamaño del peso. Los dos gráficos anteriores son gráficos sin pesos, por lo que sus valores son ambos 1.
Mesa adyacente
Sabemos que el método de almacenamiento de la matriz de adyacencia del gráfico utiliza una matriz N*n. Cuando esta matriz es una matriz densa (por ejemplo, cuando el gráfico es un gráfico completo), entonces, por supuesto, se elige el método de almacenamiento de la matriz de adyacencia.
Pero si esta matriz es una matriz escasa, la estructura de almacenamiento de tabla adyacente es una estructura de almacenamiento más ahorrador de espacio.
Para el gráfico no dirigido anterior, podemos usar una tabla de adyacencia para representarlo de la siguiente manera:
El nodo conectado a cada nodo es su nodo adyacente.
Comparación entre la matriz de adyacencia y la tabla de adyacencia
Cuando el número de nodos en el gráfico es pequeño y hay muchos lados, la eficiencia de usar una matriz de adyacencia es mayor.
Cuando el número de nodos es muy grande y el número de bordes es mucho menor que el número de bordes del gráfico completo del mismo nodo, es más eficiente adoptar una estructura de almacenamiento de tabla de adyacencia.
Implementación de Java de la matriz de adyacencia
Clase de modelo de matriz adyacente
El nombre de clase de la clase de modelo de matriz de adyacencia es amwgraph.java. Puede construir un gráfico representado por una matriz de adyacencia a través de esta clase, y proporcionar nodos de inserción, insertar bordes y obtener el primer nodo de adyacencia y el siguiente nodo de adyacencia de un determinado nodo.
import java.util.arrayList; import java.util.linkedList;/** * @Description Class de modelo de matriz adyacente * @Author Beanlam * @time 2015.4.17 */public class amwgraph {private private arrayList vertexlist; ///de almacenamiento int [] [] [] edgs; // adyacent matrix de store intrayges intrayges; ////de almacenamiento privado int [] [] Edges; // adyacentes, soluciones de inicio de arrayes privados; Bordes public Amwgraph (int n) {// Inicializar matriz, matriz unidimensional y número de bordes bordes = new int [n] [n]; VERTEXLIST = new ArrayList (n); numOfEdges = 0; } // Obtenga el número de nodos public int getNuMOfvertex () {return vertexList.size (); } // Obtenga el número de bordes públicos int getNumofedges () {return numOfEdges; } // Devuelve los datos del nodo I Public Object getValueByIndex (int i) {return vertexlist.get (i); } // Devuelve el peso de V1, V2 public int } // Inserte el nodo público void insertverx (objeto vértice) {vertexlist.add (vertexlist.size (), vértice); } // Inserte el nodo público void insertedge (int v1, int v2, int weight) {bordes [v1] [v2] = peso; NUMOFEDGES ++; } // Eliminar nodo public void deletedge (int v1, int v2) {bordes [v1] [v2] = 0; NUMOFEDGES--; } // Obtenga el índice del primer nodo adyacente público int getFirstneighbor (int index) {for (int j = 0; j <vertexlist.size (); j ++) {if (edges [index] [j]> 0) {return j; }} return -1; } // Obtenga el siguiente nodo de adyacencia de acuerdo con el subíndice del nodo de adyacencia anterior int getNextNeighbor (int v1, int v2) {for (int j = v2+1; j <vertexlist.size (); j ++) {if (edges [v1] [j]> 0) {return j; }} return -1; }}Prueba de la clase de modelo de matriz de adyacencia
A continuación, configure la clase de modelo de prueba en función del siguiente gráfico dirigido
El programa de prueba testamwgraph.java es el siguiente:
/** * @Description Test Class of Amwgraph Class * @author Beanlam * @time 2015.4.17 */public class testamwgraph {public static void main (string args []) {int n = 4, e = 4; // representa el número de nodos y el número de bordes respectivamente las etiquetas de cadena [] = {"v1", "v1", "V3", "v4" "" "," "", "V4"; Identificación AmwGraph Graph = new AmwGraph (n); for (etiqueta de cadena: etiquetas) {gráfico.insertversex (etiqueta); // insertar nodo} // insertar cuatro bordes gráfico. Insertedge (0, 1, 2); Graph.Insertedge (0, 2, 5); Graph.Insertedge (2, 3, 8); Graph.Insertedge (3, 0, 7); System.out.println ("El número de nodos es:"+Graph.getNuMOfvertex ()); System.out.println ("El número de bordes es:"+Graph.getNuMOfEdges ()); Graph.DelEdedeedge (0, 1); // Eliminar <v1, v2> borde system.out.println ("después de la deleción <v1, v2> borde ..."); System.out.println ("El número de nodos es:"+Graph.getNuMOfvertex ()); System.out.println ("El número de bordes es:"+Graph.getNuMOfEdges ()); }}Los resultados de salida de la consola se muestran en la figura a continuación:
Resumir
Lo anterior es todo el contenido de este artículo sobre la descripción del lenguaje Java de la estructura de almacenamiento y los ejemplos de código de matriz de adyacencia. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo.