Introducción
Contenido
Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. El concepto fue “robado” de las matemáticas y apropiado para las necesidades de la informática.
Hay varias formas en las que podemos describir qué son las gráficas. Abordaremos los gráficos primero de una manera muy simplificada, luego a través de árboles si el lector está familiarizado con el concepto de experiencias anteriores, y finalmente como un término matemático.
Gráficos simplificados
Cada gráfico consta de nodes (también llamados vértices) y aristas. Podemos considerar los nodes como “fragmentos de datos” y los bordes como “relaciones entre esos fragmentos de datos”.
Si queremos señalar que dos fragmentos de datos están relacionados entre sí de alguna manera, los conectaríamos con una ventaja. Los nodes generalmente se representan como círculos con una marca de identificación en ellos, para que podamos distinguir entre nodes, y los bordes se representan mediante líneas (o flechas, como veremos más adelante) que conectan dos nodes.
A menudo se utiliza una forma de la estructura de datos del gráfico al hacer mapas para las líneas de autobús de una ciudad. Verá un mapa simplificado que muestra en qué estaciones (nodes) se detiene el autobús, y la ruta que conecta diferentes paradas es lo que llamamos un borde:
Este gráfico muestra qué diferentes paradas de autobús tenemos y cómo están conectadas. Por ejemplo, podemos ver que, usando esta línea de autobús, para ir de la parada A a la parada C tendríamos que pasar por la parada B, no podemos llegar de otra manera.
Gráficos ponderados
Los gráficos son muy versátiles y esa es una de las razones por las que son tan populares. Digamos que queríamos agregar información sobre cuánto tiempo se tarda en promedio (en minutos) en llegar de una parada de autobús a otra. Agregaríamos “pesos” a nuestros bordes:
Ahora nuestro gráfico muestra aún más información que antes, vemos cuánto tiempo se tarda en llegar de una parada a otra. Podemos deducir que llegar de la parada de autobús A a la parada de autobús C tomaría 23 minutos ya que tendríamos que “atravesar” el borde que conecta la parada de autobús A y la parada de autobús B que tiene un peso de 15 y la (parada de autobús B -> Parada de autobús C) borde, que tiene un peso de 8.
El ejemplo anterior introdujo el concepto de gráficos ponderados, es decir, que los bordes pueden tener valores adjuntos si así lo requerimos.
Gráficos dirigidos y no dirigidos
Ahora veremos otro concepto de gráfico: gráficos dirigidos y no dirigidos. Digamos que nuestra línea de autobús no tenía las mismas paradas en ambas direcciones.
Más precisamente, cuando nuestro autobús parte de la parada A, pasa por B, C y termina en D; sin embargo, en la otra dirección no pasa por C sino por una parada de autobús completamente diferente E, antes de pasar por B. Podríamos hacer algo como esto:
Como sugiere el spoiler de la imagen, este enfoque no es correcto. Con solo mirar este gráfico, no podemos entender por qué paradas de autobús pasa el autobús en qué dirección, ya que nada nos impide ir de B a E, aunque solo deberíamos poder ir de E a B.
Aquí es donde entran en juego los gráficos dirigidos. Los bordes en los gráficos dirigidos se representan mediante flechas en lugar de líneas, una flecha que apunta de A a B significa “podemos ir de A a B pero no al revés”. Si quisiéramos decir que podemos ir tanto de A a B como de B a A, usaríamos una flecha de doble cara.
Ahora, el ciclo ya no es ambiguo:
Ahora está claro que no podemos ir de B a E o de D a C, etc. Está claro que podemos hacer gráficos tan simples o tan complejos como queramos. Podríamos ir un paso más allá en nuestro ejemplo, si por alguna razón tomara una cantidad diferente de tiempo viajar entre algunas paradas de autobús dependiendo de la dirección en la que vayamos.
Aplicaciones de gráficos
A continuación, se muestran algunos ejemplos de datos que se pueden almacenar / representar convenientemente mediante gráficos:
- Un conjunto de personas y sus afiliaciones: Esto se puede hacer usando un gráfico no dirigido, ya que asumimos que si la persona A conoce a la persona B, lo mismo ocurre al revés. Las diferentes personas estarían representadas por nodes, y si la persona A conoce a la persona B, habrá un borde que conectará los dos nodes.
- La estructura de un sitio web: Las diferentes páginas de ese sitio web son nodes, y hay un borde dirigido entre la página A y la página B si existe un enlace a la página B en la página A. Por ejemplo, la página de inicio a menudo tiene enlaces a una página Acerca de nosotros y Contacto.
- Tareas mutuamente dependientes: Podemos representar qué tareas deben completarse antes de la tarea A y qué tareas no pueden completarse antes de que A se haya completado de la siguiente manera: si hay un borde dirigido de B a A, entonces A no se puede completar antes de que se complete B; si hay un borde dirigido de A a C, entonces C no se puede completar antes de que se complete A:
Aquí podemos ver que podemos ponernos anteojos, calcetines, pantalones y una camiseta independientemente de otras prendas. Pero no podemos ponernos los zapatos antes de ponernos los pantalones y los calcetines. Y no podemos salir antes de hacer todo lo demás, excepto ponernos las gafas, ya que puede que no sean necesarias. Estos tipos de gráficos se ordenan fácilmente y podemos ver un orden factible de ejecución de tareas mediante la clasificación topológica.
Nota: Un error frecuente es que los gráficos deben estar conectados, o al menos que cada node debe estar conectado a otro de alguna manera. Esto no es cierto y lo hemos demostrado en el ejemplo anterior. Un gráfico puede estar formado fácilmente por cualquier número de nodes sin un solo borde entre ellos.
Gráficos comparados con árboles
Si está familiarizado con los árboles, los gráficos son fáciles de entender: los árboles son un tipo especial de gráfico, es decir, gráficos con ciertas restricciones. Cada árbol es un gráfico, pero no todo gráfico es un árbol.
Por definición, los árboles son gráficos no dirigidos que:
- Son acíclicos, es decir, no podemos retroceder a ningún node de inicio que elijamos sin retroceso
- Se crea un ciclo agregando cualquier borde en el árbol existente
- La ruta entre dos nodes es única
- Hay un node raíz distinto
- El gráfico está conectado (hay una ruta entre cada dos nodes)
O en términos muy simplificados: los árboles son gráficos conectados sin ciclos. Para los gráficos, simplemente nos deshacemos de todas estas restricciones y mantenemos el concepto de nodes y bordes.
Gráficos como término matemático
Todo lo anterior se originó a partir del término matemático de un gráfico. Una gráfica es un par ordenado G = (V, E), dónde V es un conjunto de vértices y E es el conjunto de aristas.
Gráficos no dirigidos: En el caso de un gráfico no dirigido, E tiene la siguiente definición E ⊆ {{x, y} | (x, y) ∈ V^2}. A veces se agrega una condición adicional si queremos evitar los bordes que tienen el mismo punto de inicio y final (es decir, x ≠ y).
Gráficos dirigidos: E ⊆ {(x, y) | (x, y) ∈ V^2}, aquí también podemos agregar la condición de que x ≠ y si queremos evitar aristas que comienzan y terminan en el mismo node / vértice.
Como podemos ver en las definiciones anteriores del conjunto de aristas E, la única diferencia es que en el caso de gráficos dirigidos (x,y) es un par ordenado, mientras que en gráficos no dirigidos el par {x,y} está desordenado. Esto significa que en un gráfico no dirigido, lo que importa es que x y y están conectados, no en “qué orden”. Entonces podríamos haber escrito {y,x} en vez de {x,y} mientras no pudimos haber escrito (y,x) en vez de (x,y) para un gráfico dirigido.
Todo esto nos lleva a varios temas importantes cuando se trata del recorrido de gráficos en Java: representación de gráficos en código, búsqueda primero en amplitud, búsqueda primero en profundidad y algoritmo de Dijkstra.
Representar gráficos en código
Sabiendo qué son los gráficos, necesitamos una forma de representarlos en código. Por lo general, esto se realiza mediante listas de adyacencia y matrices de adyacencia. En el siguiente artículo presentamos una mirada en profundidad a estas implementaciones en Java:
- Gráficos en Java: representación de gráficos en código
Búsqueda en profundidad (DFS)
La búsqueda en profundidad (DFS) busca lo más lejos posible a lo largo de una rama y luego retrocede para buscar lo más lejos posible en la siguiente rama. Esto significa que en el gráfico anterior, comienza con el primer vecino y continúa por la línea lo más lejos posible.
- Gráficos en Java: búsqueda en profundidad
Búsqueda primero en amplitud (BFS)
Breadth First Search (BFS) es un algoritmo de recorrido de gráfico, a menudo utilizado para encontrar la ruta más corta desde un node inicial a un node objetivo.
BFS visita “capa por capa”. Esto significa que primero visita a todos los hijos del node inicial (raíz). Estos niños son considerados como la “segunda capa”, después de lo cual sus niños son visitados de la misma manera.
- Gráficos en Java: búsqueda primero en amplitud
Algoritmo de Dijkstra
El algoritmo de Dijkstra es un algoritmo de recorrido de grafos muy conocido para encontrar la ruta más corta desde un node / vértice dado a otro.
Hay varias implementaciones de este algoritmo y algunas incluso usan diferentes estructuras de datos y tienen diferentes aplicaciones.
Dijkstra funciona de manera diferente a los algoritmos anteriores. En lugar de comenzar en el node raíz, comienza en el node objetivo y retrocede hasta el node inicial.
- Gráficos en Java: algoritmo de Dijkstra
DFS frente a BFS
Una pregunta que probablemente le vino a la mente cuando estaba leyendo sobre DFS y BFS fue:
“¿Cuál es la diferencia práctica?”
La teoría es clara; BFS primero visita los nodes más cercanos a nuestro node inicial, mientras que DFS profundiza en el gráfico (lo más lejos posible de nuestro node inicial) antes de continuar con otros nodes cercanos a nuestro node inicial.
Repasemos algunos ejemplos:
- Si todo lo que desea hacer es verificar si dos nodes están conectados en absoluto en un gráfico que no le da una razón clara para preferir uno u otro de los algoritmos de recorrido del gráfico: cualquiera de los dos
- Si “sabe” que sus dos nodes están cerca el uno del otro, si es que están conectados, por ejemplo, buscando miembros de la familia en un gráfico de conocidos, utilice BFS
- Si desea contar todas las formas posibles de ir de un node a otro: DFS
- Si desea la ruta más corta (la ruta que pasa por la menor cantidad de nodes) de un node a otro: BFS
- DFS también se puede utilizar para algunas cosas ligeramente avanzadas, como detectar un ciclo en un gráfico o para comprobar componentes fuertemente conectados (un término matemático que significa “que cada node es accesible desde cualquier otro node”) que luego puede usarse para resolver problemas de 2-satisfacibilidad (2-SAT).
Conclusión
Los gráficos son una forma conveniente de almacenar ciertos tipos de datos. Cada gráfico consta de nodes (también llamados vértices) y aristas. Podemos considerar los nodes como “fragmentos de datos” y los bordes como “relaciones entre esos fragmentos de datos”.
Los algoritmos de recorrido de gráficos como BFS, DFS, el algoritmo de Dijkstra y A * se utilizan con mucha frecuencia en muchas ramas de la ciencia de datos y el Machine Learning.
