En ciencias de la computación, recorrido del grafo es el problema de visitar todos los nodos en un gráfico de una manera particular, actualización y / o control de sus valores a lo largo del camino, recorrido del árbol es un caso especial del recorrido del grafo.
Una búsqueda en profundidad (DFS) es un algoritmo para recorrer un grafo finito. DFS visitas los nodos secundarios antes de visitar los nodos del mismo nivel, es decir, que atraviesa la profundidad de cualquier camino en particular antes de explorar su amplitud. Una pila (a menudo del programa pila de llamadas a través de recursión) se usa generalmente cuando la ejecución del algoritmo.
El algoritmo comienza con un nodo “raíz” elegida, entonces iterativamente transiciones desde el nodo actual a una, el nodo no visitado adyacente, hasta que ya no puede encontrar un nodo inexplorado para la transición a partir de su ubicación actual. El algoritmo entonces retrocede a lo largo de los nodos visitados anteriormente, hasta que encuentra un nodo conectado a un territorio aún más desconocido. A continuación, se procederá por el nuevo camino como antes, dando marcha atrás cuando se encuentra con callejones sin salida, y termina cuando el algoritmo ha retrocedido más allá del nodo original “root” desde el primer paso.
DFS es la base de muchos algoritmos de grafos conexos, incluyendo las clases topológicas y pruebas de planitud.
No hay comentarios.:
Publicar un comentario