Estructuras de datos 101: Gráficos: una introducción visual para principiantes

Conozca las estructuras de datos que usa todos los días

? ¡Bienvenido! Comencemos con un contexto vital. Déjame preguntarte algo:

✅ ¿Utiliza la búsqueda de Google?

✅ ¿Utiliza Google Maps?

✅ ¿Utiliza sitios de redes sociales?

Si su respuesta es “sí” a cualquiera de estas preguntas, entonces definitivamente ha usado gráficos y ni siquiera lo sabía. ¿Sorprendido? ? ¡ Yo también lo estaba! Este artículo le dará una introducción visual al mundo de los gráficos, su propósito, elementos y tipos.

Estas estructuras de datos realmente me llamaron la atención debido a sus increíbles capacidades. Son tan poderosos que ni siquiera imaginará cuán diversas pueden ser sus aplicaciones en el mundo real. ¡Vamos a empezar! ?

? Aplicaciones del mundo real: ¡comienza la magia!

Los gráficos se utilizan en diversas industrias y campos:

  • Los sistemas GPS y Google Maps utilizan gráficos para encontrar el camino más corto de un destino a otro.
  • Las redes sociales usan gráficos para representar conexiones entre usuarios.
  • El algoritmo de búsqueda de Google utiliza gráficos para determinar la relevancia de los resultados de búsqueda.
  • La investigación de operaciones es un campo que utiliza gráficos para encontrar la ruta óptima para reducir el costo de transporte y entrega de bienes y servicios.
  • Incluso la química usa gráficospara representar moléculas !!! ❤️

Sus aplicaciones son asombrosas, ¿verdad?

¡Comencemos nuestro viaje por este mundo! ?

? ¡Conoce Graphs!

Ahora que tiene algo de contexto, comencemos hablando de su propósito y elementos principales.

Los gráficos se utilizan para representar, encontrar, analizar y optimizar conexiones entre elementos (casas, aeropuertos, ubicaciones, usuarios, artículos, etc.).

Este es un ejemplo de cómo se ve un gráfico:

? Bloques de construcción

Estoy seguro de que ha notado dos elementos principales en el diagrama de arriba: círculos y líneas gruesas que los conectan. Se denominan, respectivamente, Nodos y Aristas .

¡Veámoslos con más detalle! ?

  • Nodos: son los elementos que crean la red. Podrían representar casas, ubicaciones, aeropuertos, puertos, paradas de autobús, edificios, usuarios, básicamente cualquier cosa que puedas representar como conectado a otros elementos similares en una red.
  • Bordes: son conexiones entre los nodos. Podrían representar calles, vuelos, rutas de autobús, una conexión entre dos usuarios en una red social o cualquier cosa que pudiera representar una conexión entre los nodos en el contexto con el que está trabajando.

? ¿Qué sucede si no hay conexión?

Si dos nodos no están conectados por un borde, eso significa que no hay una conexión directa entre ellos. ¡Pero que no cunda el pánico! ? Es posible que aún pueda pasar de un nodo a otro siguiendo una secuencia de bordes, similar a conducir por varias calles para llegar a su destino final. ?️ ? ?

Por ejemplo, en el diagrama a continuación, aunque no hay una conexión directa ( borde ) entre el nodo púrpura (izquierda) y el nodo amarillo (derecha), puede pasar del nodo púrpura al nodo naranja, al nodo rosa, al nodo verde, y finalmente llegar al nodo amarillo. ?

Este es un aspecto clave de los gráficos, que puede buscar el elemento que está buscando siguiendo las rutas disponibles.

? Notación y terminología

Es muy importante aprender el "lenguaje" formal para trabajar con gráficos:

  • |V|= Número total de vértices ( nodos ) en el gráfico.
  • |E|= Número total de conexiones ( bordes ) en el gráfico.

En el siguiente ejemplo, |V| = 6debido a que hay seis nodos (círculos) y

|E| = 7porque hay siete aristas (líneas).

? Tipos de gráficos

Los gráficos se clasifican en función de las características de sus bordes (conexiones). ¡Echémosle un vistazo en detalle! ?

1️⃣ Gráficos dirigidos

En los gráficos dirigidos, los bordes tienen una dirección. Van de un nodo a otro y no hay forma de volver al nodo inicial a través de ese borde.

Como puede ver en el diagrama a continuación, los bordes (conexiones) ahora tienen flechas que apuntan a una dirección específica. Piense en estos bordes como calles de un solo sentido. Puede ir en una dirección y llegar a su destino, pero no puede regresar por esa misma calle, por lo que debe buscar un camino alternativo.

? Por ejemplo, si creamos un gráfico para un servicio de entrega de pizzas, que representa una ciudad, dos casas (nodos) pueden estar conectadas por una calle de un solo sentido (borde). Podrías ir de la casa A a la casa B por esta calle, pero no podías regresar, por lo que tendrías que tomar un camino alternativo.

? Nota: En un gráfico dirigido, es posible que no pueda regresar a su ubicación inicial si no hay un camino con las direcciones adecuadas. ? En el diagrama a continuación, puede ver que puede pasar con éxito del nodo púrpura al nodo verde, pero observe que no hay forma de regresar del nodo verde al nodo púrpura porque los bordes son “calles de un solo sentido. "

2️⃣ Gráficos no dirigidos

En este tipo de gráfico, los bordes no están dirigidos (no tienen una dirección específica). Piense en los bordes no dirigidos como calles de dos sentidos. Puede ir de un nodo a otro y volver por ese mismo "camino".

? Nota: Cuando vea un diagrama de un gráfico donde los bordes no tienen flechas apuntando en una dirección específica, puede asumir que el gráfico no está dirigido.

