Búsqueda en profundidad (DFS)
Explora un grafo siguiendo un camino lo más profundo posible y luego vuelve a la última bifurcación. La pila en pantalla es ese camino.
- tiempo O(V + E)
- espacio O(V)
- usa una pila
¿Qué significan estos términos?
- Vértice: un punto del grafo, dibujado aquí como un círculo con una letra.
- Arista: una línea que une dos vértices. Aquí se puede recorrer en los dos sentidos.
- Vecinos: los vértices unidos a un vértice por una arista. Se revisan en orden alfabético.
- Cola: el primero en entrar es el primero en salir. BFS siempre toma el vértice que lleva más tiempo esperando.
- Pila: el último en entrar es el primero en salir. DFS siempre sigue desde el último vértice al que llegó.
- V y E: el número de vértices y de aristas. O(V + E) significa que cada vértice y cada arista se procesan un número fijo de veces.
- en la pila
- actual
- listo
- arista del árbol de búsqueda
- arista omitida
Empieza en A. Pulsa reproducir o avanza paso a paso.
Espacio: reproducir o pausar. Flechas izquierda y derecha: paso a paso. Inicio y Fin: saltar.
Prueba esto: Elige el grafo con ciclos. Cada arista discontinua lleva de vuelta a un vértice que ya está en la pila o listo: esa arista cierra un ciclo.
Cómo funciona
DFS se llama a sí misma con el primer vecino que aún no ha visto, luego con el primer vecino nuevo de ese vértice, y así sucesivamente. Cuando un vértice ya no tiene vecinos nuevos, su llamada termina y DFS retrocede un paso para probar el siguiente vecino de allí. Las llamadas abiertas forman una pila, que siempre es el camino desde el inicio hasta el vértice actual. El número junto a un vértice es el orden en que se visitó.
Cuándo es una buena opción
Usa DFS para saber qué se puede alcanzar, para encontrar ciclos, para recorrer un laberinto o para ordenar tareas que dependen unas de otras. No encuentra el camino más corto.