Fuentes:
UNAM, Mtro. ISC. MIGUEL ANGEL SÁNCHEZ HERNÁNDEZ
https://drive.google.com/file/d/10mizsWCMF7ZQJGE9BP_7byHXAnJP_781/view
<aside> 🤔 Antes de leer esto por favor repasa la diferencia entre concepto y definición
</aside>
DFS es un algoritmo de búsqueda que se utiliza para recorrer o buscar en una estructura de grafo o árbol. Este algoritmo se caracteriza por explorar tan lejos como sea posible a lo largo de un camino antes de retroceder.
En otras palabras DFS nos indica que primero tiene que ir lo más lejos posible a la izquierda (o a la derecha) para encotrar el camino n, luego regresa hacia arriba hasta el primer cruce, avanza una paso a la derecha (o a la izquierda) para encotrr el camino n+1, y de nuevo lo más lejos posible a la izquierda (o la derecha). Se repite este proceso hasta que todos lo nodos se visiten.
https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fwww.codesdope.com%2Fstaticroot%2Fimages%2Falgorithm%2Fdfs.gif&f=1&nofb=1&ipt=93b373d68744367229f82d7780649539e0b5da9cdebc4fce591d29dc5867de8f&ipo=images
Proceso del agoritmo
- Primero elige un nodo de inicio para que de ese nodo partan todos los demas caminos Este algortmo esta preparado para enfrentarse a cualquier grafo, es por ello que se van a asignar 3 estados el estado “descubieto”, “Completamente visitado” y “no descubieto”
- Se les asigna todos los nodos como “no descubieto”, se verifican todos los nodos de conectados al nodo inicio en la imagen se usa el nodo “1”
- Se busca el nodo que encaje en el criterio de eleccion(en algunos es por el más a la izquierda con el estado “no descubierto”) y se porcede a saignarle el estado “descubierto”
- Se verfica que los nosods ayacentes a l nodo eleguido no esten descubietos , de caso contrario se psasa al estado “Completamente visitado” y se mueve al nodo anterior en estado “descubierto”
- Se repite el paso 2 siempre y cuando el nodo inicion no este en el estado “Completamente visitado”
DFS recursivo
JavaScript
Java
Python
