En informática , el recorrido de gráficos (también conocido como búsqueda de gráficos ) se refiere al proceso de visitar (verificar y/o actualizar) cada vértice de un gráfico . Estos recorridos se clasifican según el orden en que se visitan los vértices. El recorrido de árbol es un caso especial de recorrido de gráfico.
A diferencia del recorrido de árbol, el recorrido de gráfico puede requerir que algunos vértices se visiten más de una vez, ya que no necesariamente se sabe antes de realizar la transición a un vértice que ya ha sido explorado. A medida que los gráficos se vuelven más densos , esta redundancia se vuelve más frecuente, lo que hace que aumente el tiempo de cálculo; A medida que los gráficos se vuelven más escasos, ocurre lo contrario.
Por lo tanto, generalmente es necesario recordar qué vértices ya han sido explorados por el algoritmo, de modo que los vértices 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 cada vértice del gráfico con 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 el camino no continúa; de lo contrario, el algoritmo verifica/actualiza el vértice y continúa por su ruta actual.
Varios casos especiales de gráficos implican la visita de otros vértices en su estructura y, por lo tanto, no requieren que la visita se registre explícitamente durante el recorrido. Un ejemplo importante de esto es un árbol: durante un recorrido se puede suponer que todos los vértices "ancestros" del vértice actual (y otros dependiendo del algoritmo) ya han sido visitados. Tanto la búsqueda de gráficos en profundidad como en amplitud son adaptaciones de algoritmos basados en árboles, que se distinguen principalmente por la falta de un vértice "raíz" determinado estructuralmente y la adición de una estructura de datos para registrar el estado de visita del recorrido.
Nota. — Si cada vértice de un gráfico debe ser recorrido por un algoritmo basado en árbol (como DFS o BFS), entonces el algoritmo debe llamarse al menos una vez para cada componente conectado del gráfico. Esto se logra 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 ha sido visitado cuando se examina.
Una búsqueda en profundidad (DFS) es un algoritmo para atravesar un gráfico finito. DFS visita los vértices secundarios antes de visitar los vértices hermanos; es decir, atraviesa la profundidad de cualquier camino particular antes de explorar su amplitud. Generalmente se utiliza una pila (a menudo la pila de llamadas del programa mediante recursividad ) al implementar el algoritmo.
El algoritmo comienza con un vértice "raíz" elegido; luego realiza una transición iterativa desde el vértice actual a un vértice adyacente no visitado, hasta que ya no puede encontrar un vértice inexplorado al que realizar la transición desde su ubicación actual. Luego, el algoritmo retrocede a lo largo de los vértices visitados anteriormente, hasta que encuentra un vértice conectado a un territorio aún más inexplorado. Luego procederá por el nuevo camino como lo había hecho antes, retrocediendo cuando encuentre callejones sin salida y finalizando sólo cuando el algoritmo haya retrocedido más allá del vértice "raíz" original desde el primer paso.
DFS es la base de muchos algoritmos relacionados con gráficos, incluidos los tipos topológicos y las pruebas de planaridad .
El procedimiento DFS( G , v ) es la etiqueta v explorada para todos los bordes e en G .incidentEdges( v ) si el borde e no está explorado entonces w ← G .adjacentVertex( v , e ) si el vértice w no está explorado entonces etiqueta e como a borde descubierto llamar recursivamente a DFS( G , w ) de lo contrario etiquetar e como borde posterior
Una búsqueda en amplitud (BFS) es otra técnica para atravesar un gráfico finito. BFS visita los vértices hermanos antes de visitar los vértices secundarios y se utiliza una cola en el proceso de búsqueda. Este algoritmo se utiliza a menudo para encontrar el camino más corto de un vértice a otro.
El procedimiento BFS( G , v ) es crear una cola Q poner en cola v en Q marcar v mientras Q no está vacío do w ← Q .dequeue() si w es lo que estamos buscando, entonces devolvemos w para todos los bordes e en G .adjacentEdges ( w ) hacer x ← G .adjacentVertex( w , e ) si x no está marcado , entonces marque x ponga en cola x en Q return null
La búsqueda en amplitud se puede utilizar para resolver muchos problemas en teoría de grafos, por ejemplo:
El problema de la exploración de gráficos puede verse como una variante del recorrido de gráficos. Es un problema en línea , lo que significa que la información sobre el gráfico sólo se revela durante el tiempo de ejecución del algoritmo. Un modelo común es el siguiente: dado un gráfico conectado G = ( V , E ) con pesos de borde no negativos. El algoritmo comienza en algún vértice y conoce todos los bordes salientes incidentes y los vértices al final de estos bordes, pero no más. Cuando se visita un nuevo vértice, se conocen nuevamente todos los bordes salientes incidentes y los vértices al final. El objetivo es visitar los n vértices y volver 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 vendedor tiene que descubrir el gráfico sobre la marcha.
Para gráficos generales, el algoritmo más conocido para gráficos dirigidos y no dirigidos es un algoritmo codicioso simple :
Una secuencia transversal universal es una secuencia de instrucciones que comprende un recorrido de gráfico para cualquier gráfico regular con un número determinado de vértices y para cualquier vértice inicial. Aleliunas et al. utilizaron una prueba probabilística. para mostrar que existe una secuencia transversal universal con un número de instrucciones proporcional a O ( n 5 ) para cualquier gráfico 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 j y v j tiene d vecinos, entonces la secuencia transversal especificará el siguiente nodo a visitar, v j +1 , como el i ésimo vecino de v j , donde 1 ≤ i ≤ d .