BFS: percorso più breve e visita per livelli
Usi BFS per trovare il percorso più breve in un grafo non pesato, risolva word-ladder livello per livello e cloni un grafo usando una hash map
BFS: percorso più breve e visita per livelli è 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.
BFS e cammino minimo nei grafi non pesati
BFS trova il cammino minimo (con il minor numero di archi) in un grafo non pesato perché esplora i nodi in ordine di distanza crescente dalla sorgente. La prima volta che un nodo viene raggiunto durante BFS, viene raggiunto tramite il cammino più breve possibile. Questa proprietà non vale per DFS. Per i grafi pesati con pesi non negativi, utilizzi invece l'algoritmo di Dijkstra: BFS tratta implicitamente tutti gli archi come se avessero peso 1.
from collections import deque, defaultdict
def shortest_path(graph, start, end):
if start == end:
return 0
visited = {start}
queue = deque([(start, 0)]) # (node, distance)
while queue:
node, dist = queue.popleft()
for neighbour in graph[node]:
if neighbour == end:
return dist + 1
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, dist + 1))
return -1 # no path found
graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(0,3),(1,4)]:
graph[u].append(v); graph[v].append(u)
print(shortest_path(graph, 0, 3)) # 1 (direct edge)
print(shortest_path(graph, 0, 4)) # 2 (0->1->4)Tracciare il cammino minimo effettivo
Per ricostruire il cammino effettivo, non solo la sua lunghezza, mantenga un dizionario dei predecessori che registri come è stato raggiunto ciascun nodo. Quando raggiunge la destinazione, segua a ritroso la mappa dei predecessori dalla fine all'inizio e inverta il risultato. Questo aggiunge spazio O(V) per la mappa dei predecessori, ma fornisce il cammino completo in O(path_length) dopo il completamento di BFS.
from collections import deque, defaultdict
def shortest_path_with_route(graph, start, end):
parent = {start: None}
queue = deque([start])
while queue:
node = queue.popleft()
if node == end:
break
for nb in graph[node]:
if nb not in parent:
parent[nb] = node
queue.append(nb)
if end not in parent:
return [] # no path
# Reconstruct path by tracing back
path = []
node = end
while node is not None:
path.append(node)
node = parent[node]
return path[::-1] # reverse
graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(0,4),(4,3)]:
graph[u].append(v); graph[v].append(u)
print(shortest_path_with_route(graph, 0, 3)) # [0, 4, 3] or [0, 1, 2, 3]Word Ladder: BFS su un grafo implicito
Word Ladder (LeetCode #127) richiede di trovare il numero minimo di modifiche di un singolo carattere necessarie per trasformare una parola iniziale in una parola finale, dove ogni parola intermedia deve appartenere a un dizionario. Si tratta di una BFS su un grafo implicito in cui i nodi sono parole e gli archi collegano le parole che differiscono per una lettera. Generi tutte le mutazioni ottenute cambiando una lettera e verifichi se appartengono all'insieme di parole. BFS garantisce la sequenza minima di trasformazioni.
from collections import deque
def word_ladder(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)])
visited = {begin_word}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == end_word:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(word_ladder('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5Attraversamento per livelli: tracciare la distanza
L'attraversamento per livelli raggruppa i nodi in base alla loro distanza dalla sorgente, caratteristica utile per i problemi che richiedono un'elaborazione separata per ogni livello. Può tracciare la distanza memorizzandola nell'elemento della coda come tupla (node, dist) oppure utilizzando la tecnica della dimensione della coda: registri la dimensione della coda prima di ogni livello, elabori esattamente quel numero di nodi e poi incrementi un contatore del livello. Entrambi gli approcci producono risultati identici.
from collections import deque, defaultdict
def bfs_levels(graph, start):
levels = {}
visited = {start}
queue = deque([start])
dist = 0
while queue:
# Process all nodes at current distance
for _ in range(len(queue)):
node = queue.popleft()
levels[node] = dist
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
queue.append(nb)
dist += 1
return levels
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,3),(2,3),(3,4)]:
graph[u].append(v); graph[v].append(u)
print(bfs_levels(graph, 0)) # {0:0, 1:1, 2:1, 3:2, 4:3}Clonare un grafo
Clone Graph (LeetCode #133) crea una copia profonda di un grafo non orientato connesso. Utilizzi BFS e una mappa hash che associa i nodi originali alle rispettive copie. Quando visita un nodo per la prima volta, ne crei il clone e lo aggiunga alla mappa. Durante l'elaborazione dei nodi adiacenti, cerchi le rispettive copie o le crei, quindi colleghi gli archi. La mappa hash svolge una doppia funzione: tenere traccia dei nodi visitati e associare gli originali alle copie.
from collections import deque
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def clone_graph(node):
if not node:
return None
old_to_new = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for nb in curr.neighbors:
if nb not in old_to_new:
old_to_new[nb] = Node(nb.val)
queue.append(nb)
old_to_new[curr].neighbors.append(old_to_new[nb])
return old_to_new[node]
# Build a simple graph: 1 -- 2 -- 3 -- 4 -- 1
n1 = Node(1); n2 = Node(2); n3 = Node(3); n4 = Node(4)
n1.neighbors = [n2, n4]; n2.neighbors = [n1, n3]
n3.neighbors = [n2, n4]; n4.neighbors = [n3, n1]
cloned = clone_graph(n1)
print(cloned.val, [n.val for n in cloned.neighbors]) # 1 [2, 4]BFS bidirezionale
La BFS bidirezionale avvia BFS contemporaneamente dalla sorgente e dalla destinazione, espandendo un livello alla volta da entrambe le estremità. Quando le due frontiere si incontrano, è stato trovato il cammino minimo. Nei grafi di grandi dimensioni, questo riduce lo spazio di ricerca da O(b^d) a O(2 * b^(d/2)), dove b è il fattore di ramificazione e d è la lunghezza del cammino: un miglioramento notevole per grafi con cammini profondi, come quello di Word Ladder con dizionari di grandi dimensioni.
from collections import defaultdict
def word_ladder_bidir(begin, end, word_list):
word_set = set(word_list)
if end not in word_set:
return 0
front, back = {begin}, {end}
visited = {begin, end}
steps = 1
while front and back:
# Always expand the smaller frontier
if len(front) > len(back):
front, back = back, front
next_front = set()
for word in front:
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nw = word[:i] + c + word[i+1:]
if nw in back: # frontiers met!
return steps + 1
if nw in word_set and nw not in visited:
visited.add(nw)
next_front.add(nw)
front = next_front
steps += 1
return 0
print(word_ladder_bidir('hit','cog',['hot','dot','dog','lot','log','cog'])) # 5BFS 0-1 per grafi pesati
BFS 0-1 gestisce i grafi in cui i pesi degli archi sono esclusivamente 0 o 1. Anziché una coda normale, utilizzi un deque: aggiunga in fondo gli archi con peso 1 (livello successivo) e in testa quelli con peso 0 (stesso livello). In questo modo il calcolo dei cammini minimi ha complessità O(V + E), più veloce di O((V+E) log V) di Dijkstra quando i pesi sono binari. È comune nei problemi su griglia in cui alcune mosse sono gratuite e altre hanno costo 1.
from collections import deque
def zero_one_bfs(graph, start, n):
# graph: list of (neighbour, weight) where weight is 0 or 1
dist = [float('inf')] * n
dist[start] = 0
dq = deque([start])
while dq:
node = dq.popleft()
for nb, w in graph[node]:
if dist[node] + w < dist[nb]:
dist[nb] = dist[node] + w
if w == 0:
dq.appendleft(nb) # same level
else:
dq.append(nb) # next level
return dist
# Simple test:
graph = [[(1, 0), (2, 1)], # node 0: free to 1, cost 1 to 2
[(3, 1)], # node 1: cost 1 to 3
[(3, 0)], # node 2: free to 3
[]]
print(zero_one_bfs(graph, 0, 4)) # [0, 0, 1, 1]Walls and Gates (BFS multi-sorgente)
Walls and Gates riempie ogni stanza vuota con la distanza dal cancello più vicino. Utilizzi una BFS multi-sorgente: inizializzi simultaneamente la coda con tutti i cancelli (valore 0) ed espanda verso l'esterno. Il valore di ogni cella viene impostato al livello in cui viene raggiunta per la prima volta. Questa soluzione O(mn) è più efficiente dell'esecuzione separata di BFS da ogni stanza vuota, che avrebbe complessità O(m²n²).
from collections import deque
def walls_and_gates(rooms):
if not rooms:
return
rows, cols = len(rooms), len(rooms[0])
INF = float('inf')
queue = deque()
# Multi-source: all gates at distance 0
for r in range(rows):
for c in range(cols):
if rooms[r][c] == 0: # gate
queue.append((r, c))
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols and rooms[nr][nc]==INF:
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
rooms = [[float('inf'),-1,0,float('inf')],
[float('inf'),float('inf'),float('inf'),-1],
[float('inf'),-1,float('inf'),-1],
[0,-1,float('inf'),float('inf')]]
walls_and_gates(rooms)
print(rooms[0][0], rooms[1][1]) # 3, 2BFS di Snakes and Ladders
Snakes and Ladders (LeetCode #909) è un problema di cammino minimo risolvibile con BFS su una griglia numerata. Modelli il tabellone come un grafo non pesato in cui da ogni casella si può avanzare di 1-6 posizioni e si può finire su un serpente o una scala che teletrasporta il giocatore. BFS trova il numero minimo di lanci del dado. La difficoltà principale consiste nel convertire tra la posizione 1D e le coordinate della griglia 2D, tenendo conto della disposizione a righe alternate.
from collections import deque
def snakes_and_ladders(board):
n = len(board)
def get_board(pos):
r, c = divmod(pos - 1, n)
if r % 2 == 1: c = n - 1 - c # alternating direction
return board[n - 1 - r][c]
visited = {1}
queue = deque([(1, 0)])
while queue:
pos, moves = queue.popleft()
for dice in range(1, 7):
next_pos = pos + dice
if next_pos > n * n:
break
val = get_board(next_pos)
if val != -1:
next_pos = val # snake or ladder
if next_pos == n * n:
return moves + 1
if next_pos not in visited:
visited.add(next_pos)
queue.append((next_pos, moves + 1))
return -1
print('BFS models game as an unweighted shortest-path problem')Complessità e ottimizzazioni di BFS
La complessità temporale di BFS è O(V + E) perché ogni vertice viene inserito nella coda una volta e ogni arco viene esaminato un numero costante di volte. La complessità spaziale è O(V) per l'insieme dei visitati e la coda. Nei grafi a griglia, V = m*n ed E = 4*m*n (ogni cella ha 4 nodi adiacenti), quindi BFS su una griglia ha complessità O(mn). Ottimizzazione fondamentale: utilizzi un set per i visitati (ricerca in O(1)), non una lista (ricerca in O(n)). Contrassegni un nodo come visitato quando lo inserisce nella coda, non quando lo estrae.
# BFS on a graph with V vertices and E edges:
# Time: O(V + E) -- each vertex and edge visited once
# Space: O(V) -- visited set + queue
# BFS on an m x n grid:
# V = m*n cells
# E <= 4*m*n edges (4 directions, max)
# Time: O(m*n)
# Space: O(m*n)
# Common pitfalls:
# 1. Marking visited on dequeue (not enqueue) -> same node queued multiple times
# 2. Using a list for visited -> O(n) membership check -> O(V*E) total
# 3. Not handling disconnected graph -> BFS from single source misses components
print('O(V+E) time, O(V) space -- mark visited on enqueue')Lo 0 più vicino in una matrice binaria
01 Matrix (LeetCode #542) trova la distanza da ogni cella allo 0 più vicino. Una BFS multi-sorgente avviata simultaneamente da tutti gli 0 fornisce la soluzione ottimale O(mn). Inizializzi la coda con tutte le celle contenenti 0 alla distanza 0 e tutte le celle contenenti 1 a distanza infinita. BFS propaga le distanze verso l'esterno dagli 0, impostando la distanza di ogni cella contenente 1 la prima volta che viene raggiunta: ciò garantisce che sia la distanza minima.
from collections import deque
def update_matrix(mat):
rows, cols = len(mat), len(mat[0])
dist = [[float('inf')] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c))
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<rows and 0<=nc<cols:
if dist[r][c] + 1 < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
mat = [[0,0,0],[0,1,0],[1,1,1]]
result = update_matrix(mat)
for row in result: print(row) # [[0,0,0],[0,1,0],[1,2,1]]Controllo rapido
Metta alla prova la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso: BFS per i cammini minimi nei grafi non pesati, con tracciamento dei predecessori per ricostruire il percorso, Word Ladder come esempio canonico di BFS su un grafo implicito, la BFS bidirezionale per i grafi di grandi dimensioni e la BFS multi-sorgente per i problemi con più punti di partenza. Nel prossimo argomento applicheremo DFS alle componenti connesse e al flood fill.
Domande Frequenti
La lezione «BFS: percorso più breve e visita per livelli» è gratuita?
Sì — il testo completo di «BFS: percorso più breve e visita per livelli» è 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: percorso più breve e visita per livelli»?
Usi BFS per trovare il percorso più breve in un grafo non pesato, risolva word-ladder livello per livello e cloni un grafo usando una hash map 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: percorso più breve e visita per livelli»?
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
- Rappresentazioni dei grafi e configurazione dei percorsi
- BFS: percorso più breve e visita per livelli
- DFS: componenti connesse e flood fill
- Rilevamento dei cicli nei grafi diretti e non diretti