Gráficos en estructura de datos: tipos, almacenamiento y recorrido

Una estructura de datos es una forma eficiente de organizar datos en la ciencia de datos para que se pueda acceder fácilmente a los datos y utilizarlos de manera efectiva. Hay muchos tipos de bases de datos, pero en este artículo se explica por qué los gráficos juegan un papel vital en la gestión de datos.

Alerta de spoiler: utiliza gráficos en la estructura de datos todos los días para obtener la mejor ruta a su oficina, para obtener sugerencias para su almuerzo, película y para optimizar su próxima ruta de vuelo. ¡Suena interesante! Veamos las propiedades del gráfico y su aplicación.

Primero, veamos qué es un gráfico. Es una representación de datos en una estructura no lineal que consta de nodos (o vértices) y bordes (o caminos).

Un gráfico en la estructura de datos se puede denominar como una estructura de datos que consta de datos que se almacenan entre muchos grupos de bordes (caminos) y vértices (nodos), que están interconectados. La estructura de datos del gráfico (N, E) está estructurada con una colección de nodos y bordes. Tanto los nodos como los vértices deben ser finitos.

En la representación gráfica anterior, el conjunto de nodos es N = {0,1,2,3,4,5,6} y el conjunto de aristas es

G={01,12,23,34,45,05,03}

Ahora estudiemos los tipos de gráficos.

Leer: Las 10 mejores técnicas de visualización de datos

Tipos de gráficos

1. Gráfico ponderado

Gráficos cuyas aristas o caminos tienen valores. Todos los valores que se ven asociados a los bordes se denominan pesos. El valor de los bordes puede representar peso/costo/longitud.

Los valores o pesos también pueden representar:

• Distancia recorrida entre dos puntos- Ej: Para buscar el camino más corto a la oficina, la distancia entre dos estaciones de trabajo en una red de oficinas.
• Velocidad del paquete de datos en una red o ancho de banda.

2. Gráfico no ponderado

Donde no hay valor o peso asociado con el borde. De forma predeterminada, todas las gráficas no están ponderadas a menos que haya un valor asociado.

3. Gráfico no dirigido

Donde un conjunto de objetos están conectados y todos los bordes son bidireccionales. La siguiente imagen muestra el gráfico no dirigido,

Es como la asociatividad de dos usuarios de Facebook después de conectarse como amigo. Ambos usuarios pueden referirse y compartir fotos, comentar entre ellos.

4. Gráfico dirigido

También llamado dígrafo, donde un conjunto de objetos (N, E) están conectados y todos los bordes están dirigidos de un nodo a otro. La imagen de arriba muestra el gráfico dirigido.

Pago: Proyectos de visualización de datos que puede replicar

Almacenamiento de gráfico

Cada método de almacenamiento tiene sus pros y sus contras, y el método de almacenamiento correcto se elige en función de la complejidad. Las dos estructuras de datos más utilizadas para almacenar gráficos son:

1. Lista de adyacencia

Aquí los nodos se almacenan como un índice de la matriz de una dimensión, seguidos de los bordes que se almacenan como una lista.

2. Matriz de adyacencia

Aquí los nodos se representan como el índice de una matriz bidimensional, seguidos de los bordes representados como valores distintos de cero de una matriz adyacente.

Tanto las filas como las columnas muestran Nodos; toda la matriz se llena con "0" o "1", lo que representa verdadero o falso. Cero representa que no hay camino y 1 representa un camino.

Gráfico transversal

El recorrido de gráficos es un método utilizado para buscar nodos en un gráfico. El recorrido del gráfico se utiliza para decidir el orden utilizado para la disposición de los nodos. También busca aristas sin hacer un bucle, lo que significa que se pueden buscar todos los nodos y aristas sin crear un bucle.

Hay dos estructuras transversales de grafos.

1. DFS (búsqueda primero en profundidad): método de búsqueda en profundidad

La búsqueda de DFS comienza desde el primer nodo y va más y más profundo, explorando hacia abajo hasta encontrar el nodo de destino. Si no se encuentra la clave objetivo, la ruta de búsqueda se cambia a la ruta que se dejó de explorar durante la búsqueda inicial y se repite el mismo procedimiento para esa rama.

El árbol de expansión se produce a partir del resultado de esta búsqueda. Este método de árbol no tiene bucles. El número total de nodos en la estructura de datos de la pila se usa para implementar el recorrido DFS.

Pasos seguidos para implementar la búsqueda DFS:

Paso 1: el tamaño de la pila debe definirse en función del número total de nodos.

Paso 2 – Seleccione el nodo inicial para transversal; necesita ser empujado a la pila visitando ese nodo.

Paso 3: ahora, visite el nodo adyacente que no se visitó antes y empújelo a la pila.

Paso 4: repita el paso 3 hasta que no haya ningún nodo adyacente que no se visite.

Paso 5: use el retroceso y un nodo cuando no haya otros nodos para visitar.

Paso 6: vacíe la pila repitiendo los pasos 3, 4 y 5.

Paso 7: cuando la pila está vacía, se forma un árbol de expansión final al eliminar los bordes no utilizados.

Las aplicaciones de DFS son:

