La ricerca in ampiezza (BFS) in Python
In questa lezione percorrerai un grafo livello per livello con la ricerca in ampiezza e una coda deque.
Introduzione
Il problema
Quanti passi servono per andare da una persona a un'altra in un social network, o da una casella di un labirinto all'uscita? La ricerca in ampiezza esplora ad anelli di distanza, quindi la prima volta che raggiunge un nodo lo fa lungo un percorso più breve.
Immaginalo così
La ricerca in ampiezza è come le onde su uno stagno. Butta un sasso nel punto di partenza e l'onda raggiunge prima tutto ciò che è a un passo, poi tutto ciò che è a due passi, e così via. Niente di più lontano viene toccato prima che sia stato raggiunto tutto ciò che è più vicino.
queue = deque(["A"])🪨 Butta il sasso in Anode = queue.popleft()🌊 Prendi il prossimo nodo in ordine di distanzaif neighbor not in visited:🔎 Non ancora raggiunto?queue.append(neighbor)➕ Aggiungilo all'anello successivoLa ricerca in ampiezza (BFS) visita un grafo livello per livello a partire da un nodo, usando una coda, quindi trova i percorsi più brevi nei grafi senza pesi.
Punti chiave
queuetiene i nodi in attesa di essere esplorati, prima i più vecchi.visitedregistra i nodi già trovati, così nessuno viene aggiunto due volte e i cicli non girano all'infinito.node = queue.popleft()prende il nodo successivo; i suoi vicini non visitati si mettono in fondo alla coda.ordermostra A, poi i suoi vicini B e C, poi D ed E un livello più in là.
Quando si usa?
- Percorsi più brevi in grafi senza pesi, griglie e labirinti.
- Gradi di separazione nei social network.
- Web crawler e trovare tutto ciò che è raggiungibile da un punto di partenza.
Quando non serve
- Gli archi hanno costi diversi, come le distanze stradali: usa l'algoritmo di Dijkstra.
- Devi esplorare un percorso fino in fondo prima degli altri, come per il backtracking: usa la ricerca in profondità.
Visualizzatore di La ricerca in ampiezza (BFS) in Python
O(V + E)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print(order)
Risultato dell'esecuzione
['A', 'B', 'C', 'D', 'E']
Spiegazione del codice
La coda queue contiene i vertici in attesa di essere visitati, che escono nello stesso ordine in cui sono entrati. L'insieme visited registra i vertici già incontrati, per non visitare più volte lo stesso vertice quando il grafo ha cicli. L'ordine di visita è A, B, C, D, E, e la complessità è O(V + E), dove V è il numero di vertici ed E quello degli archi.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Segnare i nodi come visitati troppo tardi
Se un nodo viene segnato solo quando esce dalla coda, può essere aggiunto molte volte.
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Media
- Tree Diameter A tree is a connected undirected graph with no cycles. Media
- Count Islands Count groups of connected land cells in a grid. Media