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.
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;
clase pública amwgraph {
VERTEXIST DE ARRAYLISTIS PRIVADO;
// La tabla de enlaces de puntos de almacenamiento
bordes privados int [] [];
// Matriz de dirección, utilizada para almacenar bordes
privado int numofedges;
// Número de bordes
public amwgraph (int n) {
// Inicializar la matriz, la matriz unidimensional y el número de bordes
Bordes = new int [n] [n];
VERTEXLIST = new ArrayList (n);
numOfEdges = 0;
}
// Obtener el número de nodos
public int getNuMOfvertex () {
return VertexList.Size ();
}
// Obtener el número de bordes
public int getNumofedges () {
devolver numofedges;
}
// devuelve los datos del nodo I
objeto público getValueByIndex (int i) {
return VertexList.get (i);
}
// devuelve el peso de V1 y V2
public int getweight (int v1, int v2) {
Bordes de retorno [v1] [v2];
}
// Insertar nodo
public void insertverx (objeto vértice) {
VERTEXLIST.Add (VERTEXLIST.SIZE (), Vertex);
}
// Insertar nodo
public void insertedge (int v1, int v2, int weight) {
bordes [v1] [v2] = peso;
NUMOFEDGES ++;
}
// Eliminar nodo
public void Deleteedge (int v1, int v2) {
bordes [v1] [v2] = 0;
NUMOFEDGES--;
}
// Obtener el subíndice del primer nodo adyacente
public int getFirstneighbor (int index) {
para (int j = 0; j <vértexlist.size (); j ++) {
if (edges [index] [j]> 0) {
regresar j;
}
}
regreso -1;
}
// Obtenga el siguiente nodo de adyacencia basado en el subíndice del nodo de adyacencia anterior
public int getNextneighbor (int v1, int v2) {
para (int j = v2+1; j <vertexlist.size (); j ++) {
if (edges [v1] [j]> 0) {
regresar j;
}
}
regreso -1;
}
}Echemos un vistazo al código que implementa la matriz de adyacencia para representar gráficos densos:
paquete com.datastructure.graph;
///// gráfico denso: use la matriz de adyacencia para representar
// clase pública DenseGraph {
//
// private int n; // Número de nodos
// private int m; // número de borde
// Dirigido privado booleano; // ¿Es un gráfico dirigido?
// privado booleano [] [] g; // datos específicos de la imagen
//
// // constructor
// Public DenseGraph (int n, dirigido booleano) {
// afirmar n> = 0;
// this.n = n;
// this.m = 0; // La inicialización no tiene bordes
// this.Directed = dirigido;
// // g se inicializa a una matriz booleana de n*n. Cada g [i] [j] es falso, lo que indica que no hay ninguno y bordes.
// // falso es el valor predeterminado de la variable de tipo booleano
// g = nuevo booleano [n] [n];
//}
//
// public int v () {
// regresar n;
//} // Devuelve el número de nodos
//
// public int e () {
// return m;
//} // devuelve el número de bordes
//
// // Agregar un borde al gráfico
// public void adicional (int v, int w) {
//
// afirmar v> = 0 && v <n;
// afirmar w> = 0 && w <n;
//
// if (Hasedge (V, W))
// devolver;
//
// // conectar V y W
// g [v] [w] = true;
// if (! Dirigido)
// g [w] [v] = true;
//
// // número de bordes ++
// m ++;
//}
//
// // Verifique si hay bordes de V a W en el gráfico
// boolean Hasedge (int v, int w) {
// afirmar v> = 0 && v <n;
// afirmar w> = 0 && w <n;
// return g [v] [w];
//}
//
// // Devuelve todos los vecinos de un vértice en el gráfico
// // Dado que Java usa un mecanismo de referencia, devolver un vector no traerá ninguna sobrecarga adicional.
// public ITerable <Integer> adj (int v) {
// afirmar v> = 0 && v <n;
// vector <integer> adjv = new Vector <Integer> ();
// para (int i = 0; i <n; i ++)
// if (g [v] [i])
// adjv.add (i);
// devolver adjv;
//}
//}
import java.util.arrayList;
import java.util.list;
// Use la matriz de adyacencia para representar gráficos densos
clase pública Densegraph {
privado int n;
// Número de nodos en la figura
privado int m;
// Número de bordes en la imagen
booleano privado [] [] g;
// Matriz adyacente G
booleano privado dirigido;
// ¿Es un gráfico dirigido?
Public DenseGraph (int n, dirigido booleano) {
this.n = n;
// El número de nodos en el gráfico de inicialización
this.m = 0;
// El número de bordes en la figura se inicializa a 0
this.Directed = dirigido;
g = nuevo booleano [n] [n];
// La matriz de adyacencia G se inicializa en una matriz bidimensional de N*n
// El índice representa el nodo en el gráfico, y el valor almacenado en G es si el nodo tiene bordes
}
// devuelve el número de bordes en el gráfico
public int e () {
regresar m;
}
// Devuelve el número de nodos en el gráfico
public int v () {
regresar n;
}
// Agregar bordes entre los dos nodos especificados en la figura
public void adicional (int v, int w) {
if (! Hasedge (V, W)) {
// conectar [v] [w]
g [v] [w] = true;
// Gráfico no dirigido
if (! dirigido)
g [w] [v] = true;
// El número de lados en la imagen +1
m ++;
}
}
// Determinar si hay bordes entre los dos nodos
Booleano privado Hasedge (int v, int w) {
return g [v] [w];
}
// Devuelve los nodos de adyacencia de todos los nodos v
public ITerable <integer> adjacentNode (int v) {
// adyacentl se utiliza para almacenar el nodo adyacente de V
List <integer> adyacentl = new ArrayList <> ();
// Encuentra todos los nodos adyacentes a V y agrégalos a adjacentl
para (int i = 0; i <n; i ++) {
if (g [v] [i])
adyacentl.add (i);
}
regreso adyacentl;
}
}
Resumir
Lo anterior es todo el contenido de este artículo sobre la programación de Java para implementar el ejemplo del código de representación densa de gráficos de la matriz de adyacencia, y espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a este sitio:
Análisis de conceptos básicos y ejemplos de código del árbol de estructura de datos Java
Preguntas de la entrevista de la estructura de datos comunes de Java (con respuestas)
Principio de algoritmo de coincidencia de cadena multimodo y código de implementación de Java
Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!