62,723 lecturas

Una introducción a las estructuras de datos: gráficos y sus algoritmos transversales

por Meet Zaveri2018/07/23

Demasiado Largo; Para Leer

La gran mayoría de los algoritmos de interés operan sobre datos. Por lo tanto, existen formas particulares de organizar los datos que juegan un papel fundamental en el diseño y análisis de algoritmos. A partir de eso, podemos decir que las estructuras de datos son simplemente formas de organizar datos.

Companies Mentioned

Coin Mentioned

featured image - Una introducción a las estructuras de datos: gráficos y sus algoritmos transversales

Son lineales o no lineales . Las matrices y las listas enlazadas son ejemplos de estructuras de datos lineales. Por otro lado, los gráficos y los árboles son formas de estructuras de datos no lineales.

Por ejemplo, una estructura de datos común es la lista o matriz , que es una secuencia ordenada de valores. Aquí hay una lista de números: 0, 1, 1, 2, 3, 5, 8, 13. El concepto de la lista no es particular de un idioma, y también se usa fuera de la programación en la vida cotidiana: listas de deseos, compras listas, etc.

Los algoritmos son recetas para la ejecución lógica del problema. No son lo mismo que las estructuras de datos. Los algoritmos suelen ser "mejores" si funcionan más rápido o de manera más eficiente (usando menos tiempo, memoria o ambos).

Pero aquí, en este artículo, se trata de buscar estructuras de datos no lineales: gráficos

Buceando en gráficos

Un grafo es un sistema en el que existen potencialmente múltiples formas de llegar desde un punto arbitrario, A, a otro punto arbitrario, B.

Un gráfico se define normalmente como un par de conjuntos (V,E). V es un conjunto de objetos arbitrarios llamados vértices o nodos, y E es un conjunto de pares de vértices, a los que llamamos aristas o (más raramente) arcos. En un gráfico no dirigido, las aristas son pares no ordenados o simplemente conjuntos de dos vértices. Usualmente escribo uv en lugar de {u,v} para denotar el borde no dirigido entre u y v.

En un grafo dirigido, las aristas son pares ordenados de vértices. Usaré u → v en lugar de (u,v) para indicar el borde dirigido de u a v y viceversa para todos los bordes de este artículo.

Los gráficos también pueden ser no dirigidos o dirigidos, cíclicos o acíclicos (principalmente dirigidos) o ponderados.

Recorriendo un gráfico

Para visitar cada nodo o vértice que es un componente conectado, se utilizan algoritmos basados en árboles. Puede hacer esto fácilmente iterando a través de todos los vértices del gráfico, ejecutando el algoritmo en cada vértice que aún no se ha visitado cuando se examina.

Generalmente se utilizan dos algoritmos para el recorrido de un gráfico: búsqueda primero en profundidad (DFS) y búsqueda primero en amplitud (BFS).

Algoritmo de primera búsqueda en profundidad (DFS)

Visualización del recorrido DFS

La búsqueda en profundidad (DFS) es un algoritmo para buscar una estructura de datos de gráfico o árbol . El algoritmo comienza en el nodo raíz (superior) de un árbol y va tan lejos como puede por una rama determinada (camino), y luego retrocede hasta que encuentra un camino inexplorado y luego lo explora. El algoritmo hace esto hasta que se ha explorado todo el gráfico.

Muchos problemas en informática se pueden pensar en términos de gráficos. Por ejemplo, el análisis de redes, el mapeo de rutas, la programación y la búsqueda de árboles de expansión son problemas gráficos. Para analizar estos problemas, los algoritmos de búsqueda de gráficos como la búsqueda en profundidad son útiles. - Fuente

El pseudocódigo más simple sería:

La búsqueda en profundidad es una forma común que muchas personas usan naturalmente al resolver problemas como laberintos.

Primero, seleccionamos un camino en el laberinto (por el bien de este ejemplo, elijamos un camino de acuerdo con alguna regla que establezcamos con anticipación) y lo seguimos hasta llegar a un callejón sin salida o llegar al final del laberinto. Si un camino dado no funciona, retrocedemos y tomamos un camino alternativo desde un cruce pasado, y probamos ese camino.

Para convertir esto en un algoritmo de gráfico transversal, básicamente reemplazamos "niño" con "vecino". Pero para evitar bucles infinitos, solo queremos visitar cada vértice una vez. Al igual que en BFS, podemos usar marcas para realizar un seguimiento de los vértices que ya se han visitado, para que no los volvamos a visitar. Además, al igual que en BFS, podemos usar esta búsqueda para construir un árbol de expansión con ciertas propiedades útiles.

