La idea detrás de la primera búsqueda en profundidad es que, en un gráfico, tenemos que avanzar (en profundidad) mientras exista la posibilidad, si no, de retroceder. es decir, cuando hemos alcanzado una posición en la que ya se han visitado todos los nodos adyacentes al nodo actual, luego retroceda y elija otra ruta.
Los gráficos pueden contener ciclos, por lo que durante la primera búsqueda en profundidad, podemos visitar un nodo varias veces. Para evitar procesar un nodo más de una vez, podemos utilizar una matriz booleana visitada. Por ejemplo, en el siguiente gráfico (primera figura a continuación), si comenzamos a atravesar el vértice 2. Cuando llegamos al vértice 0, buscamos todos los vértices adyacentes. 2 también es un vértice adyacente de 0. Si no marcamos los vértices visitados, entonces 2 se procesará nuevamente y se convertirá en un proceso que no termina. Profundidad El primer recorrido de este gráfico es 2, 0, 1, 3. La segunda figura a continuación muestra cómo se visitan los nodos en profundidad y cómo un nodo, una vez marcado, no se vuelve a visitar
- ¿Me pueden ayudar a aprender estructuras de datos y algoritmos?
- Recientemente me enamoré de las estructuras de datos y algoritmos. ¿Qué idioma (s) y qué rama (s) de matemáticas le servirían mejor y qué tipo de trabajos de entrada debería buscar una vez que lo lleve a un nivel decente, unos 4-6 meses después?
- ¿Qué algoritmo debo usar para la generación de código para mi AST?
- ¿Cuál es la diferencia entre una matriz y una lista de matrices?
- ¿Cómo se usa el hashing para la integridad?
Podemos implementar DFS usando la estructura de datos de la pila. La siguiente figura muestra cómo funciona DFS con la ayuda de una pila.
Ahora, dado que estamos usando la pila, podemos implementarla recursivamente (usando la pila de llamadas implícitas) o iterativamente (usando nuestra propia pila explícita). A continuación se muestra el pseudocódigo para el enfoque recursivo.
// La función para hacer DFS transversal. Utiliza DFSUtil recursivo ()
DFS nulo (int s) {
// Marca todos los vértices como no visitados (se establece como
// falso por defecto en java)
booleano [] visitado = nuevo booleano [v]
// Llama a la función auxiliar recursiva para imprimir el recorrido DFS
DFSUtil (s, visitado)
}
// Una función utilizada por DFS
nulo DFSUtil (int s, boolean [] visitado) {
// Marque el nodo actual visitado e imprímalo
visitado [s] = verdadero
imprimir m
// Recurrir para todos los vértices adyacentes a este vértice
para (número entero n: adj [s]) {
if (! visitado [n])
DFSUtil (n, visitado)
}
}
Tenga en cuenta que el código anterior solo atraviesa los vértices accesibles desde un vértice fuente dado. Es posible que no se pueda acceder a todos los vértices desde un vértice dado (ejemplo, gráfico desconectado). Para completar el recorrido DFS de tales gráficos, debemos llamar a DFSUtil () para cada vértice. Además, antes de llamar a DFSUtil (), debemos verificar si ya está impreso por alguna otra llamada de DFSUtil (). La función DFSUtil () permanece igual, solo los cambios estarán en la función principal DFS (). A continuación se muestra la función DFS () modificada.
// La función para hacer DFS transversal. Utiliza DFSUtil recursivo ()
nulo DFS () {
// Marca todos los vértices como no visitados (se establece como
// falso por defecto en java)
booleano [] visitado = nuevo booleano [v]
// Llama a la función auxiliar recursiva para imprimir el recorrido DFS
// a partir de todos los vértices uno por uno
para (int i = 0; i <v; i ++)
if (! visitado [i])
DFSUtil (i, visitado)
}
Veamos también cómo podemos resolverlo iterativamente. A continuación se muestra el pseudocódigo para el enfoque iterativo.
// Método iterativo para hacer un recorrido DFS de un gráfico
anular DFSItr () {
booleano [] visitado = nuevo booleano [v]
Pila s = nueva pila ()
// Hacer DFS para todos los vértices uno por uno para imprimir todos los nodos
// de un gráfico disjunto. Este bucle ‘for’ no es necesario si
// queremos imprimir solo los nodos conectados
para (int i = 0; i <v; i ++) {
if (! visitó [i]) {
// comienza con un nodo en la pila
s.push (i)
imprimir i
visitado [i] = verdadero
while (! s.isEmpty ()) {
int j = s.peek ()
boolean isFound = false
para (número entero n: adj [j]) {
if (! visitó [n]) {
s.push (n)
imprimir n
visitado [n] = verdadero
isFound = true
rotura
}
}
si (! isFound)
s.pop ()
}
}
}
}
La complejidad del tiempo para ambos enfoques será O (V + E), donde V es el número de vértices y E es el número de aristas en el gráfico. DFS visita cada vértice en el gráfico y verifica cada borde para cada vértice, por lo tanto, la complejidad temporal será O (V + E).
Notas al pie:
Profundidad del primer recorrido o DFS para un gráfico – GeeksforGeeks
