BFS para Caminhos Mínimos sem Pesos
Calcule a distância camada por camada a partir de uma origem.
BFS para Caminhos Mínimos sem Pesos é 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.
O que BFS faz
BFS explora um grafo em camadas: primeiro o ponto inicial, depois tudo que está a um passo, depois a dois passos e assim por diante. 🌊
Por que as camadas indicam o caminho mais curto
Como BFS termina cada camada antes de passar à próxima, a primeira vez que alcança um nó corresponde ao caminho não ponderado mais curto até ele.
A fila é o mecanismo principal
BFS usa uma fila: primeiro a entrar, primeiro a sair. Você adiciona novos vizinhos ao final e processa primeiro o elemento da frente.
from collections import deque
q = deque([start])Acompanhar o que já foi visto
Mantenha um marcador de visitado para nunca inserir o mesmo nó na fila duas vezes. Isso mantém BFS rápido e finito.
visited = [False] * (n + 1)
visited[start] = TrueArmazenar a distância
Um vetor de distâncias armazena a camada de cada nó. O nó inicial recebe 0; cada vizinho recebe um valor maior que o de seu antecessor.
dist = [-1] * (n + 1)
dist[start] = 0Remover o primeiro elemento
A cada etapa, retire o nó que está na frente da fila. Ele é o nó não processado mais próximo, portanto deve ser tratado agora.
u = q.popleft()Expandir os vizinhos
Para cada vizinho não visitado de u, marque-o, defina sua distância e coloque-o no final da fila.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)O laço completo
Continue removendo elementos e expandindo enquanto a fila não estiver vazia. Quando ela esvaziar, você terá visitado todos os nós alcançáveis.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Marcar ao enfileirar
Defina visitado no momento em que inserir o nó na fila, não quando removê-lo. Marcar tarde permite que duplicatas entrem na fila.
Nós inalcançáveis permanecem em -1
Qualquer nó que ainda tenha distância -1 após BFS é simplesmente inalcançável a partir do seu ponto inicial. Essa resposta também é significativa.
BFS é linear
BFS toca em cada nó e aresta uma vez, portanto é executado em O(n + m). Isso atende facilmente à maioria dos limites de competições.
Verificação rápida
Por que BFS simples encontra os caminhos mais curtos?
Recapitulação
Você executa BFS com uma fila e um vetor de distâncias: marca ao enfileirar, expande os vizinhos e lê as menores distâncias ao final. 🎉
Perguntas Frequentes
A aula “BFS para Caminhos Mínimos sem Pesos” é grátis?
Sim — o texto completo de “BFS para Caminhos Mínimos sem Pesos” é 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 para Caminhos Mínimos sem Pesos”?
Calcule a distância camada por camada a partir de uma origem. 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 para Caminhos Mínimos sem Pesos”?
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
- Listas de Adjacência a partir da Entrada
- BFS para Caminhos Mínimos sem Pesos
- DFS, Recursão e Pilhas Iterativas
- Componentes Conexos e Preenchimento por Inundação