java graph tutorial how implement graph data structure
Este completo tutorial de Java Graph explica en detalle la estructura de datos de Graph. Incluye cómo crear, implementar, representar y atravesar gráficos en Java:
Una estructura de datos gráfica representa principalmente una red que conecta varios puntos. Estos puntos se denominan vértices y los vínculos que conectan estos vértices se denominan 'Bordes'. Entonces, una gráfica g se define como un conjunto de vértices V y aristas E que conectan estos vértices.
Los gráficos se utilizan principalmente para representar diversas redes como redes informáticas, redes sociales, etc. También se pueden utilizar para representar diversas dependencias en software o arquitecturas. Estos gráficos de dependencia son muy útiles para analizar el software y, en ocasiones, también para depurarlo.
=> Consulte TODOS los tutoriales de Java aquí.
Lo que vas a aprender:
- Estructura de datos de Java Graph
- ¿Cómo crear un gráfico?
- Implementación de gráficos en Java
- Biblioteca de gráficos de Java
- Conclusión
Estructura de datos de Java Graph
A continuación se muestra un gráfico que tiene cinco vértices {A, B, C, D, E} y aristas dadas por {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Como los bordes no muestran ninguna dirección, este gráfico se conoce como 'gráfico no dirigido'.
Aparte del gráfico no dirigido que se muestra arriba, existen varias variantes del gráfico en Java.
Analicemos estas variantes en detalle.
Diferentes variantes de gráfico
Las siguientes son algunas de las variantes del gráfico.
# 1) Gráfico dirigido
Un gráfico o dígrafo dirigido es una estructura de datos de gráfico en la que los bordes tienen una dirección específica. Se originan en un vértice y culminan en otro vértice.
El siguiente diagrama muestra el ejemplo de gráfico dirigido.
En el diagrama anterior, hay una arista desde el vértice A hasta el vértice B. Pero tenga en cuenta que A a B no es lo mismo que B a A como en un gráfico no dirigido a menos que haya una arista especificada de B a A.
Un gráfico dirigido es cíclico si hay al menos un camino que tiene su primer y último vértice igual. En el diagrama anterior, una ruta A-> B-> C-> D-> E-> A forma un ciclo dirigido o gráfico cíclico.
Por el contrario, un gráfico acíclico dirigido es un gráfico en el que no hay un ciclo dirigido, es decir, no hay una ruta que forme un ciclo.
# 2) Gráfico ponderado
En un gráfico ponderado, un pesoestá asociado con cada borde del gráfico. El peso normalmente indica la distancia entre los dos vértices. El siguiente diagrama muestra el gráfico ponderado. Como no se muestran direcciones, este es el gráfico no dirigido.
Tenga en cuenta que un gráfico ponderado puede estar dirigido o no dirigido.
¿Cómo crear un gráfico?
Java no proporciona una implementación completa de la estructura de datos del gráfico. Sin embargo, podemos representar el gráfico mediante programación utilizando Colecciones en Java. También podemos implementar un gráfico usando matrices dinámicas como vectores.
Por lo general, implementamos gráficos en Java usando la colección HashMap. Los elementos HashMap tienen la forma de pares clave-valor. Podemos representar la lista de adyacencia del gráfico en un HashMap.
Una forma más común de crear un gráfico es utilizando una de las representaciones de gráficos como matriz de adyacencia o lista de adyacencia. Discutiremos estas representaciones a continuación y luego implementaremos el gráfico en Java usando la lista de adyacencia para la cual usaremos ArrayList.
Representación gráfica en Java
Representación gráfica significa el enfoque o técnica mediante la cual los datos gráficos se almacenan en la memoria de la computadora.
Tenemos dos representaciones principales de gráficos como se muestra a continuación.
Matriz de adyacencia
La matriz de adyacencia es una representación lineal de gráficos. Esta matriz almacena el mapeo de vértices y aristas del gráfico. En la matriz de adyacencia, los vértices del gráfico representan filas y columnas. Esto significa que si el gráfico tiene N vértices, entonces la matriz de adyacencia tendrá un tamaño NxN.
Si V es un conjunto de vértices del gráfico, entonces la intersección Mijen la lista de adyacencia = 1 significa que existe una arista entre los vértices i y j.
Para comprender mejor este concepto con claridad, preparemos una matriz de adyacencia para un gráfico no dirigido.
Como se ve en el diagrama anterior, vemos que para el vértice A, las intersecciones AB y AE se establecen en 1 ya que hay un borde de A a B y A a E. De manera similar, la intersección BA se establece en 1, ya que esta es una gráfico y AB = BA. De manera similar, hemos establecido todas las demás intersecciones para las que hay una arista en 1.
En caso de que la gráfica esté dirigida, la intersección Mijse establecerá en 1 solo si hay un borde libre dirigido de Vi a Vj.
Esto se muestra en la siguiente ilustración.
Como podemos ver en el diagrama anterior, hay una arista de A a B. Por lo tanto, la intersección AB se establece en 1 pero la intersección BA se establece en 0. Esto se debe a que no hay una arista dirigida de B a A.
Considere los vértices E y D. Vemos que hay bordes de E a D así como de D a E. Por lo tanto, hemos establecido ambas intersecciones en 1 en la Matriz de adyacencia.
Ahora pasamos a los gráficos ponderados. Como sabemos para el gráfico ponderado, un número entero también conocido como peso está asociado con cada borde. Representamos este peso en la Matriz de adyacencia para el borde que existe. Este peso se especifica siempre que hay un borde de un vértice a otro en lugar de '1'.
Esta representación se muestra a continuación.
cómo ejecutar un archivo .jar
Lista de adyacencia
En lugar de representar un gráfico como una matriz de adyacencia que es de naturaleza secuencial, también podemos utilizar la representación vinculada. Esta representación vinculada se conoce como lista de adyacencia. Una lista de adyacencia no es más que una lista vinculada y cada nodo de la lista representa un vértice.
La presencia de un borde entre dos vértices se indica mediante un puntero desde el primer vértice al segundo. Esta lista de adyacencia se mantiene para cada vértice del gráfico.
Cuando hemos atravesado todos los nodos adyacentes para un nodo en particular, almacenamos NULL en el siguiente campo de puntero del último nodo de la lista de adyacencia.
Ahora usaremos los gráficos anteriores que usamos para representar la matriz de adyacencia para demostrar la lista de adyacencia.
La figura anterior muestra la lista de adyacencia para el gráfico no dirigido. Vemos que cada vértice o nodo tiene su lista de adyacencia.
En el caso del gráfico no dirigido, la longitud total de las listas de adyacencia suele ser el doble del número de aristas. En el gráfico anterior, el número total de bordes es 6 y el total o la suma de la longitud de toda la lista de adyacencia es 12.
Ahora, preparemos una lista de adyacencia para el gráfico dirigido.
Como se ve en la figura anterior, en el gráfico dirigido la longitud total de las listas de adyacencia del gráfico es igual al número de bordes en el gráfico. En el gráfico anterior, hay 9 aristas y la suma de las longitudes de las listas de adyacencia para este gráfico = 9.
Ahora consideremos el siguiente gráfico dirigido ponderado. Tenga en cuenta que cada borde del gráfico ponderado tiene un peso asociado. Entonces, cuando representamos este gráfico con la lista de adyacencia, tenemos que agregar un nuevo campo a cada nodo de la lista que denotará el peso del borde.
La lista de adyacencia para el gráfico ponderado se muestra a continuación.
El diagrama anterior muestra el gráfico ponderado y su lista de adyacencia. Tenga en cuenta que hay un nuevo espacio en la lista de adyacencia que denota el peso de cada nodo.
Implementación de gráficos en Java
El siguiente programa muestra la implementación de un gráfico en Java. Aquí hemos utilizado la lista de adyacencia para representar el gráfico.
|_+_|Producción:
Graph Traversal Java
Para realizar una acción significativa, como buscar la presencia de datos, necesitamos recorrer el gráfico de modo que cada vértice y el borde del gráfico se visiten al menos una vez. Esto se hace usando algoritmos de gráficos que no son más que un conjunto de instrucciones que nos ayudan a recorrer el gráfico.
Hay dos algoritmos compatibles para recorrer el gráfico en Java .
- Traversal en profundidad primero
- Travesía primero en anchura
Recorrido en profundidad primero
La búsqueda en profundidad (DFS) es una técnica que se utiliza para recorrer un árbol o un gráfico. La técnica DFS comienza con un nodo raíz y luego atraviesa los nodos adyacentes del nodo raíz profundizando en el gráfico. En la técnica DFS, los nodos se atraviesan en profundidad hasta que no hay más niños para explorar.
Una vez que llegamos al nodo hoja (no más nodos secundarios), el DFS retrocede y comienza con otros nodos y realiza el recorrido de manera similar. La técnica DFS utiliza una estructura de datos de pila para almacenar los nodos que se atraviesan.
A continuación se muestra el algoritmo para la técnica DFS.
Algoritmo
Paso 1: comience con el nodo raíz e insértelo en la pila
Paso 2: saque el elemento de la pila e insértelo en la lista 'visitados'
Paso 3: Para el nodo marcado como 'visitado' (o en la lista de visitados), agregue los nodos adyacentes de este nodo que aún no están marcados como visitados, a la pila.
Paso 4: Repita los pasos 2 y 3 hasta que la pila esté vacía.
Ilustración de la técnica DFS
Ahora ilustraremos la técnica DFS usando un ejemplo apropiado de gráfico.
A continuación se muestra un gráfico de ejemplo. Mantenemos una pila para almacenar los nodos explorados y una lista para almacenar los nodos visitados.
Comenzaremos con A, lo marcaremos como visitado y lo agregaremos a la lista de visitados. Luego, consideraremos todos los nodos adyacentes de A y los colocaremos en la pila como se muestra a continuación.
A continuación, sacamos un nodo de la pila, es decir, B y lo marcamos como visitado. Luego lo agregamos a la lista 'visitados'. Esto se representa a continuación.
Ahora consideramos los nodos adyacentes de B que son A y C. De este A ya se ha visitado. Entonces lo ignoramos. A continuación, sacamos C de la pila. Marque C como visitado. El nodo adyacente de C, es decir, E se agrega a la pila.
A continuación, sacamos el siguiente nodo E de la pila y lo marcamos como visitado. El nodo adyacente del nodo E es el C que ya se ha visitado. Entonces lo ignoramos.
Ahora solo el nodo D permanece en la pila. Así que lo marcamos como visitado. Su nodo adyacente es A que ya está visitado. Entonces no lo agregamos a la pila.
En este punto, la pila está vacía. Esto significa que hemos completado el recorrido de profundidad primero para el gráfico dado.
La lista de visitas proporciona la secuencia final de recorrido utilizando la técnica de profundidad primero. La secuencia final de DFS para el gráfico anterior es A-> B-> C-> E-> D.
Implementación de DFS
|_+_|Producción:
Aplicaciones de DFS
# 1) Detecta un ciclo en un gráfico: DFS facilita la detección de un ciclo en un gráfico cuando podemos retroceder hasta un borde.
# 2) Búsqueda de caminos: Como ya hemos visto en la ilustración DFS, dados dos vértices cualesquiera podemos encontrar la ruta entre estos dos vértices.
# 3) Mínimo árbol de expansión y camino más corto: Si ejecutamos la técnica DFS en el gráfico no ponderado, nos da el árbol de expansión mínimo y la ruta corta.
# 4) Clasificación topológica: La clasificación topológica se utiliza cuando tenemos que programar los trabajos. Tenemos dependencias entre varios trabajos. También podemos usar la clasificación topológica para resolver dependencias entre enlazadores, programadores de instrucciones, serialización de datos, etc.
Travesía primero en anchura
La técnica Breadth-first (BFS) utiliza una cola para almacenar los nodos del gráfico. A diferencia de la técnica DFS, en BFS recorremos el gráfico a lo ancho. Esto significa que recorremos el nivel del gráfico en forma inteligente. Cuando exploramos todos los vértices o nodos en un nivel, pasamos al siguiente nivel.
A continuación se muestra un algoritmo para la técnica transversal de amplitud primero .
Algoritmo
Veamos el algoritmo de la técnica BFS.
Dada una gráfica G para la que necesitamos realizar la técnica BFS.
- Paso 1: Comience con el nodo raíz e insértelo en la cola.
- Paso 2: Repita los pasos 3 y 4 para todos los nodos del gráfico.
- Paso 3: Elimine el nodo raíz de la cola y agréguelo a la lista de Visitas.
- Paso 4: Ahora agregue todos los nodos adyacentes del nodo raíz a la cola y repita los pasos 2 a 4 para cada nodo. [FIN DEL BUCLE]
- Paso 6: SALIDA
Ilustración de BFS
Ilustremos la técnica BFS utilizando un gráfico de ejemplo que se muestra a continuación. Tenga en cuenta que hemos mantenido una lista denominada 'Visitados' y una cola. Usamos el mismo gráfico que usamos en el ejemplo de DFS por motivos de claridad.
Primero, comenzamos con la raíz, es decir, el nodo A y lo agregamos a la lista de visitas. Todos los nodos adyacentes del nodo A, es decir, B, C y D se agregan a la cola.
A continuación, eliminamos el nodo B de la cola. Lo añadimos a la lista de Visitas y lo marcamos como visitado. A continuación, exploramos los nodos adyacentes de B en la cola (C ya está en la cola). Otro nodo adyacente A ya está visitado, por lo que lo ignoramos.
A continuación, eliminamos el nodo C de la cola y lo marcamos como visitado. Agregamos C a la lista de visitados y su nodo adyacente E se agrega a la cola.
A continuación, eliminamos D de la cola y lo marcamos como visitado. El nodo adyacente A del nodo D ya está visitado, así que lo ignoramos.
Entonces ahora solo el nodo E está en la cola. Lo marcamos como visitado y lo agregamos a la lista de visitados. El nodo adyacente de E es C que ya está visitado. Así que ignóralo.
En este punto, la cola está vacía y la lista visitada tiene la secuencia que obtuvimos como resultado del recorrido BFS. La secuencia es, A-> B-> C-> D-> E.
Implementación de BFS
El siguiente programa Java muestra la implementación de la técnica BFS.
|_+_|Producción:
Aplicaciones de BFS Traversal
# 1) Recolección de basura: Uno de los algoritmos utilizados por la técnica de recolección de basura para copiar la recolección de basura es el 'algoritmo de Cheney'. Este algoritmo utiliza una técnica transversal de amplitud primero.
# 2) Difusión en redes: La transmisión de paquetes de un punto a otro en una red se realiza mediante la técnica BFS.
# 3) Navegación GPS: Podemos usar la técnica BFS para encontrar nodos adyacentes mientras navegamos usando GPS.
# 4) Sitios web de redes sociales: La técnica BFS también se utiliza en sitios web de redes sociales para encontrar la red de personas que rodean a una persona en particular.
# 5) Ruta más corta y árbol de expansión mínimo en un gráfico no ponderado: En el gráfico no ponderado, la técnica BFS se puede utilizar para encontrar un árbol de expansión mínimo y la ruta más corta entre los nodos.
Biblioteca de gráficos de Java
Java no obliga a los programadores a implementar siempre los gráficos en el programa. Java proporciona muchas bibliotecas listas que se pueden usar directamente para hacer uso de gráficos en el programa. Estas bibliotecas tienen toda la funcionalidad API de gráficos necesaria para hacer un uso completo del gráfico y sus diversas características.
A continuación se muestra una breve introducción a algunas de las bibliotecas de gráficos en Java.
# 1) Google Guayaba: Google Guava proporciona una biblioteca rica que admite gráficos y algoritmos, incluidos gráficos simples, redes, gráficos de valor, etc.
# 2) Apache Commons: Apache Commons es un proyecto de Apache que proporciona componentes de estructura de datos Graph y API que tienen algoritmos que operan en esta estructura de datos gráfica. Estos componentes son reutilizables.
# 3) JGraphT: JGraphT es una de las bibliotecas de gráficos de Java más utilizadas. Proporciona una funcionalidad de estructura de datos de gráficos que contiene gráficos simples, gráficos dirigidos, gráficos ponderados, etc., así como algoritmos y API que funcionan en la estructura de datos de gráficos.
# 4) FuenteForge JUNG: JUNG significa 'Java Universal Network / Graph' y es un marco de Java. JUNG proporciona un lenguaje extensible para el análisis, visualización y modelado de los datos que queremos que se representen como un gráfico.
JUNG también proporciona varios algoritmos y rutinas para descomposición, agrupación, optimización, etc.
Preguntas frecuentes
P # 1) ¿Qué es un gráfico en Java?
preguntas y respuestas de la entrevista html css
Responder: Una estructura de datos de gráfico almacena principalmente datos conectados, por ejemplo, una red de personas o una red de ciudades. Una estructura de datos de gráfico generalmente consta de nodos o puntos llamados vértices. Cada vértice está conectado a otro vértice mediante enlaces llamados aristas.
Q #2) ¿Cuáles son los tipos de gráficos?
Responder: A continuación se enumeran diferentes tipos de gráficos.
- Gráfico de líneas: Se utiliza un gráfico de líneas para trazar los cambios en una propiedad particular en relación con el tiempo.
- Gráfico de barras: Los gráficos de barras comparan valores numéricos de entidades como la población en varias ciudades, porcentajes de alfabetización en todo el país, etc.
Además de estos tipos principales, también tenemos otros tipos como pictogramas, histogramas, gráficos de áreas, gráficos de dispersión, etc.
P # 3) ¿Qué es un gráfico conectado?
Responder: Un gráfico conectado es un gráfico en el que cada vértice está conectado a otro vértice. Por lo tanto, en el gráfico conectado, podemos llegar a cada vértice desde cualquier otro vértice.
Q #4) ¿Cuáles son las aplicaciones del gráfico?
Responder: Los gráficos se utilizan en una variedad de aplicaciones. El gráfico se puede utilizar para representar una red compleja. Los gráficos también se utilizan en aplicaciones de redes sociales para indicar la red de personas, así como para aplicaciones como encontrar personas o conexiones adyacentes.
Los gráficos se utilizan para denotar el flujo de la computación en la informática.
Q #5) ¿Cómo se almacena un gráfico?
Respuesta: Hay tres formas de almacenar un gráfico en la memoria:
#1) Podemos almacenar nodos o vértices como objetos y aristas como punteros.
#2) También podemos almacenar gráficos como matriz de adyacencia cuyas filas y columnas son iguales al número de vértices. La intersección de cada fila y columna denota la presencia o ausencia de un borde. En el gráfico no ponderado, la presencia de un borde se indica con 1 mientras que en el gráfico ponderado se reemplaza por el peso del borde.
#3) El último enfoque para almacenar un gráfico es utilizar una lista de adyacencia de bordes entre los vértices o nodos del gráfico. Cada nodo o vértice tiene su lista de adyacencia.
Conclusión
En este tutorial, hemos discutido los gráficos en Java en detalle. Exploramos los diversos tipos de gráficos, implementación de gráficos y técnicas de recorrido. Los gráficos se pueden utilizar para encontrar el camino más corto entre nodos.
En nuestros próximos tutoriales, continuaremos explorando gráficos discutiendo algunas formas de encontrar el camino más corto.
=> Tenga cuidado con la serie de capacitación simple de Java aquí.
Lectura recomendada
- Tutorial de reflexión de Java con ejemplos
- Cómo implementar el algoritmo de Dijkstra en Java
- Tutorial de Java SWING: contenedor, componentes y manejo de eventos
- Tutorial de JAVA para principiantes: más de 100 tutoriales prácticos en vídeo de Java
- TreeMap en Java - Tutorial con ejemplos de Java TreeMap
- Modificadores de acceso en Java: tutorial con ejemplos
- Tutorial Java String con String Buffer y String Builder
- Tutorial del método Java String contains () con ejemplos