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.
- O(V + E)
- espacio O(V)
- pila
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.
Pila: el último en entrar es el primero en salir. DFS siempre sigue desde el último vértice al que llegó.
Otros términos de esta página
- 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.
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.