BFS 0-1 com uma Deque
Encontre caminhos mínimos quando os pesos são 0 ou 1.
BFS 0-1 com uma Deque é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Um tipo especial de grafo
Alguns grafos têm apenas pesos de aresta 0 ou 1. Neles, você pode superar o Dijkstra com um truque mais simples e rápido.
Conheça o 0-1 BFS
O 0-1 BFS encontra caminhos mínimos em grafos com pesos 0/1 em tempo linear, sem montículo e sem nenhum fator log.
A ferramenta: uma fila de duas extremidades
Substitua o montículo por uma fila de duas extremidades, uma fila da qual você pode inserir e remover elementos tanto pela frente quanto por trás.
from collections import deque
dq = deque([src])A ideia central
Uma aresta de peso 0 mantém a mesma distância, enquanto uma aresta de peso 1 acrescenta um. A fila de duas extremidades mantém os dois grupos em ordem.
A frente para arestas de peso zero
Atravessou uma aresta de peso 0? Use appendleft para inserir o vizinho, de modo que ele seja processado em seguida, pois não acrescenta nenhum custo à distância.
dq.appendleft(v)A parte de trás para arestas de peso um
Atravessou uma aresta de peso 1? Use append para inserir o vizinho no final, pois ele está uma camada mais distante da origem.
dq.append(v)Remova pela frente
Sempre use popleft para remover o nó atual. Isso mantém a fila de duas extremidades ordenada por distância, assim como uma BFS em camadas.
u = dq.popleft()Relaxe usando o peso
Relaxe cada aresta: calcule uma nova distância como dist[u] mais o peso da aresta e insira o nó na frente ou atrás de acordo com esse peso.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndPor que ela permanece ordenada
A fila de duas extremidades contém no máximo duas distâncias distintas ao mesmo tempo. Essa invariante explica exatamente por que inserir na frente ou atrás funciona.
A velocidade linear
Como não há montículo, o 0-1 BFS é executado em O(V + E), sendo perceptivelmente mais rápido que o Dijkstra no mesmo grafo.
Quando usá-lo
Use-o sempre que os movimentos sejam gratuitos ou custem um, como em grades nas quais alguns passos estão bloqueados e outros estão livres.
Verificação rápida
Você relaxa um vizinho através de uma aresta de peso 0. Onde ele deve ser inserido?
Revisão: 0-1 BFS
Com uma fila de duas extremidades, insira as arestas de peso 0 na frente e as de peso 1 atrás. Você obtém caminhos mínimos em tempo O(V+E), de forma simples. ⚡
Aprenda Python com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 30
- Aulas
- 120
Perguntas Frequentes
A aula “BFS 0-1 com uma Deque” é grátis?
Sim — o texto completo de “BFS 0-1 com uma Deque” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “BFS 0-1 com uma Deque”?
Encontre caminhos mínimos quando os pesos são 0 ou 1. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “BFS 0-1 com uma Deque”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Dijkstra com uma Heap
- BFS 0-1 com uma Deque
- Bellman-Ford e Arestas Negativas
- Floyd-Warshall para Todos os Pares