Algoritmi Python

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.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dalle onde sullo stagno al codice
queue = deque(["A"])🪨 Butta il sasso in A
node = queue.popleft()🌊 Prendi il prossimo nodo in ordine di distanza
if neighbor not in visited:🔎 Non ancora raggiunto?
queue.append(neighbor)➕ Aggiungilo all'anello successivo
Prima i nodi più vicini, usando una coda.
In una frase

La 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

  1. queue tiene i nodi in attesa di essere esplorati, prima i più vecchi.
  2. visited registra i nodi già trovati, così nessuno viene aggiunto due volte e i cicli non girano all'infinito.
  3. node = queue.popleft() prende il nodo successivo; i suoi vicini non visitati si mettono in fondo alla coda.
  4. order mostra 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

Esegui codice →
main.py
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)
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Segnare i nodi come visitati troppo tardi

Se un nodo viene segnato solo quando esce dalla coda, può essere aggiunto molte volte.

Problema
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
Correzione
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.

Tutte le sfide