BFS 0-1 con una Deque
Trovare cammini minimi con pesi pari a 0 o 1
BFS 0-1 con una Deque è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Un tipo speciale di grafo
Alcuni grafi hanno solo archi con peso 0 o 1. In questo caso è possibile superare Dijkstra con una tecnica più semplice e veloce.
Ecco 0-1 BFS
0-1 BFS trova i cammini minimi nei grafi con pesi 0/1 in tempo lineare, senza heap e senza alcun fattore logaritmico.
Lo strumento: una deque
Sostituisca l'heap con una deque, una coda in cui è possibile inserire ed estrarre elementi sia dall'inizio sia dalla fine.
from collections import deque
dq = deque([src])L'intuizione fondamentale
Un arco di peso 0 mantiene invariata la distanza, mentre un arco di peso 1 la aumenta di uno. La deque mantiene entrambi i gruppi nell'ordine corretto.
In testa per gli archi di peso zero
Attraversa un arco di peso 0? Usi appendleft per inserire il vicino all'inizio, così verrà elaborato subito dopo, poiché non aggiunge distanza.
dq.appendleft(v)In coda per gli archi di peso uno
Attraversa un arco di peso 1? Usi append per inserire il vicino alla fine, perché si trova a un livello di distanza in più dalla sorgente.
dq.append(v)Estrarre dalla testa
Esegua sempre popleft sul nodo corrente. In questo modo la deque rimane ordinata per distanza, proprio come in una BFS a livelli.
u = dq.popleft()Rilassare usando il peso
Rilassi ogni arco: calcoli la nuova distanza come dist[u] più il peso dell'arco, quindi inserisca il vicino in testa o in coda in base a quel peso.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndPerché rimane ordinata
La deque contiene al massimo due distanze distinte contemporaneamente. Questo invariante spiega esattamente perché funziona l'inserimento in testa o in coda.
La velocità lineare
Poiché non c'è alcun heap, 0-1 BFS richiede O(V + E), risultando sensibilmente più veloce di Dijkstra sullo stesso grafo.
Quando utilizzarlo
Lo utilizzi quando gli spostamenti sono gratuiti o costano uno, ad esempio nelle griglie in cui alcuni passi sono bloccati e altri liberi.
Verifica rapida
Rilassa un vicino attraverso un arco di peso 0. Dove deve inserirlo?
Riepilogo: 0-1 BFS
Con una deque, inserisca gli archi di peso 0 in testa e quelli di peso 1 in coda. Otterrà i cammini minimi in un chiaro tempo O(V+E). ⚡
Domande Frequenti
La lezione «BFS 0-1 con una Deque» è gratuita?
Sì — il testo completo di «BFS 0-1 con una Deque» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «BFS 0-1 con una Deque»?
Trovare cammini minimi con pesi pari a 0 o 1 Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «BFS 0-1 con una Deque»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Dijkstra con un heap
- BFS 0-1 con una Deque
- Bellman-Ford e archi negativi
- Floyd-Warshall per tutte le coppie