BFS per i cammini minimi non pesati
Calcolare la distanza dalla sorgente livello per livello
BFS per i cammini minimi non pesati è una lezione Coding Interview Prep 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cosa fa BFS
BFS esplora un grafo per livelli: prima il nodo di partenza, poi tutti quelli a distanza uno, poi quelli a distanza due e così via. 🌊
Perché i livelli indicano il cammino minimo
Poiché BFS completa ogni livello prima di passare al successivo, la prima volta che raggiunge un nodo trova il cammino non pesato più breve per raggiungerlo.
La coda è il motore
BFS utilizza una coda: primo a entrare, primo a uscire. I nuovi vicini vengono aggiunti in fondo e il primo elemento viene elaborato subito dopo.
from collections import deque
q = deque([start])Tenere traccia dei nodi visitati
Si mantiene un indicatore visited per non inserire mai due volte lo stesso nodo nella coda. Questo mantiene BFS veloce e finita.
visited = [False] * (n + 1)
visited[start] = TrueMemorizzare la distanza
Un array dist contiene il livello di ogni nodo. Il nodo di partenza ha valore 0; ogni vicino ha un valore maggiore di uno rispetto al proprio predecessore.
dist = [-1] * (n + 1)
dist[start] = 0Estrarre il primo elemento
A ogni passaggio si prende il nodo in testa alla coda. È il nodo non ancora elaborato più vicino, quindi va gestito subito.
u = q.popleft()Espandere i vicini
Per ogni vicino di u che non è stato visitato, lo si marca, si imposta la sua distanza e lo si inserisce in fondo alla coda.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Il ciclo completo
Si continua a estrarre ed espandere finché la coda non è vuota. Quando si svuota, sono stati visitati tutti i nodi raggiungibili.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Marcare all’inserimento
Impostate visited nel momento stesso in cui inserite il nodo nella coda, non quando lo estraete. Marcarlo in ritardo permette ai duplicati di entrare nella coda.
I nodi irraggiungibili restano a -1
Qualsiasi nodo che dopo BFS mantiene distanza -1 è semplicemente irraggiungibile dal punto di partenza. Anche questo è un risultato significativo.
BFS è lineare
BFS visita ogni nodo e ogni arco una sola volta, quindi ha complessità O(n + m). Questo consente di rispettare facilmente la maggior parte dei limiti delle competizioni.
Verifica rapida
Perché BFS standard trova i cammini minimi?
Riepilogo
Si esegue BFS con una coda e un array dist: si marca il nodo quando viene inserito, si espandono i vicini e, al termine, si leggono le distanze minime. 🎉
Impara Coding Interview Prep con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 90
- Lezioni
- 360
Domande Frequenti
La lezione «BFS per i cammini minimi non pesati» è gratuita?
Sì — il testo completo di «BFS per i cammini minimi non pesati» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «BFS per i cammini minimi non pesati»?
Calcolare la distanza dalla sorgente livello per livello Eserciti Coding Interview Prep 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep 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 per i cammini minimi non pesati»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep 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
- Liste di adiacenza dall’input
- BFS per i cammini minimi non pesati
- DFS, ricorsione e stack iterativi
- Componenti connesse e flood fill