BFS para caminos mínimos no ponderados
Calcule la distancia por capas desde un origen
BFS para caminos mínimos no ponderados es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Qué hace BFS
BFS explora un grafo por capas: primero el nodo inicial, después todo lo que está a un paso, luego a dos pasos y así sucesivamente. 🌊
Por qué las capas indican el camino más corto
Como BFS termina una capa antes de pasar a la siguiente, la primera vez que alcanza un nodo encuentra el camino no ponderado más corto hasta él.
La cola es el motor
BFS utiliza una cola: primero en entrar, primero en salir. Añade los vecinos nuevos al final y procesa después el elemento del frente.
from collections import deque
q = deque([start])Registrar lo que ya ha visto
Mantenga una marca de visited para no introducir nunca dos veces el mismo nodo en la cola. Así BFS se mantiene rápido y finito.
visited = [False] * (n + 1)
visited[start] = TrueAlmacenar la distancia
Un arreglo dist contiene la capa de cada nodo. El nodo inicial recibe 0; cada vecino recibe uno más que su nodo padre.
dist = [-1] * (n + 1)
dist[start] = 0Extraer el primero
En cada paso, tome el nodo que está al frente de la cola. Es el nodo no procesado más cercano, así que debe gestionarlo ahora.
u = q.popleft()Expandir los vecinos
Para cada vecino de u que no haya sido visitado, márquelo, establezca su distancia y añádalo al final de la cola.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)El bucle completo
Siga extrayendo y expandiendo mientras la cola no esté vacía. Cuando se vacíe, habrá visitado todos los nodos alcanzables.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Marcar al introducir en la cola
Establezca visited en el momento de introducir el nodo en la cola, no al extraerlo. Marcarlo tarde permite que se introduzcan duplicados en la cola.
Los nodos inalcanzables permanecen en -1
Cualquier nodo que aún conserve la distancia -1 después de BFS es simplemente inalcanzable desde el nodo inicial. Esa respuesta también es significativa.
BFS es lineal
BFS visita cada nodo y cada arista una vez, por lo que se ejecuta en O(n + m). Esto suele bastar para superar los límites de la mayoría de las competiciones.
Comprobación rápida
¿Por qué BFS sin modificaciones proporciona los caminos más cortos?
Resumen
Ejecuta BFS con una cola y un arreglo dist: marque al introducir en la cola, expanda los vecinos y lea las distancias más cortas cuando termine. 🎉
Preguntas frecuentes
¿La lección «BFS para caminos mínimos no ponderados» es gratis?
Sí — el texto completo de «BFS para caminos mínimos no ponderados» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «BFS para caminos mínimos no ponderados»?
Calcule la distancia por capas desde un origen Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «BFS para caminos mínimos no ponderados»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Listas de adyacencia a partir de la entrada
- BFS para caminos mínimos no ponderados
- DFS, recursión y pilas iterativas
- Componentes conexas y flood fill