Recorrido del gráfico - Graph traversal

En informática , el recorrido de gráfico (también conocido como búsqueda de gráfico ) se refiere al proceso de visitar (verificar y / o actualizar) cada vértice de un gráfico . Dichos recorridos se clasifican por el orden en que se visitan los vértices. El recorrido de árbol es un caso especial de recorrido de gráfico.

Redundancia

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 se sabe necesariamente antes de hacer la transición a un vértice que ya se ha 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 no se sigue el camino; 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 las búsquedas 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.

Algoritmos de recorrido de grafos

Nota. - Si cada vértice de un gráfico debe ser atravesado 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, realizando el algoritmo en cada vértice que aún no está visitado cuando se examina.

Una descripción no verbal de tres algoritmos de recorrido de gráficos: búsqueda aleatoria, búsqueda en profundidad y búsqueda en amplitud.

Búsqueda en profundidad

Una búsqueda en profundidad primero (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 en particular antes de explorar su amplitud. Una pila (a menudo la pila de llamadas del programa a través de recursividad ) se usa generalmente cuando se implementa 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 hacer 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 la nueva ruta como lo había hecho antes, retrocediendo cuando encuentre callejones sin salida y terminando 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 tipos topológicos y las pruebas de planaridad .

Pseudocódigo

  • Entrada : Una gráfica G y un vértice v de G .
  • Resultado : un etiquetado de los bordes en el componente conectado de v como bordes de descubrimiento y bordes posteriores.
procedure DFS(G, v) is
    label v as explored
    for all edges e in G.incidentEdges(v) do
        if edge e is unexplored then
            wG.adjacentVertex(v, e)
            if vertex w is unexplored then
                label e as a discovered edge
                recursively call DFS(G, w)
            else
               label e as a back edge

Búsqueda en amplitud primero

Una búsqueda en amplitud (BFS) es otra técnica para recorrer 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.

Pseudocódigo

  • Entrada : Una gráfica G y un vértice v de G .
  • Salida : el vértice más cercano a v que satisface algunas condiciones, o nulo si no existe tal vértice.
procedure BFS(G, v) is
    create a queue Q
    enqueue v onto Q
    mark v
    while Q is not empty do
        wQ.dequeue()
        if w is what we are looking for then
            return w
        for all edges e in G.adjacentEdges(w) do
            xG.adjacentVertex(w, e)
            if x is not marked then
                mark x
                enqueue x onto Q
    return null

Aplicaciones

La búsqueda en amplitud se puede utilizar para resolver muchos problemas en la teoría de grafos, por ejemplo:

Exploración de gráficos

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 gráfico solo 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 de nuevo 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 de comercio , 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 :

  • En el caso no dirigido, el recorrido codicioso es como máximo O (ln n ) veces más largo que un recorrido óptimo. El mejor límite inferior conocido para cualquier algoritmo determinista en línea es 10/3.
    • Los gráficos no dirigidos de peso unitario se pueden explorar con una ración competitiva de 2 - ε , que ya es un límite estricto en los gráficos de Tadpole .
  • En el caso dirigido, el recorrido codicioso es como máximo ( n - 1 ) veces más largo que un recorrido óptimo. Esto coincide con el límite inferior de n - 1 . Un límite inferior competitivo análogo de Ω ( n ) también es válido para algoritmos aleatorios que conocen las coordenadas de cada nodo en una incrustación geométrica. Si en lugar de visitar todos los nodos se tiene que encontrar un único nodo "tesoro", los límites competitivos son Θ ( n 2 ) en los gráficos dirigidos por 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 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. 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 ≤ id .

Referencias

Ver también