En este post conoceremos una forma de representar grafos mediante una Matriz de Adyacencia y un ejemplo básico de este en lenguaje java.
¿Qué es una Matriz de Adyacencia?
Es una matriz cuadrada de n filas x n columnas donde, n es la máxima cantidad de nodos que tiene el grafo. Es la forma más sencilla de representar un grafo, pero a la vez, requiere más espacio de memoria que otros métodos, por lo que requiere al menos n^2 bits de memoria.
¿Como construir una Matriz de Adyacencia?
Para construir una matriz de adyacencia, debemos tomar en cuenta los siguientes aspectos:
Ejemplo Grafo no dirigido
Este grafo consta de 5 vértices (nodos), por tanto nuestra matriz de adyacencia sera 5×5
Completamos para la primera fila de la siguiente manera:
Y para el resto de las filas, tenemos:
Algo que podemos notar es que cuando el grafo es no dirigido, la matriz resultante es simétrica respecto a la diagonal principal.
Ejemplo Grafo dirigido
Para representar un grafo dirigido con una matriz de adyacencia se usan los mismos pasos de un grafo no dirigido, tomando en cuesta esta vez, la dirección de cada arista.
Representación en lenguaje java
Siguiendo el ejemplo de este post, la matriz de adyacencia sera de tipo entero, sin pesos, se implementan los métodos mínimos de agregar, remover e imprimir. El código es sencillo y fácil de entender por lo que no requiere de más comentarios.
/** * @see https://www.jc-mouse.net/ * @author mouse */ public class Matriz_de_adyacencia { private int n; private int[][] matriz; /** * Constructor de clase * @param n numero de nodos */ public Matriz_de_adyacencia(int n) { this.n = n; matriz = new int[this.n][this.n]; //se inicializa matriz en 0 for(int i=0; i< n; i++){ for(int j=0; j< n; j++){ matriz[i][j] = 0; } } } public void agregar(int i, int j){ matriz[i][j] += 1; } public void remover(int i, int j){ if(matriz[i][j]>0) matriz[i][j] -= 1; } public void imprimir(){ for(int i=0; i< n; i++){ for(int j=0; j< n; j++){ System.out.print( matriz[i][j] + " " ); } System.out.println(); } } }
Y ahora implementado la clase anterior con el grafo no dirigido usado como ejemplo en este post, tenemos lo siguiente:
public static void main(String[] args) { Matriz_de_adyacencia matriz = new Matriz_de_adyacencia(5); matriz.agregar(0, 1); matriz.agregar(0, 1); matriz.agregar(0, 2); matriz.agregar(0, 3); matriz.agregar(1, 0); matriz.agregar(1, 0); matriz.agregar(1, 4); matriz.agregar(2, 0); matriz.agregar(2, 3); matriz.agregar(2, 4); matriz.agregar(3, 0); matriz.agregar(3, 2); matriz.agregar(4, 1); matriz.agregar(4, 2); matriz.agregar(4, 4); matriz.agregar(4, 4); matriz.imprimir(); }
Y como salida por consola tendremos:
Yo soy yo :) JC Mouse, Soy orgullosamente boliviano soy fundador y CEO de la web jc-Mouse.net uno de las pocas web en emprendimiento y tecnología en Bolivia.
Toda la información que encuentres en este sitio es y sera completamente gratis siempre, puedes copiar, descargar y re-publicar si así lo deseas en otros blogs o sitios web, solo te pido a cambio que dejes una referencia a esta web. Esto nos ayuda a crecer y seguir aportando. Bye
Enjoy! :)
JavaMail es una expansión de Java que facilita el envío y recepción de e-mail desde código java. JavaMail implementa el...
Editar un documento PDF no es tan sencillo como editar un archivo de texto por ejemplo, para editar archivos PDFs necesi...
Cuando se desarrolla una aplicación, puede ser un requisito que este tenga soporte para varias tipos de base de datos, s...
En este post realizaremos un proyecto en VUE que se conectara a un REST API y utilizara un servicio del mismo para obte...
Una Vista (View) es una Tabla Virtual cuyo contenido está definido por una consulta (SELECT), al igual que una tabla rea...
En este post personalizaremos un componente JComboBox para que sus elementos acepten tablas (JTable) en lugar de texto s...
Los comentarios estan cerrados
Si trabajas con redes sociales (RRSS) a continuación te muestro tres herramintas gratuitas que te ayudaran a la hora de...
Por lo general se usan transacciones a nivel base de datos y posteriormente se llaman estos a través de procedimientos a...
En este post, aprenderemos como conectar Visual Basic 6 con SQL Server, abrir una tabla, leer su contenido y mostrar est...
Lo que veremos en este post es la configuración del driver para PHP de SQL Server que ha creado Microsoft el cual permit...
Hola amigo muy buena tu pagina y didactica para cualquiera que quiere aprender en el mundo de la programacion,yo estoy en mitad la carrera de ing.informatica y tambien soy orgullosamente Boliviano y creo que aqui en Bolivia tambien se puede hacer cosas innovadoras en el mundo del software solo falta las ganas y actitud saludos desde Santa Cruz de la Sierra