Tipos de gráficos en estructura de datos y aplicaciones

Introducción

Un gráfico es una estructura no lineal que comprende nodos y aristas. Puede incluir un conjunto finito o infinito de nodos sostenidos por un borde que conecta un par de nodos. Las estructuras de datos son una parte esencial de cualquier concepto de codificación; por lo tanto, tener una comprensión firme de los diferentes tipos de gráficos en las estructuras de datos puede ayudarlo a resolver problemas complejos del mundo real.

En el mundo actual, los datos son poder. Por lo tanto, organizar los datos de manera eficiente para facilitar el acceso es esencial para cualquier programador. El conocimiento de las estructuras de datos y su variedad de gráficos fortalece sus habilidades de codificación para abordar problemas del mundo real y brindar sus soluciones de manera efectiva.

Aprenda ciencia de datos para ganar ventaja sobre sus competidores

Echemos un vistazo a los diferentes tipos de gráficos que se usan comúnmente en las estructuras de datos y cómo se aplican en la vida real.

Tipos de gráficos en estructuras de datos

Una estructura de datos es un estándar práctico de almacenamiento de datos para todos los lenguajes, como la estructura de datos de gráficos de Python o la estructura de datos de gráficos de Java. Dominar todo tipo de gráficos debería ser una prioridad para cualquiera que aspire a estudiar estructuras de datos. Dado que la teoría de grafos tiene muchas aplicaciones en la vida real, se vuelven vitales en las estructuras de datos.

Los diversos tipos de gráficos en estructuras de datos se pueden enumerar a continuación:

1. Gráfico nulo

Como sugiere el nombre, el gráfico nulo está vacío; en otras palabras, es un gráfico sin bordes. Solo consta de vértices aislados en el gráfico con un conjunto de aristas vacío.

2. Gráfico finito

Si el número de aristas y nodos consiste en un número finito en un gráfico, entonces el gráfico se conoce como gráfico finito.

3. Gráfico infinito

Si uno no puede poner un número finito al número de nodos y al número de aristas en un gráfico, el gráfico se conoce como un gráfico infinito. Los gráficos infinitos son incontables, lo que significa que no puede contar la cantidad de nodos o aristas en este tipo de gráfico.

4. Gráfico simple

Se dice que un grafo es simple cuando solo hay una arista entre un par de vértices. Por lo tanto, dos nodos están conectados por un borde en un gráfico, lo que puede identificar una relación definida entre ellos.

5. Gráfico múltiple

Si un par de nodos está conectado con múltiples aristas en un gráfico, entonces el gráfico se conoce como un gráfico múltiple. Un gráfico múltiple no consta de bucles automáticos. Hay dos tipos de aristas que pueden existir en un multigrafo. Están:

• Bordes paralelos

Los bordes que corren paralelos, como dos caminos paralelos que van de un origen al mismo destino, se conocen como bordes paralelos.

• Círculo

Este es un borde cuyos vértices de origen y destino son los mismos.

Consulte nuestros programas de ciencia de datos de EE. UU.

6. Gráfico dirigido

Se dice que un grafo es dirigido si todas las aristas presentes entre dos nodos o vértices tienen una dirección definida. Un grafo dirigido también se conoce como dígrafo. Podemos determinar el nodo inicial y final mirando un gráfico dirigido. Recuerda, todas las aristas en un gráfico dirigido deben estar dirigidas para llamarse un gráfico dirigido.

7. Gráfico no dirigido

Se dice que un grafo es un grafo no dirigido si es difícil identificar el nodo inicial y final mirando sus bordes. Al igual que un gráfico dirigido, los bordes deben ser no dirigidos para que se llame un gráfico no dirigido.

8. Gráfico conectado

Un grafo conexo es un grafo en el que existe al menos un camino entre todos los nodos. En términos más simples, si comienza desde un nodo en un gráfico conectado, debería poder visitar todos los nodos presentes en el gráfico. Por lo tanto, debe haber al menos una ruta para cada nodo.

9. Gráfico desconectado

En este tipo de gráfico, no existe borde entre un par de nodos o vértices. Por lo tanto, a diferencia de los gráficos conectados, no es posible llegar a todos los nodos desde cualquier vértice. Si cualquier par de vértices no tiene un camino entre ellos, se llama un grafo desconectado.

10. Gráfico completo

Un gráfico solo se considera completo cuando existe un borde entre cada nodo, lo que significa que un borde conectará todos los vértices del gráfico. Un grafo completo en n vértices se denota como Kn , y el número de aristas en el grafo es nC2 .

11. Gráfico cíclico

Un gráfico debe tener al menos un componente cíclico para ser considerado un gráfico cíclico. Por el contrario, si el grafo no contiene ningún ciclo, se considera un grafo acíclico.

12. Gráfico regular

En un grafo regular, todos los vértices deben tener el mismo grado. El grado de un nodo se puede definir como el número de nodos conectados con él. Así, en un gráfico regular, todos los nodos deben estar conectados al mismo número de nodos.

13. Gráfico bipartito

Para que un grafo sea bipartito, debe cumplir los siguientes criterios.

• El gráfico debe dividirse en conjuntos de vértices.
• Los bordes solo deben formarse entre un grupo de nodos y el otro lado. Esta regla impide la conexión entre dos vértices del mismo conjunto de nodos.
• Los dos grupos no deben tener vértices comunes entre ellos.

Un gráfico que sigue todas las reglas anteriores debe considerarse un gráfico bipartito.

14. Gráfico etiquetado

Los bordes de los gráficos se pueden ponderar. Un peso asociado con un borde puede entenderse como el costo de viajar a través de ese borde. Estos valores pueden basarse en un parámetro fijo y pueden cambiar entre gráficos. Ahora, si todos los bordes tienen algún peso asociado con ellos, entonces ese gráfico puede denominarse gráfico etiquetado.

15. Gráfico acíclico dirigido

Un gráfico acíclico dirigido es una combinación de gráficos dirigidos y acíclicos donde los bordes dirigidos del gráfico no forman ningún tipo de ciclo. Por el contrario, un gráfico cíclico dirigido es un gráfico con aristas dirigidas que forma un ciclo.

Aplicación de gráfico en estructura de datos

La aplicación más destacada de un gráfico en informática es la representación del flujo de cálculo. Algunos otros casos usados ​​famosos de gráficos son:

1. Mapas de Google

En Google Maps, las estructuras de datos de gráficos definen y calculan el sistema de transporte. Cuando un camino se encuentra con otro camino y forma un cruce, se considera un nodo, y el camino entre dos de esos nodos se trata como un borde. Por lo tanto, Google Maps le encuentra el camino más corto y rápido a su destino utilizando la estructura de datos del gráfico.

2.Facebook

Facebook utiliza gráficos no dirigidos para identificar a un usuario y a los amigos del usuario. Cada usuario es tratado como los vértices y las conexiones que los unen como amigos son los bordes de la red. Con algoritmos basados ​​en la estructura de datos de gráficos, Facebook sugiere "personas que quizás conozcas" y muestra "amigos en común".

3. Red mundial

La World Wide Web es un ejemplo de un gráfico dirigido. También es la idea básica detrás del sistema de clasificación de Google. En el sistema World Wide Web, cada sitio web y aplicación web se trata como un nodo o vértices, y los enlaces de un sitio web a otro se consideran el borde.

4. Sistema Operativo

El sistema operativo es un caso de uso popular de gráficos de asignación de recursos que utiliza cada proceso y recurso como nodos o vértices. Los bordes ocurren entre los recursos al proceso asignado o desde el proceso solicitante a los recursos solicitados. A veces, este ciclo puede formar un bucle infinito, inicializando el interbloqueo.

5. Sistema de mapeo

Su GPS es un caso de gráficos de uso popular para ubicar restaurantes, tiendas y lugares cercanos que elija para buscar con la ayuda de esta tecnología.

6. Microsoft Excel

Los gráficos acíclicos dirigidos o DAG se utilizan en Microsoft Excel.

7. El algoritmo de Dijkstra

El algoritmo de Dijkstra utiliza la estructura de datos de gráficos para identificar el camino más corto entre dos o, en algunos casos, más de dos nodos.

8. Redes de vuelos:

La computación de redes de vuelo optimizadas es otra aplicación de la vida real de la estructura de datos de gráficos. Si considera los aeropuertos como nodos y las rutas como bordes, los datos se ajustan perfectamente a los criterios de los gráficos. Por eso, con la ayuda de varios algoritmos mejorados, se determinan las mejores rutas entre dos aeropuertos o nodos.

Estas son las diversas aplicaciones de gráficos en la estructura de datos , que se utilizan en todo el mundo en diversas aplicaciones y sistemas para organizar y mantener su buen funcionamiento.

Comience su viaje como científico de datos

Si desea convertirse en un científico de datos y manejar los datos con tacto utilizando los diversos gráficos que aprendimos, consulte una amplia gama de cursos de ciencia de datos en upGrad. Uno de los cursos más populares es el curso PG-IIITB sobre ciencia de datos , ¡un excelente curso para principiantes y futuros científicos de datos para comenzar!

Esto es lo que ofrece el curso.

• Apoyo profesional de 360 ​​grados de expertos y mentores de la industria
• Experiencia práctica con proyectos industriales y estudios de casos detallados para medir el progreso regular
• Conexión en red con expertos en ciencia de datos en todos los sectores, a nivel mundial

También puede consultar todos los otros cursos de upGrad en Data Science .