Sigueme en Facebook Sigueme en Twitter Sigueme en Instagram Sigueme en Youtube
JC Mouse Bolivia
Index / Java / Matriz de Adyacencia: Representación de grafos en Java

Matriz de Adyacencia: Representación de grafos en Java

Autor jc mouse jueves, enero 5, 2017

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:

  • A cada elemento (i,j) se suma 1, cuando exista una arista que una los vértices (nodos) i y j.
  • Si una arista es un bucle, y el grafo es no dirigido, se suma 2 en ves de 1.
  • Cada elemento (i,j) valdrá 0, cuando no exista una arista que una los nodos i y j.

Ejemplo Grafo no dirigido

graph

Este grafo consta de 5 vértices (nodos), por tanto nuestra matriz de adyacencia sera 5×5

matriz vacio

Completamos para la primera fila de la siguiente manera:

  • El nodo 1 no es un bucle, por tanto (1,1), vale 0
  • Vemos que del vértice 1 al vértice 2, salen dos aristas, por tanto para (1,2) sumamos +1 para cada arista, es decir, (1,2) vale 2
  • De 1 a 3 existe una arista, (1,3)=1
  • De 1 a 4 existe una arista, (1,4)=1
  • De 1 a 5 no existe ninguna arista, por tanto, (1,5)=0

primera linea

Y para el resto de las filas, tenemos:

Adjacency

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

Adjacency matrix

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.

dirigido matriz

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 http://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:

graph java

 

Tags

Si te ha gustado podrías compartirlo o dejar un comentario. ¡Muchas gracias!
Autor: JC Mouse

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! :)

También Te Podría Interesar

Arrastrar y cargar archivo Excel *.xlsx en tabla Java

Arrastrar y cargar archivo Excel *.xlsx en tabla Java

A continuación tenemos una clase que nos permite arrastrar un archivo de Excel (*.xlsx) y cargar su contenido en una tab...

Creación de GUI con Matlab GUIDE

Creación de GUI con Matlab GUIDE

En este videotutorial se vera la creación de Interfaces Gráficas de Usuario (GUI) utilizando MatLab GUIDE herramienta vi...

GSON: Generar objetos java desde JSON

GSON: Generar objetos java desde JSON

En un post anterior vimos como utilizar GSON para serializar un objeto java en JSON, en esta oportunidad se vera el proc...

Crear e instalar modulo NBM

Crear e instalar modulo NBM

Este post es la continuación del tutorial “Generador de código para Netbeans“ en donde vimos como crear un m...

GSON: Convertir array JSON en List de objetos Java

GSON: Convertir array JSON en List de objetos Java

En este ejemplo tenemos un array en JSON el cual representa una lista de alumnos y queremos llevar este a una lista en j...

Crea una ventana de dialogo “Acerca de…” personalizado

Crea una ventana de dialogo “Acerca de…” personalizado

Cuando se crean aplicaciones android o cualquier otro tipo de software, es importante dejar información del o los desarr...

1 comentario en “Matriz de Adyacencia: Representación de grafos en Java”

  1. Giovanni dice:

    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

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

*

Comparte lo que sabes

Categorias

Últimas entradas

Java ha ido evolucionando a pasos agigantados en los últimos años gracias al pedido de su comunidad global de programado...

pixilart no es solo una herramienta online sino una comunidad de diseñadores a quienes les encanta el arte hecha con...

Repl.it es un proyecto de tres jóvenes emprendedores (Amjad, Haya, Maso), es un compilador en linea el cual te permite p...

Song Maker es el nuevo experimento de Google Chrome Music Lab que permite al usuario crear música desde el navegador a t...

Android Bolivia

MAUS