Cómo llegar al colegio con menos paradas
Un grafo es un conjunto de puntos unidos por líneas, como el mapa de una línea de autobús. Con un grafo puedes buscar el camino más corto entre dos puntos.
Así funcionan las apps de rutas y las redes sociales cuando te sugieren amigos. Hoy aprendes el algoritmo más sencillo: la búsqueda en anchura.
Al final de esta lección
Nota
Puedo encontrar el camino más corto en un grafo con la búsqueda en anchura.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Grafo | un conjunto de nodos unidos por aristas |
| Nodo | un punto del grafo, como una parada |
| Arista | una línea que une dos nodos |
| Vecino | un nodo unido a otro por una arista |
| Salto | un paso por una arista, de un nodo a un vecino |
| Búsqueda en anchura | visitar primero los vecinos, luego los vecinos de los vecinos |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un grafo son nodos y aristas
Piensa en seis paradas de autobús: Casa, Plaza, Parque, Colegio, Museo y Estadio. Cada parada es un nodo. Cada tramo de autobús entre dos paradas es una arista.
Los vecinos de una parada son las paradas a un solo salto. En Python, un grafo se guarda en un diccionario: la clave es el nodo y el valor es la lista de sus vecinos.
Cuenta los nodos y las aristas
docker exec jupyter python3 -c "g = {'Casa': ['Plaza', 'Parque'], 'Plaza': ['Casa', 'Colegio'], 'Parque': ['Casa', 'Colegio', 'Museo'], 'Colegio': ['Plaza', 'Parque', 'Estadio'], 'Museo': ['Parque'], 'Estadio': ['Colegio']}; print(len(g), sum(len(v) for v in g.values()) // 2, g['Colegio'])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Busca las paradas con tres vecinos
docker exec jupyter python3 -c "g = {'Casa': ['Plaza', 'Parque'], 'Plaza': ['Casa', 'Colegio'], 'Parque': ['Casa', 'Colegio', 'Museo'], 'Colegio': ['Plaza', 'Parque', 'Estadio'], 'Museo': ['Parque'], 'Estadio': ['Colegio']}; print([k for k in g if len(g[k]) == 3])"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Qué cuentan los dos Run
El primer Run imprime 6 6 ['Plaza', 'Parque', 'Estadio']: seis paradas, seis aristas, y el Colegio tiene tres vecinos.
Cada arista aparece dos veces en el diccionario, una por cada extremo. Por eso se divide entre 2. El segundo Run imprime ['Parque', 'Colegio'], las dos paradas con tres vecinos.
La búsqueda en anchura avanza por rondas
Sales de Casa. Primero visitas todos los vecinos, a un salto. Después visitas los vecinos de esos, a dos saltos. Y así, ronda tras ronda.
Una cola guarda los nodos que faltan por visitar, en orden. Sacas el primero, metes sus vecinos nuevos al final, y repites. Una lista de visitados evita volver a un nodo.
Ejemplo resuelto: la cola desde Casa
| Paso | Sale de la cola | Entran | Cola después |
|---|---|---|---|
| 1 | Casa | Plaza, Parque | Plaza, Parque |
| 2 | Plaza | Colegio | Parque, Colegio |
| 3 | Parque | Museo | Colegio, Museo |
| 4 | Colegio | Estadio | Museo, Estadio |
| 5 | Museo | Nadie | Estadio |
| 6 | Estadio | Nadie | Vacía |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La búsqueda en anchura en Python
graph = {"Casa": ["Plaza", "Parque"], "Plaza": ["Casa", "Colegio"],
"Parque": ["Casa", "Colegio", "Museo"],
"Colegio": ["Plaza", "Parque", "Estadio"],
"Museo": ["Parque"], "Estadio": ["Colegio"]}
def bfs(graph, start):
distance = {start: 0}
queue = [start]
while len(queue) > 0:
current = queue.pop(0)
for neighbour in graph[current]:
if neighbour not in distance:
distance[neighbour] = distance[current] + 1
queue.append(neighbour)
return distance
print(bfs(graph, "Casa"))
Un error frecuente
Advertencia
Mucha gente se olvida de apuntar los nodos visitados. En este mapa hay un ciclo: Casa, Plaza, Colegio y Parque vuelven a Casa. Sin la lista de visitados, el programa da vueltas para siempre. Apunta cada nodo en el momento en que lo metes en la cola.
La anchura da el camino con menos saltos
La búsqueda visita los nodos a un salto antes que los de dos saltos. Por eso la primera vez que llega a un nodo es por el camino más corto en saltos.
El diccionario distance guarda esos saltos. Estadio está a 3 de Casa. Pero ojo: cuenta saltos, no minutos. Si cada tramo tarda distinto, hace falta otra idea.
Ejemplo resuelto: saltos desde Casa
| Parada | Saltos desde Casa | Por dónde se llega |
|---|---|---|
| Casa | 0 | Es el principio |
| Plaza | 1 | Casa |
| Parque | 1 | Casa |
| Colegio | 2 | Plaza o Parque |
| Museo | 2 | Parque |
| Estadio | 3 | Colegio |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Para ir más lejos: tu propio mapa
En el cuaderno, dibuja en papel el mapa de tu barrio con siete paradas y escríbelo como un diccionario. Comprueba que cada arista aparece dos veces.
Después ejecuta tu bfs y compara las distancias con las que cuentas a mano. Cambia una arista y vuelve a probar.