En informática , el recorrido de un grafo (también conocido como búsqueda de 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 el que se visitan los vértices. El recorrido de un árbol es un caso especial de recorrido de grafos.
A diferencia del recorrido de árboles, el recorrido de grafos puede requerir que se visiten algunos vértices más de una vez, ya que no se sabe necesariamente antes de pasar a un vértice que ya se ha explorado. A medida que los grafos se vuelven más densos , esta redundancia se vuelve más frecuente, lo que hace que el tiempo de cálculo aumente; a medida que los grafos se vuelven más dispersos, ocurre lo contrario.
Por lo tanto, suele ser necesario recordar qué vértices ya han sido explorados por el algoritmo, de modo que se vuelvan a visitar los vértices 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 grafo 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 no se sigue el camino; de lo contrario, el algoritmo verifica/actualiza el vértice y continúa por su camino actual.
Varios casos especiales de grafos 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 ya se han visitado todos los vértices "antecesores" del vértice actual (y otros, según el algoritmo). Tanto las búsquedas en grafos 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 se va a recorrer cada vértice de un gráfico con un algoritmo basado en árboles (como DFS o BFS), entonces se debe llamar al algoritmo 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 y ejecutando el algoritmo en cada vértice que aún no se haya visitado al examinarlo.
Una búsqueda en profundidad (DFS) es un algoritmo para recorrer un gráfico finito. La DFS visita los vértices secundarios antes de visitar los vértices hermanos; es decir, recorre la profundidad de cualquier ruta en particular antes de explorar su amplitud. Generalmente, se utiliza una pila (a menudo, la pila de llamadas del programa a través de la recursión ) 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, continuará por el nuevo camino como lo había hecho antes, retrocediendo a medida que encuentra callejones sin salida y finalizando solo 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 ordenamientos topológicos y las pruebas de planaridad .
procedimiento DFS( G , v ) es etiqueta v como explorada para todos los bordes e en G .incidentEdges( v ) si el borde e no es explorado entonces w ← G .adjacentVertex( v , e ) si el vértice w no es explorado entonces etiqueta e como un borde descubierto Llamar recursivamente a DFS( G , w ); de lo contrario, etiquetar e como borde posterior
Otra técnica para recorrer un grafo finito es la búsqueda en amplitud (BFS, por sus siglas en inglés). La 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 la ruta más corta de un vértice a otro.
procedimiento BFS( G , v ) es crear una cola Q poner en cola v en Q marcar v mientras Q no esté vacío hacer w ← Q .dequeue() si w es lo que estamos buscando entonces devolver w para todos los bordes e en G .adjacentEdges( w ) hacer x ← G .adjacentVertex( w , e ) si x no está marcado entonces marcar x poner en cola x en Q devolver 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 grafos puede verse como 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 el tiempo de ejecución del algoritmo. Un modelo común es el siguiente: dado un grafo conectado G = ( V , E ) con pesos de arista no negativos. El algoritmo comienza en algún vértice y conoce todas las aristas salientes incidentes y los vértices al final de estas aristas, pero no más. Cuando se visita un nuevo vértice, se conocen nuevamente todas las aristas salientes incidentes y los vértices al final. El objetivo es visitar todos 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 vendedor ambulante , donde el vendedor tiene que descubrir el grafo sobre la marcha.
Para gráficos generales, el algoritmo más conocido, tanto para gráficos dirigidos como no dirigidos, es un algoritmo voraz simple :
Una secuencia de recorrido universal es una secuencia de instrucciones que comprende un recorrido de grafo para cualquier grafo regular con un número determinado 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 5 ) 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 j , y v j tiene d vecinos, entonces la secuencia de recorrido especificará el siguiente nodo a visitar, v j +1 , como el i ésimo vecino de v j , donde 1 ≤ i ≤ d .