Aplicaciones, ventajas y desventajas de Graph

Graph es una estructura de datos no lineal que contiene Nodes (vértices) y bordes. Un gráfico es una colección de un conjunto de vértices y aristas (formado al conectar dos vértices). Un gráfico se define como G = {V, E} donde V es el conjunto de vértices y E es el conjunto de aristas.

Representación gráfica :

El gráfico se puede representar de las siguientes maneras:

1. Representación de conjunto: La representación de conjunto de un gráfico involucra dos conjuntos: Conjunto de vértices V = {V ₁ , V ₂ , V ₃ , V ₄ } y conjunto de aristas E = {{V ₁ , V ₂ }, {V ₂ , V ₃ }, {V ₃ , V ₄ }, {V ₄ , V ₁ }} . Esta representación es eficiente para la memoria pero no permite bordes paralelos.
2. Representación Secuencial: Esta representación de un gráfico se puede representar mediante arrays: Array de Adyacencia, Array de Incidencia y Array de Camino.
   • Array de Adyacencia: Esta array incluye información sobre los Nodes adyacentes. Aquí, a _ij = 1 si hay un borde de V _i a V _j de lo contrario 0 . Es una array de orden V×V .
   • Array de Incidencia: Esta array incluye información sobre la incidencia de aristas en los Nodes. Aquí, aij = 1 si la j – ^ésima arista Ej incide sobre el ^i- ésimo vértice Vi _{, de} lo contrario 0 _. Es una array de orden V×E.
   • Path Matrix: Esta array incluye información sobre el camino simple entre dos vértices. Aquí, P _ij = 1 si hay un camino de V _i a V _j de lo contrario 0 . También se denomina array de accesibilidad del gráfico   G.
3. Representación vinculada: esta representación brinda información sobre los Nodes a los que está conectado un Node específico, es decir, listas de adyacencia. Esta representación proporciona las listas de adyacencia de los vértices con la ayuda de arrays y listas enlazadas. En las listas de adyacencia, los vértices que están conectados con el vértice específico se organizan en forma de listas que están conectadas a ese vértice.

Aplicaciones en tiempo real de Graph:

• Los gráficos se utilizan para representar el flujo de control en las computadoras.
• Los gráficos se utilizan en sitios de redes sociales donde los usuarios actúan como Nodes y la conexión entre ellos actúa como bordes.
• En un sistema operativo, los gráficos se utilizan como gráficos de asignación de recursos.
• Los gráficos se utilizan en los mapas de Google para encontrar la ruta más corta.
• Los gráficos también se utilizan en el sistema de las aerolíneas para una optimización eficaz de las rutas. 
• En los diagramas de transición de estado, el gráfico se utiliza para representar sus estados y su transición.
• En el transporte, las gráficas se utilizan para encontrar el camino más corto.
• En los circuitos, los gráficos se pueden usar para representar los puntos del circuito como Nodes y los cables como bordes.
• Los gráficos se utilizan para resolver acertijos con una sola solución, como los laberintos.
• Los gráficos se utilizan en redes informáticas para aplicaciones punto a punto (P2P).
• Los gráficos básicamente en forma de DAG (gráfico acíclico dirigido) se utilizan como alternativa a blockchain para criptomonedas. Por ejemplo, cripto como IOTA, Nano se basan principalmente en DAG.

Ventajas del gráfico:

• Mediante el uso de gráficos, podemos encontrar fácilmente la ruta más corta, los vecinos de los Nodes y muchos más.
• Los gráficos se utilizan para implementar algoritmos como DFS y BFS.
• Se utiliza para encontrar el árbol de expansión mínimo que tiene muchas aplicaciones prácticas.
• Ayuda a organizar los datos.
• Por su estructura no lineal, ayuda en la comprensión de problemas complejos y su visualización.

Desventajas de Graph:

• Los gráficos usan muchos punteros que pueden ser complejos de manejar.
• Puede tener una gran complejidad de memoria.
• Si el gráfico se representa con una array de adyacencia, no permite bordes paralelos y la multiplicación del gráfico también es difícil.