Dos formas de caminar un grafo

Partiendo de un punto

La vez pasada vimos un grafo.
Los puntos son nodos, las líneas aristas,
y un grafo sin bucles es un árbol.
Esta vez, caminemos sobre él.
Para caminar, primero
elegimos dónde empezar.
Elige un punto,
y sus vecinos directos aparecen.

Haz clic en un punto para fijar el inicio. (Inicio = azul · vecinos directos = iluminados)

Un paso desde el inicio
llega a un vecino.
Otro paso desde ahí
es el vecino del vecino.
Moviendo los pies
por las líneas así,
tocando puntos uno a uno,
se camina por un grafo.

Lo cercano primero, en anchura

El primer andar es una onda.
Toca todo lo pegado al inicio,
luego una capa más lejos,
luego otra capa.
Como una piedra en un estanque
que esparce anillos,
de cerca a lejos por turnos,
se abre hacia afuera.

Cada clic esparce una capa como una onda. (Puntos tocados = de color · misma capa es misma distancia)

Mientras la onda se esparce,
los puntos aún no alcanzados
esperan en una fila.
Los que se formaron primero
se visitan primero, por turno.
Así un punto más cercano
siempre va antes que uno lejano.
La capa es la distancia.

Hasta el final, en profundidad

El segundo andar es explorar un laberinto.
Elige un camino
y ve tan lejos como puedas.
Cuando no queda nada,
retrocede un paso
y baja por un desvío sin probar.
En vez de esparcirse,
se hunde hondo.

Haz clic para ir por un camino hasta el final, luego retrocede al atascarte. (Punto actual = azul · camino retrocedido = atenuado)

Para no olvidar volver,
apila los puntos que pasaste.
Desde la pila apilada,
vuelve sobre el de arriba
para hallar un desvío.
Así el de profundidad
regresa primero
al lugar visitado más reciente.

El de anchura da el más corto

La onda no se esparce en vano.
Como toca la capa cercana primero,
el momento en que alcanzas un punto
es la ruta más rápida hacia él.
Si cada línea es la misma distancia,
en qué capa lo alcanzas
es la distancia desde el inicio.
No hay rodeo.

Haz clic para comparar el orden de llegada de los dos andares. (Número de capa en anchura = la distancia más corta)

El de profundidad va lejos rápido,
pero puede llegar dando un rodeo.
Así que la distancia más corta
es de la onda, el de anchura.
Por ahora, eso sí, tratamos
cada línea como la misma distancia.
Cuando las líneas difieren en distancia
es otra historia, y eso para la próxima.

Resumen

Vimos dos formas de caminar un grafo.
El de anchura se esparce como una onda,
capa por capa desde lo cercano,
y el de profundidad sigue un camino
hasta el final, luego retrocede.
Ambos tocan cada punto,
solo en distinto orden.
Con igual distancia, el de anchura es el más corto.

Toca los dos andares para encenderlos. (Anchura = onda · profundidad = hasta el final)

Hallar una ruta en un mapa,
seguir amigos de amigos,
salir de un laberinto.
Caminar por un grafo
está más cerca de lo que crees.
La próxima, hablaremos de hallar
la ruta más rápida en un grafo
donde las líneas difieren en distancia.