BFS 0-1 con una deque
Encuentre caminos mínimos cuando los pesos son 0 o 1
BFS 0-1 con una deque 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.
Un tipo especial de grafo
Algunos grafos solo tienen aristas con pesos de 0 o 1. En ellos puede superar a Dijkstra con un truco más sencillo y rápido.
Conozca 0-1 BFS
0-1 BFS encuentra caminos más cortos en grafos con pesos 0/1 en tiempo lineal, sin heap ni factor logarítmico.
La herramienta: una deque
Sustituya el heap por una deque, una cola en la que puede insertar y extraer elementos tanto por el frente como por el final.
from collections import deque
dq = deque([src])La idea central
Una arista de peso 0 mantiene la misma distancia, mientras que una arista de peso 1 suma uno. La deque mantiene ambos grupos en orden.
El frente para las aristas de peso cero
¿Atraviesa una arista de peso 0? Use appendleft para insertar el vecino, de modo que se procese a continuación, ya que no añade distancia.
dq.appendleft(v)El final para las aristas de peso uno
¿Atraviesa una arista de peso 1? Use append para insertar el vecino al final, porque se encuentra una capa más lejos del origen.
dq.append(v)Extraiga desde el frente
Haga siempre popleft para extraer el nodo actual. Esto mantiene la deque ordenada por distancia, igual que un BFS por capas.
u = dq.popleft()Relaje con el peso
Relaje cada arista: calcule una nueva distancia como dist[u] más el peso de la arista y, según ese peso, inserte el nodo al frente o al final.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndPor qué permanece ordenada
La deque contiene como máximo dos distancias distintas a la vez. Ese invariante explica exactamente por qué funciona insertar elementos al frente o al final.
La velocidad lineal
Como no hay heap, 0-1 BFS se ejecuta en O(V + E), notablemente más rápido que Dijkstra en el mismo grafo.
Cuándo utilizarlo
Úselo siempre que los movimientos sean gratuitos o cuesten uno, como en cuadrículas donde algunos pasos están bloqueados y otros están abiertos.
Comprobación rápida
Relaja un vecino a través de una arista de peso 0. ¿Dónde debe colocarlo?
Repaso: 0-1 BFS
Con una deque, inserte las aristas de peso 0 al frente y las de peso 1 al final. Obtendrá caminos más cortos en un tiempo limpio de O(V+E). ⚡
Preguntas frecuentes
¿La lección «BFS 0-1 con una deque» es gratis?
Sí — el texto completo de «BFS 0-1 con una deque» 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 0-1 con una deque»?
Encuentre caminos mínimos cuando los pesos son 0 o 1 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 0-1 con una deque»?
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
- Dijkstra con un heap
- BFS 0-1 con una deque
- Bellman-Ford y aristas negativas
- Floyd-Warshall para todos los pares