Cuántos saltos hay hasta un servidor
La búsqueda en anchura es un algoritmo que recorre un grafo y encuentra el camino con menos saltos entre dos puntos. Un grafo es un conjunto de puntos unidos por líneas.
En una empresa, para llegar a un servidor de copias hay que pasar por otras máquinas con ssh. La búsqueda en anchura dice cuál es la ruta con menos saltos.
Al final de esta lección
Nota
Puedo encontrar un camino con la búsqueda en anchura.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Grafo | puntos unidos por líneas | |
| Nodo | un punto del grafo | devbox |
| Arista | una línea que une dos nodos | |
| Cola | una lista donde se sale por donde se entró primero | |
| Visitado | un nodo que ya se ha mirado | |
| Camino más corto | el que tiene menos saltos |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un grafo son nodos y aristas
Un grafo tiene nodos, que son los puntos, y aristas, que son las líneas que los unen. Una red de máquinas es un grafo: cada máquina es un nodo y cada salto de ssh es una arista.
En Python, un diccionario guarda cada nodo con la lista de sus vecinos, los nodos a un salto.
Las aristas que salen de student
printf 'student devbox\nstudent web\ndevbox db\nweb db\n' | grep '^student'Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Solo los vecinos de student
printf 'student devbox\nstudent web\ndevbox db\nweb db\n' | grep '^student' | cut -d' ' -f2Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
La búsqueda en anchura avanza por capas
Empieza en un nodo. Primero visita todos los vecinos, que están a un salto. Después los vecinos de esos, a dos saltos. Y así, capa a capa.
Una cola guarda lo que falta por visitar: el primero que entra es el primero que sale. Una lista de visitados evita volver a un nodo y caer en un ciclo.
La cola paso a paso desde student
| Se saca | Se añaden | La cola queda |
|---|---|---|
| student | devbox, web | devbox, web |
| devbox | db | web, db |
| web | cache | db, cache |
| db | backup | cache, backup |
| cache | Nada | backup |
| backup | Nada | Vacía |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
El recorrido en anchura
# Búsqueda en anchura: primero las máquinas a un salto, luego a dos.
network = {
"student": ["devbox", "web"],
"devbox": ["student", "db"],
"web": ["student", "db", "cache"],
"db": ["devbox", "web", "backup"],
"cache": ["web"],
"backup": ["db"],
}
queue = ["student"]
visited = ["student"]
order = []
while len(queue) > 0:
machine = queue.pop(0)
order.append(machine)
for next_machine in network[machine]:
if next_machine not in visited:
visited.append(next_machine)
queue.append(next_machine)
print(order)
# Cambia el primero de la cola a "backup".
Un error frecuente
Advertencia
Mucha gente olvida la lista de visitados porque el grafo parece pequeño. Si el grafo tiene un ciclo, como student, devbox y student otra vez, el programa no termina. Marca cada nodo al meterlo en la cola, no al sacarlo.
La anchura da el camino con menos saltos
La búsqueda visita primero los nodos a un salto y luego a dos. Por eso la primera vez que llega a un nodo es por el camino más corto en saltos.
Para saber cuántos, guarda junto a cada nodo los saltos del que lo descubrió, más uno. Esta búsqueda cuenta saltos. Si cada salto costara distinto, como una tarifa, haría falta otra idea: el camino más barato.
Contar los saltos hasta backup
# La misma búsqueda, guardando los saltos de cada máquina.
network = {
"student": ["devbox", "web"],
"devbox": ["student", "db"],
"web": ["student", "db", "cache"],
"db": ["devbox", "web", "backup"],
"cache": ["web"],
"backup": ["db"],
}
jumps = {"student": 0}
queue = ["student"]
while len(queue) > 0:
machine = queue.pop(0)
for next_machine in network[machine]:
if next_machine not in jumps:
jumps[next_machine] = jumps[machine] + 1
queue.append(next_machine)
print("Saltos hasta backup:", jumps["backup"])