• Resolver acertijos con una sola solución.
• Para probar si un gráfico es bipartito.
• Clasificación topológica para programar el trabajo y muchos otros.

2. BFS (búsqueda primero en amplitud): la búsqueda se implementa mediante un método de cola

Breadth-First Search navega por un gráfico en un movimiento de amplitud y se basa en la cola para saltar de un nodo a otro, después de encontrar un final en la ruta.

Pasos seguidos para implementar la búsqueda BFS,

Paso 1: en función del número de nodos, se define la cola.

Paso 2: comience desde cualquier nodo del recorrido. Visite ese nodo y agréguelo a la cola.

Paso 3: ahora verifique el nodo adyacente no visitado, que se encuentra frente a la Cola, y agréguelo a la Cola, no al inicio.

Paso 4: ahora comience a eliminar el nodo que no tiene ningún borde que deba visitarse y que no está en la cola.

Paso 5: vacíe la cola repitiendo los pasos 4 y 5.

Paso 6: elimine los bordes no utilizados y forme el árbol de expansión solo después de que la cola esté vacía.

Las aplicaciones de BFS son:

• Redes punto a punto: como en Bittorrent, se utiliza para encontrar todos los nodos adyacentes.
• Rastreadores en el motor de búsqueda.
• Sitios web de redes sociales y muchos más.

Aplicaciones del mundo real de Graph en la estructura de datos

Los gráficos se utilizan en muchas aplicaciones cotidianas, como la representación de redes (carreteras, mapeo de fibra óptica, diseño de placas de circuitos, etc.). Ej: En la red de datos de Facebook, los nodos representan al usuario, su foto o comentario, y los bordes representan fotos, comentarios sobre la foto.

El gráfico en la estructura de datos tiene amplias aplicaciones. Algunos de los más destacados son:

• API de gráficos sociales : es la forma principal en que los datos se comunican dentro y fuera de la plataforma de redes sociales de Facebook. Es una API basada en HTTP, que se utiliza para consultar datos mediante programación, cargar fotos y videos, crear nuevas historias y muchas otras tareas. Se compone de nodos, aristas y campos; para consultar, se utilizan los nodos de objetos específicos. Los bordes de un grupo de objetos sujetos a un solo objeto y campos se utilizan para obtener datos sobre cada objeto del grupo.
• API GraphQL de Yelp : es un motor de recomendaciones que se utiliza para obtener datos específicos de la plataforma de Yelp. Aquí, las órdenes se utilizan para encontrar los bordes, después de lo cual se consulta el nodo específico para obtener el resultado exacto. Esto acelera el proceso de recuperación.

En la plataforma de Yelp, los nodos representan el negocio y contienen id, nombre, is_closed y muchas otras propiedades gráficas.

• Algoritmos de optimización de ruta : se emplean para encontrar la mejor conexión que se ajuste a los criterios de velocidad, seguridad, combustible, etc. En este algoritmo se utiliza BFS. El mejor ejemplo es Google Maps Platform (Mapas, Rutas API).
• Redes de vuelo: en las redes de vuelo, esto se usa para encontrar la ruta optimizada que se ajusta a la estructura de datos del gráfico . Esto también ayuda en el modelo y optimiza los procedimientos aeroportuarios de manera eficiente.

Lea también: Beneficios de la visualización de datos

Conclusión

En este artículo, primero discutimos la definición de Graph y Graph en la estructura de datos y luego aprendimos sobre los tipos de gráficos con sus propiedades. Más tarde, aprendimos sobre los métodos comúnmente utilizados para el almacenamiento de gráficos, seguidos de importantes métodos de búsqueda de temas utilizados en Graphs, Graph Traversal. Finalmente, discutimos las aplicaciones del mundo real de la estructura de datos de grafos.

Este artículo proporcionó información sobre gráficos en la estructura de datos ; el conocimiento de esto es vital para la comprensión fundamental de las bases de datos Graph, la implementación de algoritmos de búsqueda, la programación y mucho más. Debe aprenderse del experto de la industria.

¿Por qué elegir un curso con upGrad ?

Le recomendamos que elija el Programa Executive PG en Data Science ofrecido por IIIT Bangalore alojado en upGrad porque aquí puede obtener sus consultas 1-1 con los instructores del curso. No solo se enfoca en el aprendizaje teórico, sino que le da importancia al conocimiento práctico, que es esencial para preparar a los alumnos para enfrentar proyectos del mundo real y brindarle el primer certificado NASSCOM de la India, que lo ayuda a obtener trabajos bien remunerados en Ciencia de datos.

Trabajos citados

Departamento de Matemáticas/CS – Inicio , www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/data-stru.html.

“Información matemática”. Definición de gráfico dirigido: Math Insight , mathinsight.org/definition/directed_graph.

Singh, Amritpal. "Estructura de datos de gráficos". Medio , Medio, 29 de marzo de 2020, medium.com/@singhamritpal49/graph-data-structure-49427c81b3b3.

Solo. "Las aplicaciones de la vida real de las estructuras de datos de gráficos que debe conocer". Graph Data y GraphQL API Development-Leap Graph , LEAPGRAPH.com/graph-data-structures-applications.