Este artículo demuestra el procedimiento para implementar el DFS para un árbol o gráfico proporcionado.
¿Cómo implementar la primera búsqueda en profundidad o DFS para un gráfico en Java?
El DFS se usa principalmente para buscar un gráfico visitando cada rama/vértice exactamente una vez. Puede detectar o identificar ciclos en un gráfico que ayuda a prevenir interbloqueos. Se puede utilizar para resolver acertijos o problemas de laberinto. El DFS se puede implementar/utilizar en algoritmos gráficos, rastreo web y diseño de compiladores.
Para obtener una explicación, visite el siguiente código de la primera búsqueda en profundidad o DFS:
clase Grafico {
privado Lista enlazada añadirNodo [ ] ;
privado booleano atravesado [ ] ;
Grafico ( En t vértices ) {
añadirNodo = nuevo Lista enlazada [ vértices ] ;
atravesado = nuevo booleano [ vértices ] ;
para ( En t i = 0 ; i < vértices ; i ++ )
añadirNodo [ i ] = nuevo Lista enlazada ( ) ;
}
vacío añadirEdge ( En t origen, En t comenzar ) {
añadirNodo [ origen ] . agregar ( comenzar ) ;
}
Descripción del código anterior:
- Primero, la clase llamada “ Grafico ' es creado. En su interior, declara un “ Lista enlazada ' llamado ' añadirNodo[] ” y una matriz de tipo booleano denominada “ atravesado[] ”.
- A continuación, pase los vértices para el constructor de la ' Grafico ” class como parámetro.
- Después de eso, el “ para Se crea un bucle para moverse a través de cada nodo de la rama seleccionada.
- Al final, el tipo de vacío “ añadirBorde() ” se usa para agregar bordes entre vértices. Esta función toma dos parámetros: la fuente del vértice “ origen ” y el vértice de destino “ comenzar ”.
Después de la creación de un gráfico, ahora agreguemos el código de búsqueda en profundidad o DFS para el gráfico creado anteriormente:
vacío SFD ( En t vértice ) {
atravesado [ vértice ] = verdadero ;
Sistema . afuera . imprimir ( vértice + ' ' ) ;
iterador este = añadirNodo [ vértice ] . iterador de lista ( ) ;
mientras ( este. tieneSiguiente ( ) ) {
En t adj. = este. próximo ( ) ;
si ( ! atravesado [ adj. ] )
SFD ( adj. ) ;
}
}
En el bloque de código anterior:
- Primero el ' SFD() ” se crea la función que está obteniendo “ vértice ” como parámetro. Ese vértice se marca como visitado.
- A continuación, imprima el vértice visitado usando el ' fuera.imprimir() ' método.
- Luego, cree una instancia de “ iterador ” que itera sobre los vértices adyacentes del vértice actual.
- Si no se visita el vértice, entonces pasa ese vértice al “ SFD() ' función.
Ahora, vamos a crear un ' principal() ” parte de la función para crear el gráfico y luego aplicar DFS a eso:
público estático vacío principal ( Cadena argumentos [ ] ) {
Gráfico k = nuevo Grafico ( 4 ) ;
k. añadirEdge ( 0 , 1 ) ;
k. añadirEdge ( 1 , 2 ) ;
k. añadirEdge ( 2 , 3 ) ;
k. añadirEdge ( 3 , 3 ) ;
Sistema . afuera . imprimir ( 'Lo que sigue es profundidad primero recorrido' ) ;
k. SFD ( 1 ) ;
}
}
Explicación del código anterior:
- Primero, crea un objeto “ k ' Para el ' Grafico() ' método.
- A continuación, el “ añadirBorde() El método ” se utiliza para agregar bordes entre múltiples vértices. Esto crea la estructura de nuestro gráfico.
- Al final, pase cualquier valor de vértice como argumento al ya creado “ SFD() ' función. Para encontrar esa ruta de vértice desde la raíz, utilice un algoritmo de búsqueda primero en profundidad. Por ejemplo, un valor de “ 1 ” se pasa al “ SFD() ' función.
Después del final de la fase de compilación:
El resultado muestra que la búsqueda en profundidad se ha implementado correctamente.
Conclusión
Depth First Search es un algoritmo transversal de gráficos que constituye la base de muchos algoritmos de gráficos, como la búsqueda de la ruta más corta, los árboles de expansión y el análisis de conectividad. Comienza desde el nodo raíz y luego avanza lo más profundo posible hasta el nodo de salida o el último nodo de esa rama antes de retroceder. Este artículo ha demostrado el procedimiento para implementar la búsqueda en profundidad o DFS para un gráfico en Java.