dfs(vértice v){visitar(v);para cada vecino w de vif w no se visita{dfs(w);añadir borde vw al árbol T}}

Aquí está la implementación de Python usando recursividad:

Esta fue una descripción básica de cómo funciona DFS. Si desea profundizar más, hay algunas cosas excelentes disponibles en Internet y también en Medium.

Algoritmo de búsqueda en amplitud (BFS)

Comienza en la raíz del árbol (o algún nodo arbitrario de un gráfico, a veces denominado "clave de búsqueda") y explora todos los nodos vecinos en la profundidad actual antes de pasar a los nodos en el siguiente nivel de profundidad.

El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos, por lo que podemos volver al mismo nodo. Para evitar procesar un nodo más de una vez, usamos una matriz visitada booleana. Para simplificar, se supone que todos los vértices son accesibles desde el vértice inicial.

Lo que hacemos en un BFS es un proceso simple paso a paso:

Comienza desde un vértice S . Sea este vértice en lo que se llama…. “Nivel 0”.
Encuentre todos los demás vértices que son inmediatamente accesibles desde este vértice inicial S , es decir, están a solo un borde de distancia (los vértices adyacentes).
Marque estos vértices adyacentes para que estén en el "Nivel 1".
Es posible que regrese al mismo vértice debido a un bucle o un anillo en el gráfico. Si esto sucede, su BFS tardará ∞ tiempo. Por lo tanto, irá solo a aquellos vértices que no tengan su "Nivel" establecido en algún valor.
Marque cuál es el vértice padre del vértice actual en el que se encuentra, es decir, el vértice desde el que accedió al vértice actual. Haz esto para todos los vértices en el Nivel 1.
Ahora, encuentra todos esos vértices que están a un solo borde de distancia de todos los vértices que están en el "Nivel 1". Este nuevo conjunto de vértices estará en el "Nivel 2".
Repite este proceso hasta que te quedes sin gráfico.\

Vea esto: https://www.programiz.com/dsa/graph-bfs

Implementación de Python usando la cola

Gráficos dirigidos y no dirigidos

Un gráfico no dirigido es un gráfico en el que los bordes no tienen orientación. La arista ( x , y ) es idéntica a la arista ( y , x ). Es decir, no son pares ordenados, sino pares desordenados, es decir, conjuntos de dos vértices { x , y } (o 2 multiconjuntos en el caso de bucles ). El número máximo de aristas en un gráfico no dirigido sin bucle es n ( n − 1)/2.

Para cualquier borde u y v en un gráfico no dirigido, llamamos a ua vecino de v y viceversa. El grado de un nodo es su número de vecinos. En grafos dirigidos, tenemos dos tipos de vecinos. Para cualquier borde dirigido u — >v , llamamos a ua predecesor de v ya va sucesor de u.

Gráficos cíclicos y acíclicos

Entre las muchas propiedades de los gráficos, dos son importantes para un gran número de aplicaciones: la conectividad y la aciclicidad. Ambos se basan en la noción de un camino.

Un gráfico cíclico es un gráfico que contiene al menos un ciclo de gráfico . Recuerde también que los gráficos cíclicos no pueden ser una forma de árbol porque los nodos del árbol solo se visitan una vez a través de DFS o BFS (métodos transversales).

Un gráfico acíclico es un gráfico sin ciclos (un ciclo es un circuito completo). Al seguir el gráfico de nodo a nodo, nunca visitará el mismo nodo dos veces.

¿Qué es el gráfico acíclico dirigido?

Un gráfico acíclico dirigido es un gráfico acíclico que tiene una dirección así como una falta de ciclos.

Un árbol es una formación de gráfico acíclico dirigido

Fuente: http://www.statisticshowto.com/directed-acyclic-graph/

Las partes del gráfico anterior son:

Entero = el conjunto de los vértices.
Conjunto de vértices = {1,2,3,4,5,6,7}.
Juego de aristas = {(1,2), (1,3), (2,4), (2,5), (3,6), (4,7), (5,7), (6,7 )}.

