- Actual
- En la pila
- Terminado
- Camino
Búsqueda en profundidad (DFS)
La búsqueda en profundidad explora un grafo como quien recorre un laberinto con una mano en la pared: sigue un camino hasta donde llega y solo retrocede cuando no hay nada nuevo adonde ir. Para ello usa una pila. Haz clic en un nodo para empezar desde él, elige un destino si quieres, y avanza paso a paso para ver cómo la pila crece y se reduce, cómo cada nodo recibe su número de visita y qué aristas cierran un ciclo. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Haz clic en un nodo para que sea el origen; cambia el clic a Destino y haz clic en otro nodo para buscar un camino hasta él. El número de cada nodo es el orden en que se visitó, y la fila bajo el grafo es la pila, desde el origen hasta el nodo de la cima. Nuevo grafo crea otro grafo; elige cuántos nodos y aristas tiene. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Haz clic en un nodo para que sea el origen. Para buscar un camino, cambia el clic a Destino y haz clic en otro nodo.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
- Observa la pila bajo el grafo y el número de visita de cada nodo. Nuevo grafo crea otro grafo para probar.
Cómo funciona la búsqueda en profundidad
Pon el nodo de origen en la pila. Luego repite: mira el siguiente vecino del nodo de la cima de la pila. Un vecino que aún no se ha visto recibe el siguiente número de visita, recuerda el nodo desde el que se alcanzó y pasa a la cima de la pila, así que la búsqueda sigue desde ahí. Cuando el nodo de la cima no tiene más vecinos que revisar, está terminado y sale de la pila, y la búsqueda vuelve al nodo de debajo. Cuando la pila está vacía, se han visitado todos los nodos alcanzables.
Lo que dice la pila
Como la búsqueda siempre sigue desde el nodo más reciente, la pila es siempre un camino desde el origen hasta el nodo que se está mirando. Cuando se alcanza el destino, la pila es un camino hasta él, aunque normalmente no el más corto: ese lo encuentra la búsqueda en anchura. En un grafo no dirigido, una arista hacia un nodo que sigue en la pila, distinto del que se acaba de dejar, cierra un ciclo. Los nodos recordados forman un árbol, el árbol de búsqueda en profundidad, y el orden en que terminan los nodos es la clave del ordenamiento topológico.
Preguntas frecuentes
¿Qué es la búsqueda en profundidad?
Una forma de explorar un grafo desde un nodo de origen siguiendo un camino tan hondo como llegue, y retrocediendo para probar otra rama solo cuando no hay nada nuevo adonde ir. Usa una pila, o recursión, para recordar el camino de vuelta.
¿La búsqueda en profundidad encuentra el camino más corto?
No. Encuentra un camino hasta el destino si existe, pero puede ser mucho más largo de lo necesario, porque la DFS se queda con la primera rama que prueba. Usa la búsqueda en anchura para tener el menor número de aristas, o el algoritmo de Dijkstra cuando las aristas tienen longitud.
¿Qué diferencia hay entre DFS y BFS?
La búsqueda en profundidad usa una pila y avanza a fondo por un camino antes de retroceder. La búsqueda en anchura usa una cola y se extiende de forma uniforme, anillo a anillo. Ambas visitan todos los nodos alcanzables en un tiempo que crece con el número de nodos más el de aristas; la BFS encuentra caminos más cortos, mientras que la DFS es la opción natural para ciclos, laberintos y ordenamiento topológico.
¿Cómo encuentra la DFS un ciclo?
En un grafo no dirigido, si la búsqueda encuentra una arista hacia un nodo que sigue en la pila, y ese nodo no es del que acaba de venir, la arista cierra un bucle. En la app, la línea de estado lo indica cuando ocurre.
¿Se envía mi grafo a algún sitio?
No. El grafo se crea y se recorre en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor