Hispanopedia WikiEn informática , el recorrido de grafos (también conocido como búsqueda en grafos ) se refiere al proceso de visitar (verificar y/o actualizar) cada vértice de un grafo . Dichos recorridos se clasifican según el orden en que se visitan los vértices. El recorrido de árboles es un caso especial del recorrido de grafos.
Redundancia
A diferencia del recorrido de árboles, el recorrido de grafos puede requerir que algunos vértices se visiten más de una vez, ya que no siempre se sabe con certeza si un vértice ya ha sido explorado antes de pasar a él. A medida que los grafos se vuelven más densos , esta redundancia se hace más frecuente, lo que aumenta el tiempo de cálculo; ocurre lo contrario cuando los grafos se vuelven más dispersos.
Por lo tanto, suele ser necesario recordar qué vértices ya ha explorado el algoritmo, para que se vuelvan a visitar con la menor frecuencia posible (o, en el peor de los casos, para evitar que el recorrido continúe indefinidamente). Esto se puede lograr asociando a cada vértice del grafo un estado de "color" o "visita" durante el recorrido, que luego se verifica y actualiza a medida que el algoritmo visita cada vértice. Si el vértice ya ha sido visitado, se ignora y no se continúa con la ruta; de lo contrario, el algoritmo verifica/actualiza el vértice y continúa por su ruta actual.
En algunos casos especiales de grafos, la visita a otros vértices de su estructura no requiere que se registre explícitamente durante el recorrido. Un ejemplo importante es un árbol: durante el recorrido, se puede asumir que todos los vértices "antepasados" del vértice actual (y otros, según el algoritmo) ya han sido visitados. Tanto la búsqueda en profundidad como la búsqueda en amplitud son adaptaciones de algoritmos basados en árboles, que se distinguen principalmente por la ausencia de un vértice "raíz" estructuralmente determinado y la adición de una estructura de datos para registrar el estado de visita del recorrido.
Algoritmos de recorrido de grafos
Nota: Si se va a recorrer cada vértice de un grafo mediante un algoritmo basado en árboles (como DFS o BFS), entonces el algoritmo debe llamarse al menos una vez para cada componente conexa del grafo. Esto se logra fácilmente iterando a través de todos los vértices del grafo y ejecutando el algoritmo en cada vértice que aún no haya sido visitado al momento de examinarlo.
Búsqueda en profundidad
La búsqueda en profundidad (DFS, por sus siglas en inglés) es un algoritmo para recorrer un grafo finito. DFS visita los vértices hijos antes de visitar los vértices hermanos; es decir, recorre la profundidad de cualquier camino antes de explorar su amplitud. Generalmente, se utiliza una pila (a menudo la pila de llamadas del programa mediante recursión ) al implementar el algoritmo.
El algoritmo comienza con un vértice raíz seleccionado; luego, transita iterativamente desde el vértice actual a un vértice adyacente no visitado, hasta que ya no encuentra un vértice inexplorado al que transitar desde su ubicación actual. A continuación, el algoritmo retrocede a lo largo de los vértices visitados previamente, hasta encontrar un vértice conectado a un territorio aún más inexplorado. Continúa entonces por el nuevo camino como lo hizo antes, retrocediendo al encontrar callejones sin salida, y finalizando solo cuando el algoritmo ha superado el vértice raíz original del primer paso.
El DFS es la base de muchos algoritmos relacionados con grafos, incluidos los algoritmos de ordenación topológica y las pruebas de planaridad .
Pseudocódigo
- Entrada : Un grafo G y un vértice v de G.
- Salida : Un etiquetado de las aristas en el componente conectado de v como aristas de descubrimiento y aristas de retorno.
El procedimiento DFS( G , v ) etiqueta v como explorado para todas las aristas e en G .incidentEdges( v ) hacer si la arista e no está explorada entonces w ← G .adjacentVertex ( v , e ) si el vértice w no está explorado entonces etiqueta e como una arista descubierta llamar recursivamente a DFS( G , w ) de lo contrario etiquetar e como un borde posterior
Búsqueda en amplitud
La búsqueda en anchura (BFS) es otra técnica para recorrer un grafo finito. La BFS visita los vértices hermanos antes de visitar los vértices hijos, y se utiliza una cola en el proceso de búsqueda. Este algoritmo se usa frecuentemente para encontrar el camino más corto entre dos vértices.
Pseudocódigo
- Entrada : Un grafo G y un vértice v de G.
- Salida : El vértice más cercano a v que satisface ciertas condiciones, o nulo si no existe tal vértice.
El procedimiento BFS( G , v ) consiste en crear una cola Q , encolar v en Q, marcar v mientras Q no esté vacía, hacer w ← Q.dequeue () si w es lo que buscamos, entonces devolver w para todas las aristas e en G.adjacentEdges ( w ) hacer x ← G.adjacentVertex ( w , e ) si x no está marcado, entonces marcar x, encolar x en Q, devolver null
Aplicaciones
La búsqueda en anchura se puede utilizar para resolver muchos problemas en la teoría de grafos, por ejemplo:
- encontrar todos los vértices dentro de un componente conectado ;
- El algoritmo de Cheney ;
- encontrar el camino más corto entre dos vértices;
- probar si un grafo es bipartito ;
- Numeración de malla mediante el algoritmo Cuthill-McKee ;
- Algoritmo de Ford-Fulkerson para calcular el flujo máximo en una red de flujo ;
- Serialización/deserialización de un árbol binario frente a serialización en orden ordenado (permite reconstruir el árbol de manera eficiente);
- algoritmos de generación de laberintos ;
- Algoritmo de relleno por inundación para marcar regiones contiguas de una imagen bidimensional o una matriz n-dimensional;
- análisis de redes y relaciones.
Exploración de gráficos
El problema de la exploración de grafos puede considerarse una variante del recorrido de grafos. Es un problema en línea , lo que significa que la información sobre el grafo solo se revela durante la ejecución del algoritmo. Un modelo común es el siguiente: dado un grafo conexo G = ( V , E ) con pesos de aristas no negativos, el algoritmo comienza en un vértice y conoce todas las aristas incidentes salientes y los vértices en sus extremos, pero nada más. Al visitar un nuevo vértice, se conocen nuevamente todas las aristas incidentes salientes y los vértices en sus extremos. El objetivo es visitar los n vértices y regresar al vértice inicial, pero la suma de los pesos del recorrido debe ser lo más pequeña posible. El problema también puede entenderse como una versión específica del problema del viajante , donde el viajante debe descubrir el grafo sobre la marcha.
Para grafos generales, el mejor algoritmo conocido tanto para grafos no dirigidos como dirigidos es un algoritmo voraz simple :
- En el caso no dirigido, el recorrido voraz es como máximo O (ln n ) veces más largo que un recorrido óptimo. [ 1 ] El mejor límite inferior conocido para cualquier algoritmo en línea determinista es 10/3. [ 2 ]
- Los grafos no dirigidos de peso unitario se pueden explorar con una razón competitiva de 2 − ε , [ 3 ] que ya es una cota ajustada en los grafos Tadpole . [ 4 ]
- En el caso dirigido, el recorrido voraz es como máximo ( n − 1 ) veces más largo que un recorrido óptimo. Esto coincide con el límite inferior de n − 1. [ 5 ] Un límite inferior competitivo análogo de Ω ( n ) también se cumple para algoritmos aleatorios que conocen las coordenadas de cada nodo en una incrustación geométrica. Si en lugar de visitar todos los nodos solo se tiene que encontrar un único nodo "tesoro", los límites competitivos son Θ ( n2 ) en grafos dirigidos de peso unitario, tanto para algoritmos deterministas como aleatorios.
Secuencias de recorrido universal
Una secuencia de recorrido universal es una secuencia de instrucciones que comprende un recorrido de grafo para cualquier grafo regular con un número fijo de vértices y para cualquier vértice inicial. Aleliunas et al. utilizaron una prueba probabilística para demostrar que existe una secuencia de recorrido universal con un número de instrucciones proporcional a O(n⁵) para cualquier grafo regular con n vértices. [6 ] Los pasos especificados en la secuencia son relativos al nodo actual, no absolutos. Por ejemplo, si el nodo actual es vⱼ y vⱼ tiene d vecinos, entonces la secuencia de recorrido especificará el siguiente nodo a visitar, vⱼ + 1 , como el i - ésimo vecino de vⱼ , donde 1 ≤ i ≤ d .
Véase también
Referencias
- ↑ Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, II, Philip M. (1977). "Análisis de varias heurísticas para el problema del viajante". SIAM Journal on Computing . 6 (3): 563– 581. doi : 10.1137/0206041 . S2CID 14764079 .
- ↑ Birx, Alexander; Disser, Yann; Hopp, Alexander V.; Karousatou, Christina (mayo de 2021). "Un límite inferior mejorado para la exploración competitiva de grafos". Theoretical Computer Science . 868 : 65–86 . arXiv : 2002.10958 . doi : 10.1016/j.tcs.2021.04.003 . S2CID 211296296 .
- ↑ Miyazaki, Shuichi; Morimoto, Naoyuki; Okabe, Yasuo (2009). "El problema de la exploración de grafos en línea en grafos restringidos". IEICE Transactions on Information and Systems . E92-D (9): 1620– 1627. Bibcode : 2009IEITI..92.1620M . doi : 10.1587/transinf.E92.D.1620 . hdl : 2433/226939 . S2CID 8355092 .
- ↑ Brandt, Sebastian; Foerster, Klaus-Tycho; Maurer, Jonathan; Wattenhofer, Roger (noviembre de 2020). "Exploración de grafos en línea en una clase de grafos restringida: soluciones óptimas para grafos de renacuajo". Theoretical Computer Science . 839 : 176–185 . arXiv : 1903.00581 . doi : 10.1016/j.tcs.2020.06.007 . S2CID 67856035 .
- ↑ Foerster, Klaus-Tycho; Wattenhofer, Roger (diciembre de 2016). "Límites competitivos inferiores y superiores para la exploración en línea de grafos dirigidos" . Theoretical Computer Science . 655 : 15–29 . doi : 10.1016/j.tcs.2015.11.017 .
- ↑ Aleliunas, R.; Karp, R.; Lipton, R.; Lovász, L.; Rackoff, C. (1979). "Paseos aleatorios, secuencias de recorrido universales y la complejidad de los problemas de laberintos". XX Simposio Anual sobre Fundamentos de la Informática (SFCS 1979) . págs. 218–223 . doi : 10.1109/SFCS.1979.34 . S2CID 18719861 .
- Algoritmos de grafos
