Qué es BFS y DFS
Tenemos un grafo hecho de puntos y líneas. Si sales de un punto y quieres recorrerlo entero, ¿cómo deberías caminar? Puedes extenderte como ondas desde lo más cercano, o seguir un camino hasta el final y luego volver. El mismo grafo, dos formas de caminar.
Salir de un punto
En la lección anterior vimos los grafos: los puntos son nodos, las líneas son aristas y un grafo sin ciclos es un árbol.
Esta vez vamos a caminar sobre uno. Para caminar, primero hay que decidir desde dónde salir.
Al elegir un punto, lo primero que aparece son sus vecinos directos.
Haz clic en un punto para elegir la salida. (salida = azul · vecinos directos = iluminados)
Un paso desde la salida te lleva a un vecino, y otro paso desde ahí, al vecino de un vecino.
Avanzar así por las líneas, pisando los puntos uno a uno, es lo que significa caminar sobre un grafo.
Lo más cercano primero: en anchura
La primera forma de caminar es una onda. Pisas todo lo que está junto a la salida, luego una capa más allá, y luego otra.
Como los círculos que se forman al tirar una piedra a un estanque, se extiende hacia fuera desde lo más cercano, en orden.
Cada clic extiende la onda una capa más. (puntos pisados = de color · misma capa = misma distancia)
Mientras la onda se extiende, los puntos que aún no se han visitado esperan en una fila, y los que entraron primero en ella se visitan primero.
Por eso los puntos cercanos siempre van antes que los lejanos. La capa es la distancia.
Hasta el final: en profundidad
La segunda forma de caminar es explorar un laberinto. Eliges un camino y avanzas todo lo que puedas.
Cuando ya no hay adónde ir, retrocedes un paso y vuelves a avanzar por un camino lateral que no has probado.
En vez de extenderse a lo ancho, se adentra a fondo.
Cada clic sigue un camino hasta el final y retrocede cuando está bloqueado. (punto actual = azul · camino desandado = atenuado)
Para no olvidar adónde volver, apilas los puntos por los que pasas.
Desde lo alto de la pila vas desandando para buscar caminos laterales. Por eso el recorrido en profundidad vuelve primero al lugar que visitó más recientemente.
En anchura da el camino más corto
La onda no se extiende porque sí. Como pisa primero la capa más cercana, el momento en que llega por primera vez a un punto es justamente el camino más rápido hasta él.
Si todas las líneas miden lo mismo, la capa en la que llegas a un punto es su distancia desde la salida, sin rodeos.
Haz clic en un punto para comparar la distancia de llegada de las dos formas de caminar. (número de capa en anchura = distancia más corta)
El recorrido en profundidad llega lejos rápido, pero puede llegar dando un rodeo. Por eso la distancia más corta le corresponde a la onda, es decir, al recorrido en anchura.
Por ahora, eso sí, hemos supuesto que todas las líneas miden lo mismo. Si cada línea mide distinto, la cosa cambia, y eso lo veremos en la próxima lección.
Resumen
Hemos visto dos formas de caminar sobre un grafo. En anchura se extiende como una onda, capa a capa desde lo más cercano; en profundidad sigue un camino hasta el final y luego retrocede.
Las dos pisan todos los puntos, pero en distinto orden. Cuando las distancias son iguales, en anchura da el camino más corto.
Toca cada forma de caminar para encender su figura. (en anchura = onda · en profundidad = hasta el final)
Buscar una ruta en un mapa, seguir a los amigos de tus amigos, salir de un laberinto: caminar sobre un grafo está más cerca de lo que parece.
En la próxima lección buscaremos el camino más rápido en un grafo donde cada línea mide distinto.