Un gráfico acíclico dirigido tiene un ordenamiento topológico . Esto significa que los nodos están ordenados de modo que el nodo inicial tenga un valor más bajo que el nodo final. Un DAG tiene un ordenamiento topológico único si tiene una ruta dirigida que contiene todos los nodos; en este caso, el orden es el mismo que el orden en que aparecen los nodos en la ruta.

En informática , los DAG también se denominan gráficos de espera . Cuando se usa un DAG para detectar un interbloqueo, ilustra que un recurso tiene que esperar a que continúe otro proceso.

¿Cómo podemos detectar ciclos en un gráfico?

Resulta que la razón por la que el algoritmo de búsqueda primero en profundidad es particularmente bueno para detectar ciclos se debe al hecho de que es eficiente para encontrar bordes hacia atrás. Veremos el algoritmo DFS más adelante en este artículo.

Matrices de adyacencia y representación de listas de adyacencia

Considere este gráfico como ejemplo para comprender las listas de adyacencia y las matrices de adyacencia

La realización de algoritmos de grafos utilizando la representación de grafos por listas de aristas, o por listas de adyacencia, puede ser engorrosa si hay muchas aristas en el gráfico. Para simplificar el cálculo, los gráficos se pueden representar usando matrices. Aquí se presentarán dos tipos de matrices comúnmente utilizadas para representar gráficos. Uno se basa en la adyacencia de los vértices y el otro se basa en la incidencia de los vértices y las aristas.

Dada una matriz de adyacencia, podemos decidir en el tiempo Θ(1) si dos vértices están conectados por una arista simplemente mirando en la ranura apropiada de la matriz. También podemos listar todos los vecinos de un vértice en tiempo Θ(V) escaneando la fila (o columna) correspondiente.

Comprender la matriz de adyacencia de la imagen dada arriba ...

Comprendamos cómo se construye la matriz de adyacencia a partir de la imagen anterior. Para simplificar, he discutido esto solo para el vértice "a". Lo mismo se aplica a todos los vértices.

Debido al límite de páginas, no he incluido análisis para a → d y a → e. Como podemos concluir de la imagen, hay un borde de a → d y a → e respectivamente.

¿Y qué pasa con la lista de adyacencia?

La estructura de datos de la lista de adyacencia debería recordarle inmediatamente las tablas hash con encadenamiento; las dos estructuras de datos son idénticas.

Una lista de adyacencia es una matriz de listas enlazadas, una lista por vértice. Cada lista enlazada almacena los vecinos del vértice correspondiente.

Por ejemplo, para el vértice **a** , hay aristas que conducen a vecinos como **b,d and e** . Entonces, su lista vinculada respectiva contiene vértices que están conectados a través del borde.

Recordatorio → Para gráficos no dirigidos, cada borde (u,v) se almacena dos veces, una en la lista de vecinos de u y otra en la lista de vecinos de v; para gráficos dirigidos, cada borde se almacena solo una vez.

Gráficos ponderados

gráfico ponderado. Fuente: https://cs.stackexchange.com

Un gráfico ponderado (o dígrafo ponderado) es un gráfico (o dígrafo) con números asignados a sus bordes. Estos números se llaman pesos o costos. El interés en tales gráficos está motivado por numerosas aplicaciones del mundo real, como encontrar el camino más corto entre dos puntos en una red de transporte o comunicación o el problema del viajante de comercio .

Ejemplos de grafos en la vida real

Google Maps: ¡es solo un gran gráfico! Donde los bordes representan calles y los vértices representan cruces.

La teoría de grafos subyace en Internet. Se usa mucho en el código de red (construir tablas de enrutamiento, etc.), pero aparece en todo tipo de lugares, como construir un motor de búsqueda en Internet o una plataforma de redes sociales.

Para profundizar en los árboles, este artículo es uno de los preferidos que elegí: https://medium.freecodecamp.org/all-you-need-to-know-about-tree-data-structures-bceacb85490c

Hechos que más importan:

Todos los árboles son grafos. No todos los gráficos son árboles.
Un árbol es una especie de gráfico, solo si está conectado. Por ejemplo, el gráfico que consta de los vértices A y B y no tiene aristas no es un árbol, aunque es un gráfico acíclico.
Un solo vértice también se considera un árbol (sin ciclos, conectado al vacío). Así que dos vértices desconectados forman un bosque de dos árboles.
Un árbol es un tipo especial de gráfico donde nunca hay múltiples caminos, siempre hay una sola forma de llegar de A a B, para todas las combinaciones posibles de A y B.