? Para nuestro servicio de reparto de pizzas, esto significaría que la moto repartidora puede ir del origen al destino por la misma calle o camino (¡Para su alivio! ?).

En el gráfico a continuación, puede pasar del nodo morado al nodo verde y regresar por el mismo camino , para no llegar a un punto sin retorno. ?

? ¿Pesos? - ¡Sí, pesos!

1️⃣ Gráficos ponderados

En los gráficos ponderados, cada borde tiene un valor asociado (llamado peso) . Este valor se utiliza para representar una cierta relación cuantificable entre los nodos que conectan.

Por ejemplo, las ponderaciones pueden representar la distancia, el tiempo, la cantidad de conexiones compartidas entre dos usuarios en una red social o cualquier cosa que pueda usarse para describir la conexión entre nodos en el contexto con el que está trabajando.

El algoritmo de Dijkstra utiliza estos pesos para optimizar las rutas al encontrar las rutas más cortas o menos costosas entre los nodos de una red. (¡Estén atentos para un artículo sobre el algoritmo de Dijkstra! ?).

2️⃣ Gráficos no ponderados

Por el contrario, los gráficos no ponderados no tienen pesos asociados con sus bordes. Un ejemplo de este tipo de gráfico se puede encontrar en las redes sociales, donde los bordes representan la conexión entre dos usuarios. La conexión no se puede cuantificar. Por tanto, el borde no tiene peso.

? Nota: Es posible que haya notado que, hasta ahora, nuestros gráficos solo tienen un borde que conecta cada par de nodos. Es natural preguntar si podría haber más de un borde entre un par de nodos. De hecho, ¡esto es posible con M ultígrafos! T Hey puede tener múltiples aristas que conectan el mismo par de nodos.

? ¡Número de bordes! - Un factor importante

Es muy importante saber si un gráfico tiene muchos o pocos bordes porque este es un factor crucial para decidir cómo representará esta estructura de datos en su código. ¡Veamos los diferentes tipos! ?

1️⃣ Gráficos densos

Los gráficos densos tienen muchos bordes. ¡Pero espera! ⚠️ Sé lo que debes estar pensando, ¿cómo puedes determinar qué califica como “muchos bordes”? Esto es demasiado subjetivo, ¿verdad? ? Estoy de acuerdo contigo, así que cuantifiquémoslo un poco:

? Encontremos el número máximo de aristas en una gráfica dirigida. Si hay |V|nodos en un gráfico dirigido (en el ejemplo siguiente, seis nodos), eso significa que cada nodo puede tener hasta |v|conexiones (en el ejemplo siguiente, seis conexiones).

¿Por qué? Porque cada nodo podría potencialmente conectarse con todos los demás nodos y consigo mismo (consulte el "bucle" a continuación) . Por tanto, el número máximo de aristas que puede tener el gráfico es|V|*|V| , que es el número total de nodos multiplicado por el número máximo de conexiones que puede tener cada nodo.

Cuando el número de bordes en el gráfico está cerca del número máximo de bordes, el gráfico es denso. ?

? Nota: Los “bucles” ocurren cuando un nodo tiene un borde que lo conecta consigo mismo. Extraño e interesante, ¿verdad? ?

2️⃣ Gráficos dispersos

Los gráficos dispersos tienen pocos bordes. Como puede ver en el diagrama a continuación, no hay muchas conexiones entre los nodos.

Cuando el número de bordes en el gráfico es significativamente menor que el número máximo de bordes, el gráfico es escaso. ?

⭕️ ¡Conoce Cycles!

Ahora veamos un concepto vital para entender gráficas, ciclos.

Probablemente haya notado que si sigue una secuencia de conexiones en un gráfico, puede encontrar una ruta que lo lleve de regreso al mismo nodo. Esto es como "caminar en círculos", exactamente como si estuviera conduciendo por su ciudad y tomara un camino que podría llevarlo de regreso a su ubicación inicial.

En los gráficos, estos caminos "circulares" se denominan "ciclos". Son rutas válidas que comienzan y terminan en el mismo nodo. Por ejemplo, en el diagrama a continuación, puede ver que si comienza en cualquier nodo, puede regresar a ese mismo nodo siguiendo los bordes.

Los ciclos no siempre están “aislados” porque pueden formar parte de un gráfico más grande. Puede detectarlos iniciando su búsqueda en un nodo específico y encontrando una ruta que lo lleve de regreso a ese mismo nodo.

? En resumen ...

  • Los gráficos son estructuras de datos increíbles que utiliza todos los días a través de la Búsqueda de Google, Google Maps, GPS y las redes sociales.
  • Se utilizan para representar elementos que comparten conexiones .
  • Los elementos del gráfico se denominan Nodos y las conexiones entre ellos se denominan Aristas .
  • Los gráficos se pueden dirigir, cuando sus bordes tienen una orientación específica, similar a las calles de un solo sentido, o no dirigidos, cuando sus bordes no tienen una orientación específica, similar a las calles de dos sentidos.
  • Los bordes pueden tener un valor asociado, llamado peso .
  • Si un gráfico tiene muchas aristas, se denomina gráfico denso . De lo contrario, si tiene pocos bordes, se denomina gráfico disperso .
  • Una serie de conexiones puede formar un ciclo si crean una ruta que le permite volver al mismo nodo.

¡Continúe aprendiendo sobre estas asombrosas estructuras de datos! Valdrá la pena para tu futuro como desarrollador. Estoy aprendiendo sobre estructuras de datos en este momento y las encuentro completamente fascinantes. ? ? ❤️

Lo importante es no dejar de cuestionar. La curiosidad tiene su propia razón de existir. - Albert Einstein

? ¡Gracias!

Realmente espero que les haya gustado mi artículo. ❤️

Sigueme enGorjeo. ?